/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
フェネックとすぬけくんがボードゲームで遊んでいます。
このボードゲームには 1 番から N 番までの番号がついた N 個のマスと、マスどうしをつなぐ N-1 本の道が存在しています。 a_i 番のマスと b_i 番のマスは i 番目の道を介して隣り合っています。どの 2 つのマスも隣接するマスをいくつか辿って必ず辿り着くことが可能です。すなわち、グラフ理論の言葉を用いると、マスと道から構成されるグラフは木です。
はじめに 1 番のマスは黒く、N 番のマスは白く塗られています。その他のマスはまだ色が塗られていません。 先手のフェネックと後手のすぬけくんは残りのマスに交互に色を塗ります。 自分の手番において、2 人はそれぞれ以下のような行動を行います。
- フェネック：黒く 塗られたマスに隣接したマスであって、色が塗られていないマスを 1 つ選んで 黒く 塗る。
- すぬけくん：白く 塗られたマスに隣接したマスであって、色が塗られていないマスを 1 つ選んで 白く 塗る。
手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。フェネックとすぬけくんが最適に行動したとき勝者はどちらか判定してください。
制約
- 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 と、すぬけくんならば Snuke と出力せよ。
入力例 1
7 3 6 1 2 3 1 7 4 5 7 1 4
出力例 1
Fennec
例えばフェネックがはじめに 2 番のマスを黒く塗ると、すぬけくんがどのようにマスを白く塗ったとしてもフェネックが勝者となります。
入力例 2
4 1 4 4 2 2 3
出力例 2
Snuke
Score : 400 points
Problem Statement
Fennec and Snuke are playing a board game.
On the board, there are N cells numbered 1 through N, and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.
Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored. Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell. More specifically, each player performs the following action in her/his turn:
- Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.
- Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.
A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq a_i, b_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
:
a_{N-1} b_{N-1}
Output
If Fennec wins, print Fennec; if Snuke wins, print Snuke.
Sample Input 1
7 3 6 1 2 3 1 7 4 5 7 1 4
Sample Output 1
Fennec
For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.
Sample Input 2
4 1 4 4 2 2 3
Sample Output 2
Snuke