← 返回题目列表

AtCoder · agc014_d

D. 黑白树

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

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