← 返回题目列表

AtCoder · agc033_c

C. 取出硬币

中文机器翻译题面 查看原题

分数: 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