题目描述

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

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

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

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

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

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

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

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

输入格式

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

$N$ $a_1$ $b_1$ : $a_{N-1}$ $b_{N-1}$

输出格式

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

题目大意

题意：

• 给出一颗 $N$ 个节点组成的树，每个节点都可以被染成白色或者黑色；

• 有高桥（先手）和青木（后手）两个人————高桥可以把任意一个点染成白色，青木则可以把任意一个点染成黑色，每个点只可染色一次。

• 重复上述操作直到所有点都被染色后，只执行一次执行以下操作：

  1. 把所有青木染成黑色的节点的相邻的白点感染成“次黑色”。

  2. 次黑色不能继续感染白点。

• 若操作完毕后仍还有白点存在，即高桥（先手）胜，反之则青木（后手）胜。

• 现在给出这棵树，问当前此树是先手必胜还是后手必胜。

3
1 2
2 3

First

4
1 2
2 3
2 4

First

6
1 2
2 3
3 4
2 5
5 6

Second

提示

制約

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

Sample Explanation 1

ゲームの一例を示す。 - 高橋君がまず頂点 $2$ を白色に塗る。 - その後、青木君が頂点 $1$ を黒色に塗る。 - 最後に高橋君が頂点 $3$ を白色に塗る。 このように進んだ場合、最後の操作で頂点 $1,2,3$ の色がそれぞれ黒、黒、白となるので、高橋君の勝ちとなる。