TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2539
  • 题目
  • P2539【博弈】图删边游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Alice & Bob有一天发现了一株奇怪的灌木、他的枝分叉之后又可以汇合、更奇特的是不仅是同一点的分叉可以汇合、即使分叉点相差很远、两根枝条仍然可以生长到一起(组织连在一块儿了)。

    在我们看来他可以抽象为一个无向图。其中有唯一结点是根。
    他们认为这是用来玩游戏的绝佳材料。于是他们打算在这棵树上玩伐木游戏,规则如下:
    1.两人轮流从灌木上截下枝条(图上的边),每截下一根枝条就将与根不再相连的部分去掉。
    2.截去最后一根枝条的人获胜
    Alice 先手。
    对于给出的无向图输出输出胜利的人的名字。

    输入格式

    第一行, 一个整数K表示有K组测试数据,对于每组测试数据:
    第一行,一个空行
    第二行,两个空格间隔的整数N和M,表示图的节点数,M表示无向图中的边数。1号节点为根
    第三行,一个空行
    接下来M行,每行两个空格间隔的整数X、Y,表示节点X和Y间有边相连

    输出格式

    一个单词,表示获胜者的名字

    样例输入

    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<=3000,M<=100000


    来源  IPSC 2003 got root