OI题库

【题目描述】

著名的生物学家Herbert Greenstuff最近发现了一种新的植物，graphius vulgaris，显然是斯洛伐克西部Pezinska Baba国家荒野所特有的。这种植物非常罕见。初看上去它就像普通的灌木。但仔细观察，你就会注意到它的结构复杂得多。当这种灌木的两条分支接触到彼此时，它们有可能长在一起从而重新汇合。实际上，它们经常这样。结果就是，这种灌木令人难以置信地扭曲和稠密（如果Herbert不是一名生物学家而是一名计算机科学家，他就会注意到从图论的观点上看，这种植物并不是一棵树而是一个普通的无向连通图）。

几天以后这些灌木被两名学计算机科学的学生，Alice和Bob第二次发现了。你可能认识他们，他们因为夜以继日地玩游戏（以及执行加密协议）而著名。当Alice发现这些灌木时，他们正在玩一个简单的NIM游戏。他们立即忘掉了那个NIM游戏。这些灌木是玩一个远比它有趣的游戏的理想机会。

输入一张有N个顶点的连通图（灌木）。这些顶点从1到N编号，顶点1代表大地。边代表灌木的分支。玩家轮流进行移动，Alice先手。一个移动包含两步。第一步玩家选择一条边并且将其从图中移除。第二步他/她移除所有不再与地面连通的边（玩家剪掉灌木的一根枝条并且移去灌木被切掉的部分。）第一名无法进行合法移动（没有边可以剪掉了）的玩家输掉游戏。你可以假设Alice和Bob都以最优策略移动。

任务非常简单，以至于你的键盘可能已经饥渴难耐了。你要在Alice和Bob摧毁灌木丛之前保护它们。对灌木丛中的每一棵灌木，你要找到如果他们在这棵灌木上玩游戏，最终赢的人。当你把结果剧透给他们后，就会剥夺游戏的一切乐趣，因此他们就会放过这些灌木。请快一些，这种灌木十分罕见！

【输入格式】

输入文件的第一行有一个整数B，代表灌木棵数。

接下来有B组数据，每组描述了一棵灌木。

每组数据的第一行有两个空格隔开的整数N，M，其中N是这棵灌木的顶点数，M是边数。接下来是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

【提示】

N<=50000，M<=50000

【来源】

IPSC 2003 Problem G - Got Root？