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$.