[AGC014D] Black and White Tree

题意： - 给出一颗 $N$ 个节点组成的树，每个节点都可以被染成白色或者黑色； - 有高桥（先手）和青木（后手）两个人————高桥可以把任意一个点染成白色，青木则可以把任意一个点染成黑色，每个点只可染色一次。 - 重复上述操作直到所有点都被染色后，只执行一次执行以下操作： 1. 把所有青木染成黑色的节点的相邻的白点感染成“次黑色”。 2. 次黑色不能继续感染白点。 - 若操作完毕后仍还有白点存在，即高桥（先手）胜，反之则青木（后手）胜。 - 现在给出这棵树，问当前此树是先手必胜还是后手必胜。

[problemUrl]: https://atcoder.jp/contests/agc014/tasks/agc014_d $ N $ 頂点からなる木があり、頂点には $ 1 $ から $ N $ の番号がついています。 また、 $ N-1 $ 本の辺の内、$ i $ 本目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 はじめ、どの頂点にも色がついていません。 高橋君と青木君は各頂点に色を塗ってゲームをします。ゲームでは高橋君から始めて交互に以下の操作を繰り返します。 - 頂点の中から、まだ色がついていない頂点を一つ選ぶ。 - その後、高橋君ならその頂点を白色に、青木君ならその頂点を黒色に塗る。 次にすべての頂点に色がついた後、高橋君と青木君は以下の手順を一度だけ行います。 - 黒色の頂点に隣接している白色の頂点をすべて黒色に塗りかえる。 ただし、この操作はある頂点から順に操作を行っていくわけではなく、当該頂点すべてに対して同時に行うことに注意してください。 最終的に白色の頂点が残っていれば高橋君の勝ちであり、全て黒色の頂点であれば青木君の勝ちです。 二人が最適に行動したとき、どちらが勝つか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ : $ a_{N-1} $ $ b_{N-1} $

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

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 $ の色がそれぞれ黒、黒、白となるので、高橋君の勝ちとなる。