/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
N 頂点からなる木があり、頂点には 1 から N の番号がついています。 また、 N-1 本の辺の内、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。
はじめ、どの頂点にも色がついていません。
高橋君と青木君は各頂点に色を塗ってゲームをします。ゲームでは高橋君から始めて交互に以下の操作を繰り返します。
- 頂点の中から、まだ色がついていない頂点を一つ選ぶ。
- その後、高橋君ならその頂点を白色に、青木君ならその頂点を黒色に塗る。
次にすべての頂点に色がついた後、高橋君と青木君は以下の手順を一度だけ行います。
- 黒色の頂点に隣接している白色の頂点をすべて黒色に塗りかえる。
ただし、この操作はある頂点から順に操作を行っていくわけではなく、当該頂点すべてに対して同時に行うことに注意してください。
最終的に白色の頂点が残っていれば高橋君の勝ちであり、全て黒色の頂点であれば青木君の勝ちです。 二人が最適に行動したとき、どちらが勝つか求めてください。
制約
- 2 ≦ N ≦ 10^5
- 1 ≦ a_i,b_i ≦ N
- a_i ≠ b_i
- 入力で与えられるグラフは木である。
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
:
a_{N-1} b_{N-1}
出力
先手の高橋君が勝つなら First を、後手の青木君が勝つなら Second を出力せよ。
入力例 1
3 1 2 2 3
出力例 1
First
ゲームの一例を示す。
- 高橋君がまず頂点 2 を白色に塗る。
- その後、青木君が頂点 1 を黒色に塗る。
- 最後に高橋君が頂点 3 を白色に塗る。
このように進んだ場合、最後の操作で頂点 1,2,3 の色がそれぞれ黒、黒、白となるので、高橋君の勝ちとなる。
入力例 2
4 1 2 2 3 2 4
出力例 2
First
入力例 3
6 1 2 2 3 3 4 2 5 5 6
出力例 3
Second
Score : 900 points
Problem Statement
There is a tree with N vertices numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.
Initially, each vertex is uncolored.
Takahashi and Aoki is playing a game by painting the vertices. In this game, they alternately perform the following operation, starting from Takahashi:
- Select a vertex that is not painted yet.
- If it is Takahashi who is performing this operation, paint the vertex white; paint it black if it is Aoki.
Then, after all the vertices are colored, the following procedure takes place:
- Repaint every white vertex that is adjacent to a black vertex, in black.
Note that all such white vertices are repainted simultaneously, not one at a time.
If there are still one or more white vertices remaining, Takahashi wins; if all the vertices are now black, Aoki wins. Determine the winner of the game, assuming that both persons play optimally.
Constraints
- 2 ≤ N ≤ 10^5
- 1 ≤ a_i,b_i ≤ N
- a_i ≠ b_i
- The input graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
:
a_{N-1} b_{N-1}
Output
Print First if Takahashi wins; print Second if Aoki wins.
Sample Input 1
3 1 2 2 3
Sample Output 1
First
Below is a possible progress of the game:
- First, Takahashi paint vertex 2 white.
- Then, Aoki paint vertex 1 black.
- Lastly, Takahashi paint vertex 3 white.
In this case, the colors of vertices 1, 2 and 3 after the final procedure are black, black and white, resulting in Takahashi's victory.
Sample Input 2
4 1 2 2 3 2 4
Sample Output 2
First
Sample Input 3
6 1 2 2 3 3 4 2 5 5 6
Sample Output 3
Second