問題一覧 > 通常問題

No.2841 Leaf Eater

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : milkcoffee / テスター : とりゐ ygussany
お気に入りにしたユーザー ProblemId : 11043 / 自分の提出
問題文最終更新日: 2024-08-03 20:24:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 440 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。