No.2841 Leaf Eater
タグ : / 解いたユーザー数 24
作問者 :
milkcoffee
/ テスター :
とりゐ
Problem Statement
There is a rooted tree with $N$ vertices numbered from $1$ to $N$. Vertex $1$ is the root of this tree, and the parent of vertex $i \ (2 \leq i)$ is vertex $p_i$.
From now on, $2$ players, the first player and the second player, alternately perform the following operation.
- Choose some number of vertices, at least $1$, that are leaves of the rooted tree. Delete all the chosen vertices and all the edges connected to them.
A leaf of a rooted tree is a non-root vertex whose degree is $1$.
The player who cannot perform the operation loses, and the other player wins. Determine which player wins when both players act optimally to win.
You are given $T$ test cases; answer each of them.
Input
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Here, $case_i$ represents the $i$-th test case.Each test case is given in the following format.
$N$ $p_2$ $p_3$ $\ldots$ $p_N$
- $1 \leq T \leq 10^5$
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq p_i < i \ (2 \leq i \leq N)$
- All inputs are integers.
- The sum of $N$ over the test cases contained in $1$ input is at most $2 \times 10^5$.
Output
Print First if the first player wins, and Second if the second player wins.
Print the answer to the $i$-th test case on the $i$-th line.
Sample
Sample 1
Input
3 4 1 1 1 3 1 2 7 1 1 2 2 3 3
Output
First Second First
For the $1$-st test case, suppose that the first player first deletes vertices $2,3,4$.
The remaining vertex $1$ cannot be deleted, so the second player cannot perform the operation. Therefore, the second player loses and the first player wins.
For the $2$-nd test case, the first player has no choice but to delete vertex $3$.
Next, the second player deletes vertex $2$. After that, the first player cannot perform the operation, so the second player wins.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。