← 返回题目列表

AtCoder · arc078_b

D. 耳廓狐VS。潜伏

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

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