Score : 900 points
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:
Then, after all the vertices are colored, the following procedure takes place:
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.
Input is given from Standard Input in the following format:
N a_1 b_1 : a_{N-1} b_{N-1}
Print First
if Takahashi wins; print Second
if Aoki wins.
3 1 2 2 3
First
Below is a possible progress of the game:
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.
4 1 2 2 3 2 4
First
6 1 2 2 3 3 4 2 5 5 6
Second