問題一覧 > 通常問題

No.2841 Leaf Eater

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : milkcoffeemilkcoffee / テスター : とりゐとりゐ 👑 ygussanyygussany
11 ProblemId : 11043 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-08-03 20:24:32

問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点の根付き木があります。頂点 $1$ はこの木の根であり、頂点 $i \ (2 \leq i)$ の親頂点は頂点 $p_i$ です。

これから先手と後手の $2$ 人のプレイヤーが交互に以下の操作を行います。

  • 根付き木の である頂点を $1$ 個以上いくつか選ぶ。選んだ頂点とそれらに繋がる辺を全て削除する。

根付き木の葉とは、根以外の頂点のうち次数が $1$ の頂点のことを言います。

操作が行えなくなったプレイヤーの負けで、もう一方のプレイヤーの勝ちです。両者が自分の勝ちを目指すために最適に行動を行う場合、どちらのプレイヤーが勝つか判定してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えて下さい。

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
ただし、 $case_i$ は $i$ 番目のテストケースを表す。
各テストケースは以下の形式で与えられる。

$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)$
  • 入力はすべて整数
  • $1$ つの入力に含まれるテストケースについて、$N$ の総和は $2 \times 10^5$ 以下

出力

先手が勝つならば First を、後手が勝つならば Second を出力してください。

$i$ 番目のテストケースに対する答えを $i$ 行目に出力してください。

サンプル

サンプル1
入力
3
4
1 1 1
3
1 2
7
1 1 2 2 3 3
出力
First
Second
First

$1$ つ目のテストケースについて、まず先手が頂点 $2,3,4$ を削除したとします。

最後に残った頂点 $1$ は削除できないため、後手は操作が行えません。よって後手の負けとなり、先手が勝ちとなります。


$2$ つ目のテストケースについて、先手は頂点 $3$ を削除するしかありません。

次に後手が頂点 $2$ を削除します。その次に先手は操作が行えないため、後手が勝ちとなります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。