配点 : $900$ 点

問題文

$N$ 頂点からなる木があり、頂点には $1$ から $N$ の番号がついています。 また、 $N-1$ 本の辺の内、$i$ 本目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

はじめ、どの頂点にも色がついていません。

高橋君と青木君は各頂点に色を塗ってゲームをします。ゲームでは高橋君から始めて交互に以下の操作を繰り返します。

• 頂点の中から、まだ色がついていない頂点を一つ選ぶ。
• その後、高橋君ならその頂点を白色に、青木君ならその頂点を黒色に塗る。

次にすべての頂点に色がついた後、高橋君と青木君は以下の手順を一度だけ行います。

• 黒色の頂点に隣接している白色の頂点をすべて黒色に塗りかえる。

ただし、この操作はある頂点から順に操作を行っていくわけではなく、当該頂点すべてに対して同時に行うことに注意してください。

最終的に白色の頂点が残っていれば高橋君の勝ちであり、全て黒色の頂点であれば青木君の勝ちです。 二人が最適に行動したとき、どちらが勝つか求めてください。

制約

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

入力

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

$N$

$a_1$ $b_1$

:

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

出力

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

3
1 2
2 3

First

ゲームの一例を示す。

• 高橋君がまず頂点 $2$ を白色に塗る。
• その後、青木君が頂点 $1$ を黒色に塗る。
• 最後に高橋君が頂点 $3$ を白色に塗る。

このように進んだ場合、最後の操作で頂点 $1,2,3$ の色がそれぞれ黒、黒、白となるので、高橋君の勝ちとなる。

4
1 2
2 3
2 4

First

6
1 2
2 3
3 4
2 5
5 6

Second