分数: 800 点
问题陈述
高桥和青木将在树上玩游戏。 这棵树有 N 顶点编号 1 to N,以及 i- 第 N-1 边连接顶点 a_i 和顶点 b_i.
游戏开始时,每个顶点都包含一枚硬币。 从高桥开始,他和青木将交替执行以下操作:
- 选择一个顶点 v 包含一枚或多枚硬币,并从其中移除所有硬币 v.
- 然后,将树上剩余的每个硬币移动到最接近的顶点 v 硬币当前顶点的相邻顶点之间。
无法玩游戏的玩家输掉游戏。 也就是说,当树上没有剩余硬币时轮到的玩家输掉游戏。 当双方都发挥最佳状态时确定游戏的获胜者。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq a_i, b_i \leq 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
这是游戏的一个可能的进展:
- Takahashi 从 Vertex 中取出硬币 1。现在,顶点 1 和顶点 2 每个包含一枚硬币。
- Aoki 从 Vertex 中取出硬币 2。现在,顶点 2 包含一枚硬币。
- Takahashi 从 Vertex 中取出硬币 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