Problem:


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



Sample input:
7
3 6
1 2
3 1
7 4
5 7
1 4


Sample output:
Fennec

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



# ここから書き始める
n = int(input())
a = [0 for i in range(n - 1)]
b = [0 for i in range(n - 1)]
for i in range(n - 1):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

tree = [[] for i in range(n)]
for i in range(n - 1):
    tree[a[i]].append(b[i])
    tree[b[i]].append(a[i])

queue1 = deque([[0, 0]])
queue2 = deque([[n - 1, 0]])
visited = [-1 for i in range(n)]
cnt = 0
flag = True
while queue1 or queue2:
    if flag:
        # print("queue1 =", queue1)
        while queue1 and queue1[0][1] == cnt:
            now, cnt2 = queue1.popleft()
            if visited[now] > -1:
                continue
            visited[now] = 0
            for i in tree[now]:
                queue1.append([i, cnt2 + 1])
    else:
        # print("queue2 =", queue2)
        while queue2 and queue2[0][1] == cnt:
            now, cnt2 = queue2.popleft()
            if visited[now] > -1:
                continue
            visited[now] = 1
            for i in tree[now]:
                queue2.append([i, cnt2 + 1])
    if not flag:
        cnt += 1
    flag = not flag

cnt_fennec = visited.count(0)
cnt_snuke = n - cnt_fennec
if cnt_fennec > cnt_snuke:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import itertools
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n=int(input())
edge = [[] for _ in range(n)]
visited = [0]*n
for i in range(n-1):
    a,b=map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
path = []
def dfs(i):
    visited[i]=1
    if(i==n-1):
        return 1
    else:
        for j in edge[i]:
            if(not visited[j]):
                if(dfs(j)):
                    if(i!=0):
                        path.append(i)
                    return i

    return 0



dfs(0)
s = 0
f = 0
visited_new = [-1]*n
path_l = len(path)
for i in range(path_l):
    if(i<(path_l//2)):
        visited_new[path[i]]=1
        s+=1
    else:
        visited_new[path[i]]=2
        f+=1

visited_new[n-1]=3
visited_new[0]=3
que=deque()
que.append(n-1)
while que:
    v=que.popleft()
    for next_v in edge[v]:
        if visited_new[next_v]==2:continue
        if visited_new[next_v]==1 or visited_new[next_v]==-1:
            visited_new[next_v]=3
            que.append(next_v)
            s+=1
que.append(0)
while que:
    v=que.popleft()
    for next_v in edge[v]:
        if visited_new[next_v]==3:continue
        if visited_new[next_v]==2 or visited_new[next_v]==-1:
            visited_new[next_v]=3
            que.append(next_v)
            f+=1
if(f>s):
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import queue

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

from1 = [N] * N
fromN = [N] * N

que = queue.Queue()
que.put((0, 0))
while (not que.empty()):
    vertex, dist = que.get()
    if from1[vertex] != N:
        continue
    from1[vertex] = dist
    for to in edges[vertex]:
        que.put((to, dist + 1))
que.put((N - 1, 0))
while (not que.empty()):
    vertex, dist = que.get()
    if fromN[vertex] != N:
        continue
    fromN[vertex] = dist
    for to in edges[vertex]:
        que.put((to, dist + 1))

black = 0
white = 0
for i in range(N):
    if from1[i] <= fromN[i]:
        black += 1
    else:
        white += 1

print("Fennec" if black > white else "Snuke")

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
g = [[] for i in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

def bfs(src):
    dist = [-1]*n
    dist[src] = 0
    dq = deque([src])
    while dq:
        now = dq.popleft()
        for to in g[now]:
            if dist[to]>=0: continue
            dist[to] = dist[now] + 1
            dq.append(to)
    return dist

df = bfs(0)
ds = bfs(n-1)

fscore = 0
sscore = 0
for f, s in zip(df, ds):
    if f <= s:
        fscore += 1
    else:
        sscore += 1
if fscore > sscore:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import defaultdict

class Tree:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.dist = [-1] * self.n  # 根からの距離
        self.depth = [-1] * self.n  # 根からの深さ(cost=1での距離)
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def set_root(self, root):  # O(n)
        self.root = root
        self.order = [root]
        self.dist[root] = 0
        self.depth[root] = 0
        stack = [root]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.dist[child] = self.dist[v] + self.weight[(v, child)]
                    self.depth[child] = self.depth[v] + 1
                    self.order.append(child)
                    stack.append(child)

    def get_root_path(self, target):
        path = [target]
        v = target
        while v != self.root:
            path.append(self.parent[v])
            v = self.parent[v]
        path.reverse()
        return path

    def get_diameter(self, restore=False):  # double-sweepで求める  O(n)
        u = self.dist.index(max(self.dist))  # 根から一番遠いものを根とし、そこから一番遠いものを見つける
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + self.weight[(v, child)]
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  # [u,...,v]
            return diameter, path
        else:
            return diameter, u, v

    # --- Heavy Light Decomposition --- #

    def heavy_light_decompose(self):  # O(n)
        self.subsize = [1] * self.n  # 部分木の要素数(自分含む)
        self.head = [self.root] * self.n  # 分割された各部分木の先頭
        self.tree_order = [0] * self.n

        # 末端の方から各頂点の部分木の要素数(subsize)を計算していって、
        # heavy-nodeがchildren[v][0]に来るようにする
        for v in reversed(self.order):
            v_kids = self.children[v]  # 名前が長いのでalias
            for i, child in enumerate(v_kids):
                self.subsize[v] += self.subsize[child]
                if self.subsize[child] > self.subsize[v_kids[0]]:
                    v_kids[i], v_kids[0] = v_kids[0], v_kids[i]

        # それぞれのnodeについて分割されたchianの先頭(head)を記録
        # また、DFSの行きがけ順をtree_orderとする headの浅い順でchainが入る
        stack = [self.root]
        tree_label = 0
        while stack:
            v = stack.pop()
            self.tree_order[v] = tree_label
            tree_label += 1
            for child in reversed(self.children[v]):  # スタックを使ったdfsのため逆にしておく
                if child == self.children[v][0]:
                    self.head[child] = self.head[v]
                else:
                    self.head[child] = child  # light-nodeは切り離されたsub-treeのheadになる
                stack.append(child)

    def get_hld_chain_paths(self, u, v):  # (u,v)間の経路をchainごとに返す [l,r)
        ret = []
        while True:
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                ret.append((self.tree_order[u], self.tree_order[v] + 1))
                return ret
            else:
                ret.append((self.tree_order[self.head[v]], self.tree_order[v] + 1))
                v = self.parent[self.head[v]]

    def get_hld_lca(self, u, v):  # Lowest Common Ancestor
        while True:  # head[u] = head[v] になるまで遡る
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.parent[self.head[v]]

    def get_hld_distance(self, u, v):
        return self.dist[u] + self.dist[v] - (2 * self.dist[self.get_hld_lca(u, v)])

    def exist_on_path_hld(self, u, v, x):  # u,v間の最短経路上にxがあるかどうか
        return self.get_hld_distance(u, x) + self.get_hld_distance(x, v) == self.get_hld_distance(u, v)

# ---------------------- #

n = int(input())
edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(n - 1)]
tree = Tree(n, edges)
tree.set_root(0)
tree.heavy_light_decompose()
dist = tree.get_hld_distance(0, n - 1)
snuke = n - 1
for _ in range((dist - 1) // 2):
    snuke = tree.parent[snuke]
snuke_size = tree.subsize[snuke]
fennec_size = n - snuke_size
if snuke_size >= fennec_size:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
n = int(input())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
da = [0]*n
dn = [0]*n
from collections import deque

def bfs(s,d):
  que = deque()
  que.append((s,1))
  chk = [False]*n
  chk[s] = True
  cnt = 1
  while que:
      now,p = que.popleft()
      if cnt == n:
        break
      for i in g[now]:
          if not chk[i]:
            d[i] = p
            chk[i] = True
            cnt += 1
            que.append((i,p+1))
            
bfs(0,da)
bfs(n-1,dn)

f = 0
s = 0
for i in range(n):
  if da[i] <= dn[i]:
    f += 1
  else:
    s += 1
if f > s:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

    n = int(readline())
    edge = defaultdict(list)

    for _ in range(n - 1):
        a, b = map(int, readline().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    que1 = deque()
    que1.append(0)
    que2 = deque()
    que2.append(n - 1)

    df = [-1] * n
    ds = [-1] * n
    df[0] = 0
    ds[n - 1] = 0

    while que1:
        u = que1.popleft()
        for v in edge[u]:
            if df[v] == -1:
                que1.append(v)
                df[v] = df[u] + 1

    while que2:
        u = que2.popleft()
        for v in edge[u]:
            if ds[v] == -1:
                que2.append(v)
                ds[v] = ds[u] + 1

    cf, cs = 0, 0
    for f, s in zip(df, ds):
        if f <= s:
            cf += 1
        else:
            cs += 1

    if cf > cs:
        print("Fennec")
    else:
        print("Snuke")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    a,b=MI()
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
dis1=[-1 for i in range(n)]
dis2=[-1 for i in range(n)]
dis1[0]=0
dis2[-1]=0

def dfs1(x,l):
    for i in tree[x]:
        if dis1[i]>=0:
            continue
        else:
            dis1[i]=l+1
            dfs1(i,l+1)
dfs1(0,0)
#print(dis1)
def dfs2(x,l):
    for i in tree[x]:
        if dis2[i]>=0:
            continue
        else:
            dis2[i]=l+1
            dfs2(i,l+1)
dfs2(n-1,0)
#print(dis2)
count=0
for i in range(n):
    if dis1[i]<=dis2[i]:
        count+=1
    else:
        count-=1
if count<=0:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
def bfs(s):
    visited=[-1]*n
    q=deque([s])
    visited[s]=0
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==-1:
                visited[nx]=visited[x]+1
                q.append(nx)
    return visited
visited1=bfs(0)
visitedn=bfs(n-1)
dist=visited1[n-1]-1
if dist%2:
    for i in range(n):
        if visited1[i]==-(-dist//2) and visitedn[i]==-(-dist//2):
            a=i
        if visited1[i]==-(-dist//2)+1 and visitedn[i]==-(-dist//2)-1:
            b=i
else:
    for i in range(n):
        if visited1[i]==-(-dist//2) and visitedn[i]==-(-dist//2)+1:
            a=i
        if visitedn[i]==-(-dist//2) and visited1[i]==-(-dist//2)+1:
            b=i
edge[a].remove(b)
edge[b].remove(a)
visited=[0]*n
q=deque([0])
visited[0]=1
while q:
    x=q.popleft()
    for nx in edge[x]:
        if visited[nx]==0:
            visited[nx]=1
            q.append(nx)
fs=sum(visited)+(-dist//2)-1
ss=n-sum(visited)-dist//2-1
if dist%2:
    if fs>=ss:
        print("Fennec")
    else:
        print("Snuke")
else:
    if fs>ss:
        print("Fennec")
    else:
        print("Snuke")

Submission status: Accepted

Solution code:
import collections

N = int(input())
tree = [[] for _ in range(N)] #i行目には、i番目のマスと隣り合っているマスの番号が加えられる
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

color = [0] * N #色が塗られていなければ0、黒は1、白は-1
color[0] = 1
color[N-1] = -1
que = collections.deque() #色が塗られたマスの番号を、隣り合うマスが全て塗られるまでここに入れる
que.append(0)
que.append(N-1)
while que: #塗るべきマスがなくなるまで繰り返す
    i = que.popleft() #「左から」が重要 #n回でたどり着けるマスはn回目に全て塗って良い
    for x in tree[i]:
        if color[x] == 0:
            color[x] = color[i]
            que.append(x) #塗ったマスは調べるリストに入れる

if sum(color) > 0: #合計が正、つまり黒が多い場合は先手の勝ち
    print("Fennec")
else: #合計が0でも先手の塗るマスがないため後手の勝ち
    print("Snuke")

Submission status: Accepted

Solution code:
n = int(input())
G = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = tuple(map(lambda x: int(x)-1, input().split()))
    G[a].append(b)
    G[b].append(a)

color = [0] * n
color[0] = 1
color[n-1] = -1
from collections import deque
q = deque([])
q.append(0)
q.append(n-1)
while q:
    node = q.popleft()
    c = color[node]
    for to in G[node]:
        if color[to] == 0:
            color[to] = c
            q.append(to)

cb = color.count(1)
cw = color.count(-1)

if cb > cw:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

# nowからNまでのルート
def router(n, sta, end):
    pos = deque([sta])
    ignore = [0] * n
    path = [0] * n
    path[sta] = -1

    while pos[0] != end:
        u = pos.popleft()
        ignore[u] = 1

        for i in dist[u]:
            if ignore[i] != 1:
                path[i] = u
                pos.append(i)

    route = deque([end])
    while True:
        next = path[route[0]]
        route.appendleft(next)
        if route[0] == sta:
            break

    return list(route)

route = router(N, 0, N - 1)

# NG以外のところで辿れるところの数
def dfs_ter(sta, ng):
    pos = deque([sta])

    ignore = [0] * N
    for i in ng:
        ignore[i] = 1

    cnt = 0
    while len(pos) > 0:
        u = pos.popleft()
        ignore[u] = 1
        cnt += 1
        for i in dist[u]:
            if ignore[i] != 1:
                pos.append(i)

    return cnt

L = len(route)
fen_ter = route[:(L + 2 - 1) // 2]
snu_ter = route[(L + 2 - 1) // 2:]

fen_ans = dfs_ter(0, snu_ter)

if fen_ans > N - fen_ans:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  

s = 0

d1 = [INF]*N
d1[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d1[v] != INF: continue
    d1[v] = d1[u] + 1
    q.append(v)
    
s = N-1
d2 = [INF]*N
d2[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d2[v] != INF: continue
    d2[v] = d2[u] + 1
    q.append(v)
    
ans = 0
for i in range(N):
  if d1[i]<=d2[i]:
    ans += 1

if ans > N//2:
  print("Fennec")
else:
  print("Snuke")