Background

CCD is playing a game with friends.

Problem Description

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.

Input Format

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.

Output Format

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

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

first
second

Hint

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