#P18528. Bot Brothers
Bot Brothers
Bot Brothers
Doodle 和 Doddle 是喜欢一起玩游戏的机器人兄弟。
给定一棵有 个节点的有根树,其中有 个叶子。这里,叶子指度数为 1 且不是根的节点。叶子的编号恰为 ,根的编号为 。
两人最初都在根 。他们轮流操作,Doodle 先手。每人操作自己所在的节点:
- 如果已经在叶子上,什么也不做,仍然轮到另一人操作。
- 否则,选择当前节点的一个儿子,沿边移动到该儿子。
当两人都到达叶子时,游戏结束。设 Doodle 所在的叶子编号为 ,Doddle 所在的叶子编号为 :
- 若 ,Doodle 获胜。
- 若 ,Doddle 获胜。
- 否则为平局。
两人都采取最优策略。请确定最终结果。
输入格式
第一行包含整数 (),表示测试用例数。对每个测试用例:
第一行包含两个整数 ,满足 、。
接下来 行,每行两个整数 (),表示树的一条无向边。
保证 恰好是这棵树的全部叶子, 是根。全部测试用例的 之和不超过 。
输出格式
每个测试用例输出一行:Doodle 获胜时输出 Doodle,Doddle 获胜时输出 Doddle,平局时输出 Tie。
原样例
2
6 3
1 4
2 4
3 5
5 6
4 6
5 4
1 5
2 5
3 5
4 5
Tie
Doddle