分数: 900 点
问题陈述
有一棵树 N 顶点编号 1 通过 N。 的 i- 第 N-1 边连接顶点 a_i 和 b_i.
最初,每个顶点都是未着色的。
高桥和青木正在玩一个绘制顶点的游戏。在这个游戏中,他们从高桥开始交替执行以下操作:
- 选择尚未绘制的顶点。
- 如果是高桥在执行此操作,则将顶点涂成白色;如果是青木,就把它涂成黑色。
然后,在所有顶点着色后,将发生以下过程:
- 将与黑色顶点相邻的每个白色顶点重新绘制为黑色。
请注意,所有此类白色顶点都会同时重新绘制,而不是一次一个。
如果还剩下一个或多个白色顶点,则高桥获胜;如果所有顶点现在都是黑色,则青木获胜。 假设双方都发挥最佳,确定游戏的获胜者。
约束
- 2 ≤ N ≤ 10^5
- 1 ≤ a_i,b_i ≤ N
- a_i ≠ b_i
- 输入图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
:
a_{N-1} b_{N-1}
输出
打印 First 如果高桥获胜;打印 Second 如果青木获胜。
示例输入 1
3 1 2 2 3
示例输出 1
First
以下是游戏的可能进展:
- 一、高桥画顶点 2 白色。
- 然后,青木绘制顶点 1 黑色。
- 最后,高桥绘制顶点 3 白色。
在这种情况下,顶点的颜色 1, 2 和 3 最后的程序都是黑的、黑的、白的,结果是高桥胜利。
示例输入 2
4 1 2 2 3 2 4
示例输出 2
First
示例输入 3
6 1 2 2 3 3 4 2 5 5 6
示例输出 3
Second