アメカーの部屋

时空限制#

C/C++: 2s/512MB

其他语言：4s/1024MB

题目背景#

「与艺术家的绘画一起留下的诗的最后，如此这般地写道。」

「艺术家去世之后，一如往常的人们，一如往常的幸福光景延伸着。」

「轻轻晃动的樱的森林中响起世界的声音，优美的音色奏响起世界之声。」

题目描述#

在美术室里，草薙直哉正在教御樱稟绘画。稟在画板上画了一片樱花林，其中有 $m$ 棵樱花树。第 $i$ 棵樱花树可以看作一棵以节点 $1$ 为根，共有 $n_i$ 个节点的树¹。

现在，所有樱花树上作为叶节点²的樱花都还没有上色。

稟想把尽可能多的樱花染成粉色，直哉想把尽可能多的樱花染成红色。于是两人决定进行如下游戏。

游戏由若干局组成。第一局由稟开始。

当一局开始时，当前玩家需要从整片樱花林中选择一朵尚未染色的樱花 $v$。假设 $v$ 位于某樱花树中。随后，两人从该樱花树的根节点 $1$ 开始，沿着从 $1$ 到 $v$ 的唯一路径轮流移动画笔，选择樱花的玩家先手。

在一次移动中，当前玩家必须将画笔沿着这条路径向 $v$ 的方向移动至少 $1$ 条边，至多 $k$ 条边。

如果某次移动后，画笔到达了樱花 $v$，则执行这次移动的玩家将 $v$ 染成自己的颜色，本局立即结束。

本局结束后，如果仍存在尚未染色的樱花，则游戏进入下一局。下一局由刚刚染色该樱花的玩家的对手开始。

当所有樱花都被染色后，游戏结束。

若最终稟染色的樱花数量更多，则稟获胜；若直哉染色的樱花数量更多，则直哉获胜；若两人染色数量相同，则平局。

双方都采取最优策略。稟想知道游戏的最终结果。

输入格式#

每个测试包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每组测试用例：

第一行包含两个整数 $m, k$ ($1 \le m \le 10^5$，$1 \le k \le 2 \times 10^5$)，分别表示樱花树的数量和每次移动最多经过的边数。

接下来依次描述 $m$ 棵樱花树。

对于第 $i$ 棵樱花树：

• 第一行包含一个整数 $n_i$ ($2 \le n_i \le 2 \times 10^5$)，表示第 $i$ 棵樱花树的节点数；
• 接下来 $n_i - 1$ 行，每行包含两个整数 $u, v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

每棵樱花树的节点均从 $1$ 到 $n_i$ 编号，且节点 $1$ 为根节点。

设 $S$ 表示一组测试用例中所有樱花树的节点总数，保证 $2 \le S \le 2 \times 10^5$。

数据保证所有测试用例中 $S$ 的总和不超过 $10^6$，并且输入的每棵樱花树均为一棵合法的树。

输出格式#

对于每个测试用例，输出一行：

• 如果稟获胜，输出 $Rin$；
• 如果直哉获胜，输出 $Naoya$；
• 如果平局，输出 $Draw$。

样例#

1
3
2
1 2
3
3
4
1 2
5
2 3
6
1 1
7
3
8
1 2
9
2 3
10
2 2
11
2
12
1 2
13
2
14
1 2

1
Rin
2
Naoya
3
Draw

说明/提示#

对于第一组测试用例，唯一的叶节点是 $3$。由于 $k = 2$，稟第一步可以从 $1$ 移动到 $3$，将叶节点 $3$ 染成粉色。所有叶节点均被染色，游戏结束，稟获胜。

对于第二组测试用例，唯一的叶节点是 $3$。由于 $k = 1$，稟第一步只能从 $1$ 移动到 $2$，无法直接到达 $3$。随后直哉从当前位置 $2$ 出发，移动到 $3$，将叶节点 $3$ 染成红色。所有叶节点均被染色，游戏结束，直哉获胜。