[IPSC2003]到根了吗?

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file gotroot.in Output file gotroot.out

【题目描述】

著名的生物学家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?