1240 : 机器人兄弟

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

Source

Author

THU