分数: 400 点
问题陈述
Fennec 和 Snuke 正在玩棋盘游戏。
板上有 N 单元格编号 1 通过 N,和 N-1 道路,每条道路连接两个小区。细胞 a_i 与单元格相邻 b_i 通过 i第一条路。通过重复行进到相邻单元格,可以从每个其他单元格到达每个单元格。从图论来看,由单元格和道路组成的图就是一棵树。
最初,细胞 1 被漆成黑色,并且 Cell N 被漆成白色。其他细胞尚未着色。 Fennec(第一个)和 Snuke(第二个)交替绘制一个未着色的单元格。 更具体地说,每个玩家轮流执行以下操作:
- Fennec:选择与 黑色 单元格,并对其进行绘制 黑色.
- Snuke:选择与 白色 单元格,并对其进行绘制 白色.
当玩家无法绘制单元格时,她/他就输了。当 Fennec 和 Snuke 发挥最佳状态时确定游戏的胜利者。
约束
- 2 \leq N \leq 10^5
- 1 \leq a_i, b_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
:
a_{N-1} b_{N-1}
输出
如果 Fennec 获胜,则打印 Fennec;如果 Snuke 获胜,则打印 Snuke.
示例输入 1
7 3 6 1 2 3 1 7 4 5 7 1 4
示例输出 1
Fennec
例如,如果 Fennec 首先绘制 Cell 2 黑色,无论斯努克如何走法,她都会获胜。
示例输入 2
4 1 4 4 2 2 3
示例输出 2
Snuke