题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。另外，$N-1$ 条边中，第 $i$ 条边连接顶点 $a_i$ 与顶点 $b_i$。

初始时，所有顶点均未被染色。

高桥君和青木君轮流对每个顶点进行染色操作，游戏规则如下：

• 由高桥君先手，轮流进行如下操作：
  • 从尚未被染色的顶点中选择一个。
  • 若为高桥君操作，将该顶点染为白色；若为青木君操作，将该顶点染为黑色。

当所有顶点都被染色后，两人紧接着再进行一次如下操作：

• 将所有与黑色顶点相邻的白色顶点同时变为黑色。

请注意，这一步对所有满足条件的顶点是同时进行的，而不是依次逐个执行。

如果最后仍存在白色顶点，则高桥君获胜；否则全为黑色顶点时，青木君获胜。请判断在两人都采取最优策略的情况下，哪一方会获胜。

输入格式

输入以下格式，由标准输入读入。

$N$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{N-1}\ b_{N-1}$

输出格式

如果先手的高桥君获胜，输出 First；如果后手的青木君获胜，输出 Second。

样例 1

输入

3
1 2
2 3

输出

First

样例 2

输入

4
1 2
2 3
2 4

输出

First

样例 3

输入

6
1 2
2 3
3 4
2 5
5 6

输出

Second

说明/提示

限制条件

• $2\leq N\leq 10^5$
• $1\leq a_i,b_i\leq N$
• $a_i\neq b_i$
• 输入保证构成一棵树

样例说明 1

给出一种可能的游戏过程如下：

• 高桥君首先将顶点 $2$ 染为白色。
• 然后青木君将顶点 $1$ 染为黑色。
• 最后高桥君将顶点 $3$ 染为白色。

按照这样的流程，执行最后的染色操作后，顶点 $1,2,3$ 的颜色分别为黑、黑、白，因此高桥君获胜。

由 ChatGPT 5 翻译