/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
高橋君と青木君は木を用いてゲームをすることにしました。 ゲームに用いる木は N 頂点からなり、各頂点には 1 から N の番号が割り振られています。 また、N-1 本の辺のうち、 i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。
ゲーム開始時、各頂点にはコインが一枚ずつ置いてあります。 高橋君と青木君は高橋君から始めて以下の操作を交互に行い、操作を行えなくなった方が負けになります。
- コインが置いてある頂点を一つ選び、その頂点 v に置いてあるコインをすべて取り除く。
- その後、木上に残っているコインをすべて、今置いてある頂点に隣接する頂点のうち v に一番近い頂点に移動させる。
つまり、木上にコインが残っていない状態で手番となった人の負けです。 二人が最適に行動したとき、どちらが勝つか求めてください。
制約
- 1 ≦ N ≦ 2 \times 10^5
- 1 ≦ a_i, b_i ≦ N
- a_i \neq b_i
- 入力で与えられるグラフは木である。
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
出力
先手の高橋君が勝つなら First を、後手の青木君が勝つなら Second を出力せよ。
入力例 1
3 1 2 2 3
出力例 1
First
ゲームは例えば以下のように進行します。
- 高橋君が頂点 1 からコインを取り除く。操作後は、頂点 1 に一つ、頂点 2 に一つコインがある。
- 青木君が頂点 2 からコインを取り除く。操作後は、頂点 2 に一つコインがある。
- 高橋君が頂点 2 からコインを取り除く。操作後は、木上にコインは残っていない。
- 青木君は木上にコインがない状態で手番となってしまったので、負けとなる。
入力例 2
6 1 2 2 3 2 4 4 6 5 6
出力例 2
Second
入力例 3
7 1 7 7 4 3 4 7 5 6 3 2 1
出力例 3
First
Score : 800 points
Problem Statement
Takahashi and Aoki will play a game on a tree. The tree has N vertices numbered 1 to N, and the i-th of the N-1 edges connects Vertex a_i and Vertex b_i.
At the beginning of the game, each vertex contains a coin. Starting from Takahashi, he and Aoki will alternately perform the following operation:
- Choose a vertex v that contains one or more coins, and remove all the coins from v.
- Then, move each coin remaining on the tree to the vertex that is nearest to v among the adjacent vertices of the coin's current vertex.
The player who becomes unable to play, loses the game. That is, the player who takes his turn when there is no coin remaining on the tree, loses the game. Determine the winner of the game when both players play optimally.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq a_i, b_i \leq N
- a_i \neq b_i
- The graph given as input is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
Output
Print First if Takahashi will win, and print Second if Aoki will win.
Sample Input 1
3 1 2 2 3
Sample Output 1
First
Here is one possible progress of the game:
- Takahashi removes the coin from Vertex 1. Now, Vertex 1 and Vertex 2 contain one coin each.
- Aoki removes the coin from Vertex 2. Now, Vertex 2 contains one coin.
- Takahashi removes the coin from Vertex 2. Now, there is no coin remaining on the tree.
- Aoki takes his turn when there is no coin on the tree and loses.
Sample Input 2
6 1 2 2 3 2 4 4 6 5 6
Sample Output 2
Second
Sample Input 3
7 1 7 7 4 3 4 7 5 6 3 2 1
Sample Output 3
First