IPSC2003 Got Root?

Alice 和 Bob 有一天发现了一株奇怪的灌木：它的枝条分叉之后又可以汇合，更奇特的是，即使两个分叉点相差很远，两根枝条仍然可以生长到一起（组织连在一块儿了）。在我们看来，它可以抽象为一个无向连通图，图中有唯一的结点是根（代表地面）。

他们认为这是用来玩游戏的绝佳材料，于是打算在这株灌木上玩伐木游戏，规则如下：

1. 两人轮流从灌木上截下一根枝条（图上的一条边），每截下一根枝条，就将与根不再相连的部分一并去掉；
2. 无法进行操作（没有枝条可截）的人失败，也就是截去最后一根枝条的人获胜。

Alice 先手，双方都采用最优策略。对于给出的无向图，输出获胜者的名字。

输入格式

第一行是灌木的数目 $B$。

接下来是 $B$ 段数据，每段描述一株灌木。每段数据以两个由空白字符分隔的整数 $N, M$ 开始，其中 $N$ 是该灌木的结点数，$M$ 是边数；结点编号为 $1$ 到 $N$，其中 $1$ 号结点代表地面。接下来给出 $M$ 条边，每条边由它所连接的两个结点的编号描述。所有这些数字之间都由空白字符分隔。

输出格式

对于输入中的每一段数据，输出一行，包含在该灌木上进行游戏的获胜者的名字（即 Alice 或 Bob）。

样例输入

2

8 7

1 2
1 3
3 4
1 5
5 6
6 7
7 8

5 6

1 2
1 3
3 2
1 4
5 1
4 5

样例输出

Alice
Bob

来源与许可

本题为 IPSC 2003 试题「Got Root?」，题面与测试数据整理自 BZOJ 1463。

样例 1

输入

2

8 7

1 2
1 3
3 4
1 5
5 6
6 7
7 8

5 6

1 2
1 3
3 2
1 4
5 1
4 5

输出

Alice
Bob