Problem 4F. 剪纸游戏

时间限制：2s

空间限制：256MB

题目描述

Alice和Bob正在玩一个剪纸游戏：纸的大小可以用 \(r \times 2\) 大小的矩形来表示，两人轮流剪去这张纸的一个 \(1 \times 1\) 的矩形块，但是要求在剪的过程中纸不能被剪成多张；也就是说，如果 \((i,c)\) 这个正方形块被剪去了，那么下一步就不能剪去 \((i-1,3-c)\), \((i, 3-c)\), \((i+1, 3-c)\) 这三个正方形块；因为一旦剪去这三个正方形块中的一个，这张纸就会被”剪断“。

特别的，如果最后只剩下 \(1 \times 1\) 的矩形，那么也不能将其剪去。

现在给定一个初始被剪去 \(n\) 个小正方形的 \(r \times 2\) 的矩形，Alice 先手进行剪纸操作，如果到某个人无法进行剪纸操作，那么另外一个人获胜。假设Alice和Bob都是足够聪明的，请问最后谁会获得胜利？

输入格式

第一行包括两个整数 \(r, n\),分别代表矩形的行数和一开始被剪去的正方形块数量；

下面 \(n\) 行每行两个整数 \(r_i\), \(c_i\), 代表初始每个被剪去的正方形块的行号和列号。

数据保证一开始的矩形不会被剪断。

输出格式

输出一行字符串，如果最后 Alice 能获得胜利，则输出 "Alice"；如果最后 Bob 能获得胜利，则输出 "Bob".

样例1

输入

3 1
1 2

输出

Alice

解释

如下图所示，一开始黄色位置的小正方形被剪去了；那么Alice只需要选择绿色位置的小正方形剪去，下一步Bob将会无法进行任何操作，Alice获得胜利。

样例2

输入

12 4
5 1
7 2
8 2
10 1

输出

Alice

样例3

输入

1 1
1 1

输出

Bob

数据范围

对于 \(60\%\) 的数据，\(1 \le r \le 5\);

对于 \(100\%\) 的数据，\(1 \le r \le 500\), \(0 \le n \le r\),\(1 \le r_i \le r\),\(1 \le c_i \le 2\).