问题 G: 第四天灾

问题 G: 第四天灾

时间限制: 1 Sec  内存限制: 128 MB
提交: 62  解决: 25
[状态] [讨论版] [提交] [命题人:]
题目描述
A学长和B学长准备通过游戏来决定谁是真正的第四天灾。
游戏规则如下:地图上一共有n个星域,编号由1到n。玩家依次进行以下决定:选择地图上任意一个孤立的星域(只有一条路线与其他星域连接的星域),将该星域即其连接路线一同移除。有一个编号为x的特殊节点,移除此节点的玩家将获得胜利。
A学长先手。保证两位学长都不会失误。
输入
第一行输入t(1<=t<= 100),测试样例的数量。
第二行输入n和x(1<=n<=1000,1<=x<=n)
接下来n-1行输入u和v(1<=u,v<=n, u≠v)表示两不同星域的编号,说明两星域有连接
输出
如果A学长胜利输出"A is the fourth day disaster",否则输出"B is the fourth day disaster"。
样例输入 Copy
1
3 2
1 2
1 3
样例输出 Copy
A is the fourth day disaster