Description

Brief statement

You are given a tree with $n$ nodes (guaranteed $n\ge 2$). Hifuu and Luna take turns making moves, with Hifuu moving first. In each turn, the player chooses a node, deletes "that node" and "all edges connected to that node", which splits the tree into several connected components. The player then keeps exactly one of these connected components. If after the turn ends there is only one node left, then the player who made that move loses and the other player wins. Determine who has a winning strategy.

---

Original statement

However, the Lunar Capital is protected by a barrier, which means that if Renko and Maribel want to travel to the Moon by some method, they must break through this barrier.

The barrier of the Lunar Capital is a connected structure consisting of $n$ nodes and $n-1$ psychic energy transmission channels, where the nodes are numbered from $1 \sim n$. The barrier has a central control system to guard against outsiders breaking into the barrier and reaching the Lunar Capital. Renko and Maribel need to interact with this control system in order to enter the Lunar Capital.

More specifically, Renko and Maribel and the central control system take turns operating, and Renko and Maribel move first. On each move, the player may choose any node on the barrier, cut off all psychic energy transmission channels connected to this node, and discard this node. This means the barrier will be split into several groups of nodes: there are no psychic energy transmission channels between different groups, while nodes within a group remain connected by these channels. Among these node groups, the player may choose to keep one group of nodes and discard all other nodes, i.e., those discarded nodes can no longer be operated on in the future.

Under these rules, if after the move ends only one node remains, then the player who made that move loses and the other player wins. Now Renko and Maribel want to know: under these rules, do they have a strategy that guarantees they can reach the Lunar Capital?

Input Format

This problem contains multiple test cases. The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains a positive integer $n$.
• The next $n-1$ lines each contain two positive integers $u_i,v_i$, representing a bidirectional psychic energy transmission channel connecting node $u_i$ and node $v_i$.

Output Format

For each test case, output whether Renko and Maribel can reach the Lunar Capital. Specifically, if they have a strategy that guarantees reaching the Lunar Capital, output $\texttt{Hifuu}$; otherwise output $\texttt{Luna}$.

1
5
2 4
1 2
3 1
5 2

Hifuu

1
11
1 2
1 3
1 4
2 5
2 6
4 7
5 8
5 9
9 10
9 11

Hifuu

1
2
1 2

Luna

Hint

Sample explanation

Sample #1

Figure $1$ shows the barrier. Figure $2$ and Figure $3$ show one possible winning strategy for Renko and Maribel: choose node $2$, then keep the connected component containing $\{1,3\}$. Then no matter whether the central control system chooses node $1$ or node $3$, it must lose.

Sample #2

---

Constraints

This problem uses bundled tests.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \textbf{\textsf{特殊性质}} & \textbf{Subtask \textsf{依赖}}\cr\hline 1 & 15 & 8 & - & - \cr\hline 2 & 20 & 10^5 & \mathbf{A} & -\cr\hline 3 & 20 & 10^5 & \mathbf{B} & - \cr\hline 4 & 15 & 10^3 & - & 1 \cr\hline 5 & 30 & 10^5 & - & 2,3,4 \cr\hline \end{array}$$

• Special property $\mathbf{A}$: it is guaranteed that there exists a node whose degree is $n-1$.
• Special property $\mathbf{B}$: it is guaranteed that $n=2^k-1,k \in \N^*$, and the tree is a perfect binary tree.

For $100\%$ of the testdata: $1 \leq T \leq 5$, $2 \le n \le 10^5$, and the input forms a tree.

Translated by ChatGPT 5