配点 : $800$ 点

問題文

高橋君と青木君は木を用いてゲームをすることにしました。 ゲームに用いる木は $N$ 頂点からなり、各頂点には $1$ から $N$ の番号が割り振られています。 また、$N-1$ 本の辺のうち、 $i$ 本目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

ゲーム開始時、各頂点にはコインが一枚ずつ置いてあります。 高橋君と青木君は高橋君から始めて以下の操作を交互に行い、操作を行えなくなった方が負けになります。

• コインが置いてある頂点を一つ選び、その頂点 $v$ に置いてあるコインをすべて取り除く。
• その後、木上に残っているコインをすべて、今置いてある頂点に隣接する頂点のうち $v$ に一番近い頂点に移動させる。

つまり、木上にコインが残っていない状態で手番となった人の負けです。 二人が最適に行動したとき、どちらが勝つか求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• 入力で与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $b_1$

$a_2$ $b_2$

:

$a_{N-1}$ $b_{N-1}$

出力

先手の高橋君が勝つなら First を、後手の青木君が勝つなら Second を出力せよ。

3
1 2
2 3

First

ゲームは例えば以下のように進行します。

• 高橋君が頂点 $1$ からコインを取り除く。操作後は、頂点 $1$ に一つ、頂点 $2$ に一つコインがある。
• 青木君が頂点 $2$ からコインを取り除く。操作後は、頂点 $2$ に一つコインがある。
• 高橋君が頂点 $2$ からコインを取り除く。操作後は、木上にコインは残っていない。
• 青木君は木上にコインがない状態で手番となってしまったので、負けとなる。

6
1 2
2 3
2 4
4 6
5 6

Second

7
1 7
7 4
3 4
7 5
6 3
2 1

First