AtCoder Grand Contest 014

D - Black and White Tree


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

Submit提出する