题目描述

Drifty 在和 hgcnxn 玩躲猫猫。

整个地图有 $n$ 个房间，由 $n-1$ 条走廊连接（保证对于任意的两个房间都能互相抵达）。

对于游戏的每一回合，hgcnxn 先走一步，Drifty 后走一步（特别的，hgcnxn 必须走一步，而 Drifty 可以不动）。

hgcnxn 从编号为 $p$ 的房间开始，任务是要抓到 Drifty，hgcnxn 通过雷达，得知了 Drifty 一开始所在的房间编号 $q$，hgcnxn 会预先设计一条尽可能优的抓捕方案，并按照计划抓捕 Drifty。但 hgcnxn 并不知道接下来的回合中 Drifty 的位置。

但是，Drifty 更加狡猾，他提前预知了 hgcnxn 的整个计划，并采用了最优的方案尝试去避开 hgcnxn。但是鉴于地图的原因，Drifty 可能还是会被抓到。

特别的，hgcnxn 并不知道 Drifty 能够提前知道他的整个计划。

现在给你 $n, p, q$ 和地图，问你在有限的回合内，hgcnxn 是否可能抓到 Drifty。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行三个整数 $n, p, q$。

接下来 $n-1$ 行，每行两个节点 $u, v$，表示一条走廊连接的两个房间。

输出格式

对于每组数据：

一个字符串，若 hgcnxn 可能抓到 Drifty，输出 hgcnxn，若 hgcnxn 不可能抓到 Drifty，输出 Drifty。

特别的，对于答案的判定，我们不区分大小写。

如果应输出 Drifty，但您输出了 driFtY，您将被判定作正确。

2
3 1 3
1 2
2 3
5 2 4
1 2
1 3
1 4
1 5

hgcnxn
hgcnxn

提示

【数据范围】

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于 $100\%$ 的数据，保证：

• $3\le \sum n\le 2\times 10^5$
• $1\le p,q\le n$
• $1\le T\le 10^3$。

以下是部分分的具体分配：

$\text{Subtask}$	$\sum n\leq$	分值	特殊性质
$0$	$2\times 10^5$	$1$	A
$1$		$2$	B
$2$	$7$	$3$	无
$3$	$2\times 10^5$	$9$	C
$4$		$85$	无

• 特殊性质 A：保证所有给定的地图的形态均为一条链。
• 特殊性质 B：保证所有给定的地图的形态均为菊花图（即地图中 $n-1$ 个房间度数为 $1$）。
• 特殊性质 C：保证地图中只存在一个度数为 $3$ 的房间，且其余的房间度数均 $\le 2$。

其中，一个房间的度数被定义为连接该房间的走廊数。