P14760 [Opoi 2025] CCD’s Game

CCD is playing a game with friends.

The game works as follows: There is a tree with $n$ nodes. Node $1$ is already marked, and all other nodes are unmarked. Two players take turns performing the following operation. A player who cannot make a move loses. > In each move, choose at least one unmarked node that is adjacent to a node that was marked before this move, and mark all chosen nodes. Assuming both players play optimally, determine whether the first player or the second player has a winning strategy.

**This problem contains multiple groups of testdata in a single test file.** The first line contains a positive integer $T$, the number of test cases. For each test case, the first line contains an integer $n$. The next $n-1$ lines each contain two integers $u, v$, representing an edge of the tree.

For each test case, if the first player wins, output `first`; otherwise output `second`. Output each answer on its own line.

### Sample Explanation For the first test case, clearly the first player can mark all nodes in the first move, so the second player loses. For the second test case, the first player can only mark node $2$, and then the second player marks the remaining nodes. --- ### Constraints and Notes **This problem uses bundled tests.** $$ \def\arraystretch{1.2} \begin{array}{|c|c|c|c|} \hline \begin{array}{c} \tt{subtask}\\\hline 1\\\hline 2\\\hline \end{array} & \begin{array}{c} T\\\hline \le 10\\\hline \le 10^{5}\\\hline \end{array} & \begin{array}{c} n\\\hline \le 10\\\hline \le 10^{6}\\\hline \end{array} & \begin{array}{c} \tt{pts}\\\hline 10\\\hline 90\\\hline \end{array} \\\hline \end{array} $$ For all data, $1 \le T \le 10^{5}$, $2 \le n \le 10^{6}$, and $\sum n \le 10^{6}$. **The input is large, so please use a fast input method.** Translated by ChatGPT 5