1240 : 机器人兄弟

Description

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

今天的游戏是这样的：

有一棵有 $n$ 个点的有根树，其中有 $m$（$m\ge 3$）个叶子（度数为 $1$ 且不为根结点的结点），叶子的编号恰好为 $1\sim m$ 的一个排列。

Doodle 和 Doddle 最初都站在根结点 $n$ 上，两人轮流执行下述操作，Doodle 先操作：

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

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

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

• 若 $xmodm=(y+1)modm$，那么 Doodle 获胜。

• 若 $(x+1)modm=ymodm$，那么 Doddle 获胜。

• 否则是一个平局。

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

请判断最终谁会获胜。

Input

本题有多组测试数据。第一行一个正整数 $T$（$1\le T\le {10}^5$）表示数据组数。对于每组数据，

• 第一行两个正整数 $n$（$4\le n\le {10}^5$），$m$（$3\le 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