#P18528. Bot Brothers

Bot Brothers

Bot Brothers

Doodle 和 Doddle 是喜欢一起玩游戏的机器人兄弟。

给定一棵有 nn 个节点的有根树,其中有 m≥3m\ge3 个叶子。这里,叶子指度数为 1 且不是根的节点。叶子的编号恰为 1,2,…,m1,2,\ldots,m,根的编号为 nn。

两人最初都在根 nn。他们轮流操作,Doodle 先手。每人操作自己所在的节点:

  • 如果已经在叶子上,什么也不做,仍然轮到另一人操作。
  • 否则,选择当前节点的一个儿子,沿边移动到该儿子。

当两人都到达叶子时,游戏结束。设 Doodle 所在的叶子编号为 xx,Doddle 所在的叶子编号为 yy:

  • 若 x mod m=(y+1) mod mx\bmod m=(y+1)\bmod m,Doodle 获胜。
  • 若 (x+1) mod m=y mod m(x+1)\bmod m=y\bmod m,Doddle 获胜。
  • 否则为平局。

两人都采取最优策略。请确定最终结果。

输入格式

第一行包含整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。对每个测试用例:

第一行包含两个整数 n,mn,m,满足 4≤n≤1054\le n\le10^5、3≤m<n3\le m<n。

接下来 n−1n-1 行,每行两个整数 x,yx,y(1≤x,y≤n1\le x,y\le n),表示树的一条无向边。

保证 1,2,…,m1,2,\ldots,m 恰好是这棵树的全部叶子,nn 是根。全部测试用例的 nn 之和不超过 5×1055\times10^5。

输出格式

每个测试用例输出一行: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