P14760 [Opoi 2025] CCD 的游戏

CCD 在和小伙伴玩游戏。

游戏是这样的： 有一棵 $n$ 个节点的树，其中 $1$ 号节点已被标记，其余点均未被标记。现在有两个人，轮流进行如下操作，不能操作就输了： > 每一次操作，选择至少一个未标记的且与这一操作之前已标记点相邻的点，将这些点标记。 假如两个人都按最聪明的方法来选，请问是先手还是后手有必胜策略？

**本题单个测试点内含有多组测试数据。** 第一行一个正整数 $T$，表示测试数据组数。 对于每组测试数据，第一行一个整数 $n$。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条树上的边。

对于每组数据，如果先手必胜，输出 `first`，否则输出 `second`，换行分隔。

### 样例解释 对于第一组数据，显然先手第一轮即可标记完所有点，后手就输了。 对于第二组数据，先手只能标记二号点，然后后手标记剩下的点。 --- ### 数据范围与约定 **本题采用捆绑测试。** $$ \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} $$ 对于所有数据，$1\le T \le 10^5$，$2\le n \le 10^6$，$\sum n \le 10^6$。 **输入数据较大，请使用较快的读入方式。**