题目描述

爱丽丝（Alice）和鲍勃（Bob）经常一起玩游戏，他们总是喜欢尝试新游戏。现在他们发明了一个名为“ESCAPE”的新游戏。这个游戏是怎么玩的呢？

游戏基于一个无向图（他们在游戏开始前绘制好）。两位玩家轮流进行操作：

• 每轮玩家必须选择一个顶点，该顶点需满足以下两个条件：
  1. 必须与对手上一轮选择的顶点相邻（首轮可以选择任意顶点）；
  2. 该顶点未被选择过。
• 无法选择顶点的玩家输掉游戏。

假设爱丽丝总是先手，且双方均采取最优策略。现在给定图的结构，请预测谁会获胜。

输入格式

• 第一行输入一个整数 $T$（测试用例数量）。
• 每个测试用例包含多行：
  • 第一行两个整数 $N$（顶点数，$1 \leq N \leq 50$）和 $M$（边数）。
  • 接下来 $M$ 行，每行两个整数 $a$ 和 $b$（$1 \leq a, b \leq N$），表示顶点 $a$ 和 $b$ 之间有一条边。

输出格式

• 对于每个测试用例，输出一行：
  • 如果爱丽丝必胜，输出 "alice"；
  • 如果鲍勃必胜，输出 "bob"；
  • 若无法确定（题目保证不会出现此情况），输出 "I don't know"。

示例输入 1

2
2 1
1 2
3 2
1 2
2 3

示例输出 1

bob
alice

题目来源

POJ Monthly, dodo