[ABC067D] Fennec VS. Snuke
题意翻译
## 题目描述
$Fennec$ 和 $Snuke$ 正在玩棋盘游戏。
在这个游戏中,有 $n$ 个格子和 $n-1$ 条道路, 编号为 $a_i$ 和 $b_i$ 的格子通过第 $i$ 条边相连。这些格子和边组成了一棵树。
第 $1$ 个格子是黑色,第 $n$ 个格子是白色,其他格子没有颜色。先手 $Fennec$ 和后手 $Snuke$ 交替给格子涂色,两人依次执行以下操作:
$Fennec$:将一个与黑色格子相邻且未被涂色的格子涂成黑色。
$Snuke$:将一个与白色格子相邻且未被涂色的格子涂成白色。
如果当前行动的玩家无法涂色,他将输掉游戏。请你写一个程序,判断当 $Fennec$ 和 $Snuke$ 都采取最佳策略时,谁能获胜。
## 输入格式
第一行一个整数 $n\ \ (2 ≤n≤1e5)$
接下来 $n-1$行,每行两个整数 $a_i$ 和 $b_i$,表示 $a_i$ 和 $b_i$ 间有一条边 $(1≤a_i ,b_i ≤n)$
## 输出格式
若 Fennec 获胜,输出“Fennec”,否则输出“Snuke”(不包含引号)
题目描述
[problemUrl]: https://atcoder.jp/contests/abc067/tasks/arc078_b
フェネックとすぬけくんがボードゲームで遊んでいます。
このボードゲームには $ 1 $ 番から $ N $ 番までの番号がついた $ N $ 個のマスと、マスどうしをつなぐ $ N-1 $ 本の道が存在しています。 $ a_i $ 番のマスと $ b_i $ 番のマスは $ i $ 番目の道を介して隣り合っています。どの $ 2 $ つのマスも隣接するマスをいくつか辿って必ず辿り着くことが可能です。すなわち、グラフ理論の言葉を用いると、マスと道から構成されるグラフは木です。
はじめに $ 1 $ 番のマスは黒く、$ N $ 番のマスは白く塗られています。その他のマスはまだ色が塗られていません。 先手のフェネックと後手のすぬけくんは残りのマスに交互に色を塗ります。 自分の手番において、$ 2 $ 人はそれぞれ以下のような行動を行います。
- フェネック:**黒く** 塗られたマスに隣接したマスであって、色が塗られていないマスを $ 1 $ つ選んで **黒く** 塗る。
- すぬけくん:**白く** 塗られたマスに隣接したマスであって、色が塗られていないマスを $ 1 $ つ選んで **白く** 塗る。
手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。フェネックとすぬけくんが最適に行動したとき勝者はどちらか判定してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ b_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $
输出格式
勝者がフェネックならば `Fennec` と、すぬけくんならば `Snuke` と出力せよ。
输入输出样例
输入样例 #1
7
3 6
1 2
3 1
7 4
5 7
1 4
输出样例 #1
Fennec
输入样例 #2
4
1 4
4 2
2 3
输出样例 #2
Snuke
说明
### 制約
- $ 2\ \leq\ N\ \leq\ 10^5 $
- $ 1\ \leq\ a_i,\ b_i\ \leq\ N $
- 与えられるグラフは木
### Sample Explanation 1
例えばフェネックがはじめに $ 2 $ 番のマスを黒く塗ると、すぬけくんがどのようにマスを白く塗ったとしてもフェネックが勝者となります。