SZ#G6MT16. 【GESP强化 六级】黑白争夺

提交1 通过1
通过率100%
时间限制2000ms
内存限制256MiB

题目描述

有一棵包含 NN 个顶点的树,顶点编号为 11NN。开始时,小珅把顶点 11 染成黑色,小泽把顶点 NN 染成白色,其余顶点尚未染色。

接下来两人轮流行动,小珅先手:

  • 小珅每次选择一个与某个黑色顶点相邻的未染色顶点,把它染成黑色;
  • 小泽每次选择一个与某个白色顶点相邻的未染色顶点,把它染成白色。

当所有顶点都染色后游戏结束。如果黑色顶点数量多于白色顶点数量,小珅获胜;否则小泽获胜。两人都会采用使自己获胜的最优策略。请判断最后的获胜者。

输入格式

第一行输入一个整数 NN,表示树的顶点数量。

接下来 N1N-1 行,每行输入两个整数 aia_ibib_i,表示顶点 aia_i 与顶点 bib_i 之间有一条边。

输出格式

如果小珅获胜,输出 Fennec;否则输出 Snuke

4
2 1
3 1
4 3
Fennec
2
2 1
Snuke
10
6 4
1 4
10 2
3 1
1 2
9 5
8 4
5 1
6 7
Fennec

数据范围与约定

  • 2N1052\le N\le10^5
  • 输入图是一棵树