P8347 "Wdoi-6" The Moon on the Other Side

[](https://thwiki.cc/%E5%A4%A7%E7%A9%BA%E9%AD%94%E6%9C%AF_%EF%BD%9E_Magical_Astronomy.) "One of humankind's dreams, traveling on the Moon has finally become possible even for ordinary people!" "Starting next month, travel companies across Japan will begin launching tours." However, on the Moon's surface, there is a barrier that separates the Lunar Capital from a barren, lifeless planet. As long as this barrier exists, people can only see rocks. Also, the cost of lunar travel is definitely not something two college students, Renko and Maribel, can afford. But what they want to explore is the Lunar Capital, wrapped inside the barrier, with its highly developed civilization. This is the Moon on the other side. Maribel saw it: rabbits pounding medicine, and celestial maidens in gorgeous clothes, dancing gracefully in the sky. "Say, Renko. If traveling to the Moon is just too expensive, how about we try thinking of some other way to get to the Moon?"

### 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?

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$.

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}$.

### 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