CSG-CPC
Online Judge

1240 : 机器人兄弟

         Time Limit: 1.5 Sec     Memory Limit: 512 Mb     Submitted: 238     Solved: 47    

Description

Doodle 和 Doddle 是机器人兄弟,他们喜欢在一起做游戏。

今天的游戏是这样的:

有一棵有 \(n\) 个点的有根树,其中有 \(m\)\(m\geq 3\))个叶子(度数为 \(1\) 且不为根结点的结点),叶子的编号恰好为 \(1\sim m\) 的一个排列。

Doodle 和 Doddle 最初都站在根结点 \(n\) 上,两人轮流执行下述操作,Doodle 先操作:

  • 若当前节点为一个叶子,则不操作。

  • 若当前节点不为叶子,则选择一个该点在树上的子节点并移动到该子节点。

当两人都到达叶子时,游戏结束。令 Doodle 所在的叶子编号为 \(x\),Doddle 为 \(y\)

  • \(x\bmod m=(y+1)\bmod m\),那么 Doodle 获胜。

  • \((x+1)\bmod m=y\bmod m\),那么 Doddle 获胜。

  • 否则是一个平局。

Doodle 和 Doddle 都是极其聪明的机器人,所以他们一定会采用最优策略。

请判断最终谁会获胜。

Input

本题有多组测试数据。第一行一个正整数 \(T\)\(1\leq T\leq 10^5\))表示数据组数。对于每组数据,

  • 第一行两个正整数 \(n\)\(4\leq n\leq 10^5\)),\(m\)\(3\leq m<n\))表示树的结点数以及叶子的数量。
  • 接下来 \(n-1\) 行每行两个正整数 \(x,y\) 表示树上的一条边。
  • 保证 \(1,2,\dots, m\) 恰好为树的所有叶子,且结点 \(n\) 为树的根。

保证所有数据的 \(n\) 的和不超过 \(5\times 10^5\)

Output

对于每组数据,若 Doodle 获胜输出 Doodle,若 Doddle 获胜输出 Doddle,若平局输出 Tie

Sample

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

Hint

Author

THU