P11017 Hide And Seek

Drifty is playing hide-and-seek with hgcnxn. The whole map has $n$ rooms, connected by $n-1$ corridors (it is guaranteed that any two rooms are reachable from each other). In each round of the game, hgcnxn moves first, and Drifty moves after (in particular, hgcnxn must move exactly one step, while Drifty may choose to stay still). hgcnxn starts from room $p$ and wants to catch Drifty. Using a radar, hgcnxn knows that Drifty initially is in room $q$. hgcnxn will design an as-optimal-as-possible capture plan in advance, and then follow this plan to chase Drifty. **However, hgcnxn does not know Drifty's position in the later rounds.** But Drifty is even more cunning: he knows hgcnxn's entire plan in advance, and uses the best strategy to try to avoid hgcnxn. Still, due to the map, Drifty may end up being caught. In particular, hgcnxn does not know that Drifty can know his entire plan in advance. Now you are given $n$, $p$, $q$, and the map. Determine whether within $10^{100}$ rounds, hgcnxn can possibly catch Drifty.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: The first line contains three integers $n$, $p$, $q$. The next $n-1$ lines each contain two nodes $u$, $v$, indicating a corridor connecting the two rooms.

For each test case: Output one string. If hgcnxn can possibly catch Drifty, output `hgcnxn`; otherwise output `Drifty`. In particular, for judging, letter case does not matter. If the correct output is `Drifty` but you output `driFtY`, you will still be judged as correct.

#### Constraints Let $\sum n$ be the sum of $n$ within a single test point. For $100\%$ of the testdata, it is guaranteed that: - $3\le \sum n\le 2\times 10^5$ - $1\le p,q\le n$ - $1\le T\le 10^3$. Below is the detailed distribution of subtasks: |$\text{Subtask}$|$\sum n\leq$|Score| Special Property | |:-:|:-:|:-:|:-:| |$0$|$2\times 10^5$|$1$| A | |$1$|$2\times 10^5$|$2$| B | |$2$|$7$|$3$| None | |$3$|$2\times 10^5$|$9$| C | |$4$|$2\times 10^5$|$85$| None | - Special Property A: It is guaranteed that all given maps are paths. - Special Property B: It is guaranteed that all given maps are star graphs (i.e. $n-1$ rooms have degree $1$). - Special Property C: It is guaranteed that there is exactly one room with degree $3$ in the map, and all other rooms have degree $\le 2$. Here, the degree of a room is defined as the number of corridors connected to that room. Translated by ChatGPT 5