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

Solution (Python):
import sys
input = sys.stdin.readline
import copy
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
point = [[] for _ in range(n+1)]
for l in ab:
  point[l[0]].append(l[1])
  point[l[1]].append(l[0])
adone = set()
bdone = set()
adone.add(1)
bdone.add(n)
da,db = [0]*(n+1),[0]*(n+1)
alist = [1]
blist = [n]
anext,bnext = [],[]
c = 0
while alist:
  c += 1
  for i in alist:
    for j in point[i]:
      if j not in adone:
        adone.add(j)
        anext.append(j)
        da[j] = c
  alist = copy.deepcopy(anext)
  anext = []
c = 0
while blist:
  c += 1
  for i in blist:
    for j in point[i]:
      if j not in bdone:
        bdone.add(j)
        bnext.append(j)
        db[j] = c
  blist = copy.deepcopy(bnext)
  bnext = []
a,b = 0,0
for i in range(1,n+1):
  if da[i] <= db[i]:
    a += 1
  else:
    b += 1
if a > b:
  print("Fennec")
else:
  print("Snuke")

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

from collections import deque
f = deque()
s = deque()
 
f.append(0)
s.append(n-1)
 
f_visit = [-1]*n
s_visit = [-1]*n
f_visit[0] = 0
s_visit[n-1] = 0

def bfs(queue, visit):
  x = queue.popleft()
  for new_x in g[x]:
    if visit[new_x] == -1:
      visit[new_x] = visit[x]+1
      queue.append(new_x)
    else:
      continue

while f:
  bfs(f, f_visit)

while s:
  bfs(s, s_visit)

fp = 0
sp = 0
for i in range(n):
  if f_visit[i] <= s_visit[i]:
    fp += 1
  else:
    sp += 1
if fp <= sp:
  print('Snuke')
else:
  print('Fennec')

Solution (Python):
from heapq import *
n=int(input())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def f(a):
    p=[float("INF")for i in range(n+1)]
    p[a],q=0,[[0,a]]
    while q:
        i,j=heappop(q)
        for w in s[j]:
            if p[w]>i+1:
                p[w]=i+1
                heappush(q,[i+1,w])
    else:
        return p[1:]
s1,t1=f(1),f(n)
a,b=0,0
for i in range(n):
    if s1[i]<=t1[i]:
        a+=1
    else:
        b+=1
print("Fennec" if a>b else "Snuke")

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())

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

qa, qb = [0], [N-1]
sa, sb = 0, 0
visited = [False] * N
visited[0] = visited[N-1] = True

while qa or qb :
    qa_ = []
    while qa :
        cur = qa.pop()
        for nex in v[cur] :
            if not visited[nex] :
                visited[nex] = True
                qa_.append(nex)
                sa += 1
    qa = qa_
    
    qb_ = []
    while qb :
        cur = qb.pop()
        for nex in v[cur] :
            if not visited[nex] :
                visited[nex] = True
                qb_.append(nex)
                sb += 1
    qb = qb_
    
if sa > sb :
    print('Fennec')
else :
    print('Snuke')

Solution (Python):

import sys
import math
from collections import defaultdict, deque
import heapq

INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edge(self, from_, to_, weight=1):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])

    def remove_edge(self, from_, to_):
        for t_, w_ in self.edges[from_]:
            if t_ == to_:
                break
        self.edges[from_].remove([t_, w_])
        self.edges[t_].remove([from_, w_])


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.edges[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


class UnionFind(object):
    """UnionFind木
    """

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, a: "List[int]", b: "List[int]"):
    g = Graph(N)
    for x, y in zip(a, b):
        g.add_edge(x-1, y-1, 1)

    dist, prev = shortestPath(g, 0)

    depth = dist[N-1]
    boundary = N-1
    for _ in range((depth-1) // 2):
        boundary = prev[boundary]
    g.remove_edge(boundary, prev[boundary])
    

    visited = [False]*N
    countA = 0
    q = deque()
    q.append(0)
    while len(q) > 0:
        curr = q.popleft()
        visited[curr] = True
        countA += 1
        for t_, w_ in g.edges[curr]:
            if visited[t_] == False:
                q.append(t_)
    countB = N-countA
    if countA > countB:
        print("Fennec")
    else:
        print("Snuke")
    

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

que = deque([])
que.append((0, 0))

minDist = [float('inf') for _ in range(N)]

while que:
    now, dist = que.popleft()

    if minDist[now] <= dist:
        continue
    minDist[now] = dist

    for to in edges[now]:
        if dist + 1 < minDist[to]:
            que.append((to, dist + 1))

now = N - 1
minPath = [now]
dist = minDist[N - 1]
while dist > 0:
    for back in edges[now]:
        if minDist[back] == dist - 1:
            minPath.append(back)
            dist -= 1
            now = back
            break


edges[minPath[len(minPath) // 2]].remove(minPath[len(minPath) // 2 - 1])
edges[minPath[len(minPath) // 2 - 1]].remove(minPath[len(minPath) // 2])

confilm = [0 for _ in range(N)]
que.clear()
que.append(0)

while que:
    now = que.popleft()

    confilm[now] = 1

    for to in edges[now]:
        if confilm[to] == 0:
            que.append(to)

blackCount = sum(confilm)
witeCount = N - blackCount

if blackCount > witeCount:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import collections

n = int(input())
nxts = collections.defaultdict(list)
for i in range(n - 1):
    a, b = map(int, input().split())
    nxts[a - 1].append(b - 1)
    nxts[b - 1].append(a - 1)

def f(first):
    d = [-1] * n
    d[first] = 0
    stack = [first]
    while stack:
        current = stack.pop()
        for nxt in nxts[current]:
            if d[nxt] == -1:
                d[nxt] = d[current] + 1
                stack.append(nxt)
    return d

d1 = f(0)
d2 = f(n - 1)
c1 = sum(1 for x1, x2 in zip(d1, d2) if x1 <= x2)
c2 = n - c1


if c1 > c2:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import deque

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



def bfs(v):
    dist = [N] * N
    dist[v] = 0
    q = deque()
    q.append(v)
    while q:
        p = q.popleft()
        d = dist[p]
        for e in edges[p]:
            if dist[e] == N:
                dist[e] = d + 1
                q.append(e)
    return dist

fennec = bfs(0)
snuke = bfs(N-1)

cnt = 0
for i in range(N):
    if fennec[i] <= snuke[i]:
        cnt += 1
if 2 * cnt > N:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

que = deque()
que.append((0,0))
c1 = [False]*n
dist1 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist1[v] = min(dist1[v],d)
    if not c1[v]:
        c1[v] = True
        for u in g[v]:
            que.append((d+1,u))
que = deque()
que.append((0,n-1))
c2 = [False]*n
dist2 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist2[v] = min(dist2[v],d)
    if not c2[v]:
        c2[v] = True
        for u in g[v]:
            que.append((d+1,u))

w,b = 0,0
for i in range(n):
    if dist1[i] <= dist2[i]:
        b += 1
    else:
        w += 1
if w < b:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import collections
import sys
sys.setrecursionlimit(10**9)

def dfs(v):
  ret=0
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      ret+=1+dfs(u)
  return ret

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
q=collections.deque()
pn=[-1]*(n+1)
checked=[0]*(n+1)
checked[1]=1
q.append(1)
cnt=0
while cnt!=n-1:
  v=q.popleft()
  for u in g[v]:
    if checked[u]==0:
      cnt+=1
      checked[u]=1
      q.append(u)
      pn[u]=v
path=[n]
while 1:
  tmp=pn[path[-1]]
  if tmp==1:
    break
  path.append(tmp)
path=path[::-1]
l=len(path)
if l==1:
  fg=n
  sg=1
else:
  fg=path[l//2]
  sg=path[l//2-1]
checked=[0]*(n+1)
checked[1]=1
checked[fg]=1
ans1=dfs(1)
ans2=(n-2)-ans1
if ans1>ans2:
  print('Fennec')
else:
  print('Snuke')

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())

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

def dfs(v,p,path):
    for c in g[v]:
        if c == p: continue
        if c == n-1:
            path.append(n-1)
            path.append(v)
            return True
        if dfs(c,v,path):
            path.append(v)
            return True
    return False            

path = []
dfs(0,-1,path)

from collections import deque
q = deque()
memo = [-1]*n 
for i in path[:len(path)//2]:
    memo[i] = 1
    q.append(i)
for i in path[len(path)//2:]:
    memo[i] = 0
    q.append(i)

res = len(path)//2 

while q: 
    v = q.popleft() 
    for c in g[v]:
        if memo[c] != -1: continue
        
        memo[c] = memo[v]
        res += memo[c]
        q.append(c)

if n - res > res: print("Fennec")
else: print("Snuke")

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())

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

"""
def dfs(v,p,path):
    for c in g[v]:
        if c == p: continue
        if c == n-1:
            path.append(n-1)
            path.append(v)
            return True
        if dfs(c,v,path):
            path.append(v)
            return True
    return False            

path = []
dfs(0,-1,path)
path.reverse()
"""


from collections import deque

def bfs(g,root,memo):
    q = deque()
    
    """初期化、キューに入れて使用済みにする"""
    memo[root] = 0
    q.append(root)
    """BFS"""
    while q: 
        v = q.popleft() 
        for c in g[v]:
            if memo[c] != -1: continue 
            
            memo[c] = memo[v] + 1
            q.append(c)

memo0 = [-1]*n
memo1 = [-1]*n

bfs(g,0,memo0)
bfs(g,n-1,memo1)

ans = 0
for i,j in zip(memo0,memo1):
    if i <= j: ans += 1




if ans > n - ans: print("Fennec")
else: print("Snuke")

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())

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

def dfs(v,p,path):
    for c in g[v]:
        if c == p: continue
        if c == n-1:
            path.append(n-1)
            path.append(v)
            return True
        if dfs(c,v,path):
            path.append(v)
            return True
    return False            

path = []
dfs(0,-1,path)
path.reverse()



from collections import deque

q0 = deque()
q1 = deque()
ans = [-1]*n
for i in path[:(1+(len(path)))//2]:
    ans[i] = 0
    q0.append(i)
for i in path[(1+(len(path)))//2:]:
    ans[i] = 1
    q1.append(i)

turn = len(path)&1

while q0 and q1: 
    if turn: v = q1.popleft() 
    else: v = q0.popleft()
    for c in g[v]:
        if ans[c] != -1: continue
        
        ans[c] = turn
        if turn: q1.append(c)
        else: q0.append(c)
    turn ^= 1

if q0: print("Fennec")
else: print("Snuke")

Solution (Python):
n=int(input())
ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
g=[[] for _ in [0]*n]
[g[b-1].append(a-1) for a,b in ab]
[g[a-1].append(b-1) for a,b in ab]

dist_f=[None for _ in [0]*n]
dist_s=[None for _ in [0]*n]
dist_f[0]=0
dist_s[n-1]=0

q=[0]
while q:
    qq=q.pop()
    for i in g[qq]:
        if dist_f[i]==None:
            dist_f[i]=dist_f[qq]+1
            q.append(i)
            
q=[n-1]
while q:
    qq=q.pop()
    for i in g[qq]:
        if dist_s[i]==None:
            dist_s[i]=dist_s[qq]+1
            q.append(i)
            
cnt_f,cnt_s=0,0

for i in range(n):
    if dist_f[i]<=dist_s[i]:
        cnt_f+=1
    else:
        cnt_s+=1
if cnt_f>cnt_s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

E = [{} for _ in [0]*N]
for a,b in AB:
    E[a-1][b-1] = 1
    E[b-1][a-1] = 1

def dist_dfs_tree(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        i = q.pop()
        ci = d[i]
        for j,cj in E[i].items():
            if d[j] !=-1:continue
            d[j] = ci+cj
            q.append(j)
    return d

D1 = dist_dfs_tree(N,E,0)
Dn = dist_dfs_tree(N,E,N-1)
d1n = D1[-1]
for i,dd in enumerate(zip(D1,Dn)):
    if dd[0] == d1n//2 and sum(dd) == d1n:break

di = Dn[i]
for j in E[i]:
    if Dn[j]==di-1:break
E[i].pop(j)
E[j].pop(i)
s1 = sum(s>=0 for s in dist_dfs_tree(N,E,0))
print("Fennec" if s1 > N//2 else "Snuke")

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
from collections import deque
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
check=[False]*n
check[0]=True
check[n-1]=True
f_q=deque([0])
s_q=deque([n-1])
f_c=1
s_c=1
while not (len(f_q)==0 and len(s_q)==0):
    f_n=len(f_q)
    for i in range(f_n):
        now=f_q.popleft()
        for j in G[now]:
            if not check[j]:
                check[j]=True
                f_c+=1
                f_q.append(j)
    s_n=len(s_q)
    for i in range(s_n):
        now=s_q.popleft()
        for j in G[now]:
            if not check[j]:
                check[j]=True
                s_c+=1
                s_q.append(j)
if f_c>s_c:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
N = int(input())
T = [[] for _ in range(N)]


def dfs(k):
    q = [k]
    d = [-1] * N
    d[k] = 0
    while len(q) > 0:
        v = q.pop()
        for i in T[v]:
            if d[i] == -1:
                d[i] = d[v] + 1
                q.append(i)
    return d


def main():
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        T[a].append(b)
        T[b].append(a)
    c = dfs(0)
    d = dfs(N - 1)
    ac = 0
    for x, y in zip(c, d):
        if y >= x:
            ac += 1
    if ac > N // 2:
        print('Fennec')
    else:
        print('Snuke')


main()

Solution (Python):
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            return True
        for i in root[x]:
            if tami(i):
                return True
        else:
            del path[-1]
    return False

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[math.ceil(len(path)/2)-1]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(N)

Snuke = cnt
Fennec = N - Snuke

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

Solution (Python):
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            return True
        for i in root[x]:
            if tami(i):
                return True
        else:
            del path[-1]
    return False

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[math.ceil(len(path)/2)-1]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(N)

Snuke = cnt
Fennec = N - Snuke

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

Solution (Python):
from collections import deque
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    es[a].append(b)
    es[b].append(a)
pre = [None] * (N+1)
pre[1] = 0
dq = deque()
dq.append((0, 1))
while dq:
    d, v = dq.popleft()
    if v == N:
        break
    for u in es[v]:
        if pre[u] == None:
            pre[u] = v
            dq.append((d+1, u))
col = [None] * (N+1)
v = N
sv = [N]
for i in range(d+1):
    if i < d/2:
        col[v] = 0
    else:
        col[v] = 1
    v = pre[v]
    sv.append(v)



bc, wc = 0, 0
for s in sv:
    if s == 0:
        continue
    dq = deque()
    dq.append(s)
    c = 0
    while dq:
        v = dq.popleft()
        c += 1
        for u in es[v]:
            if col[u] == None:
                col[u] = col[s]
                dq.append(u)
    if col[s] == 1:
        bc += c
    else:
        wc += c
if bc > wc:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    global f
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            f = 1
        else:
            for i in root[x]:
                if f == 0:
                    tami(i)
                else:
                    break
            else:
                if f == 0:
                    del path[-1]

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[math.ceil(len(path)/2)-1]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(N)

Snuke = cnt
Fennec = N - Snuke

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

Solution (Python):
import queue

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]

T = {}
for a, b in ab:
  if a not in T:
    T[a] = [b]
  else:
    T[a].append(b)
  if b not in T:
    T[b] = [a]
  else:
    T[b].append(a)

R = [-1] * (N + 1)
q = queue.Queue()
put = q.put
get = q.get
put(1)
R[1] = 1
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] == -1:
        R[i] = R[t] + 1
        put(i)

L = [N]
t = N
while t != 1:
  for i in T[t]:
    if R[i] < R[t]:
      L.append(i)
      t = i
      break

k = L[len(L) // 2 - 1]

cnt = 1
put(k)
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] > R[t]:
        cnt += 1
        put(i)

Ans = ["Fennec", "Snuke"]
print(Ans[cnt >= N - cnt])

Solution (Python):
import sys
input = sys.stdin.readline
 
n = int(input())
connect_list = [[] for i in range(n)]

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

def djkstra(in_connect_list):
    out_parent_list = [-1 for i in range(n)]
    out_shortest_list = [-1 for i in range(n)]
    out_shortest_list[0] = 0
    searching_list = [0]
    
    while searching_list != []:
    
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                if out_shortest_list[j] == -1:
                    out_shortest_list[j] = 1 + out_shortest_list[i]
                    out_parent_list[j] = i
                    new_search_list.append(j)
        searching_list = new_search_list


    return out_shortest_list, out_parent_list

shortest_list, parent_list = djkstra(connect_list)

nto1_list = [n-1]
while nto1_list[-1] != 0:
    nto1_list.append(parent_list[nto1_list[-1]])
nto1_list = list(reversed(nto1_list))


shortest_length = len(nto1_list) 
if shortest_length % 2 == 0:
    p = nto1_list[(shortest_length//2)-1]
    q = nto1_list[shortest_length//2]
else:
    p = nto1_list[shortest_length//2]
    q = nto1_list[(shortest_length//2)+1]

del connect_list[p][connect_list[p].index(q)]
del connect_list[q][connect_list[q].index(p)]


shortest_list, parent_list = djkstra(connect_list)

snu, fen = shortest_list.count(-1), n - shortest_list.count(-1)
if fen > snu:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):


N = int(input())
ab = [[] for i in range(N+1)]
for i in range(N-1):              
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
 
def calc_dist(K):
    
    dist = [-1 for i in range(N+1)]
    dist[K] = 0
 
    
    stack = []
    stack.append(K)
 
    while stack:
        v = stack.pop()
        for nxt in ab[v]:            
            if dist[nxt] == -1:
                dist[nxt] = dist[v] + 1
                stack.append(nxt)
 
    return dist
 
dist1 = calc_dist(1)
distN = calc_dist(N)
 
Fennec = 0
Snuke = 0
for v in range(1,N+1):
    if dist1[v] <= distN[v]:     
        Fennec += 1
    else:
        Snuke += 1
 
if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):


N = int(input())
ab = [[] for i in range(N+1)]
for i in range(N-1):              
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
 
def calc_dist(K):
    
    dist = [-1 for i in range(N+1)]
    dist[K] = 0
 
    
    from collections import deque
    stack = deque()
    stack.append(K)
 
    while stack:
        v = stack.pop()
        for nxt in ab[v]:            
            if dist[nxt] == -1:
                dist[nxt] = dist[v] + 1
                stack.append(nxt)
 
    return dist
 
dist1 = calc_dist(1)
distN = calc_dist(N)
 
Fennec = 0
Snuke = 0
for v in range(1,N+1):
    if dist1[v] <= distN[v]:     
        Fennec += 1
    else:
        Snuke += 1
 
if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import deque
n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d:
        d[b].append(a)
    else:
        d[b]=[a]
f,s=set([1]),set([n])
e=deque([0,1])
u=deque([0,n])
x=0
while 1:
    if len(e)==len(u)==1: break

    if len(e)>0:
        while e[-1]!=0:
            tmp=e.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    f.add(i)
                    e.appendleft(i)
        e.rotate()
    if len(u)>0:
        while u[-1]!=0:
            tmp=u.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    s.add(i)
                    u.appendleft(i)
        u.rotate()

print(["Fennec","Snuke"][len(f)<=len(s)])

Solution (Python):
from collections import deque
n=int(input())
d={}
for i in range(n-1):
    
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d:
        d[b].append(a)
    else:
        d[b]=[a]
f,s=set([1]),set([n])
e=deque([0,1])
u=deque([0,n])
x=0
while 1:
    if len(e)==len(u)==1: break

    if x%2==0 and len(e)>0:
        while e[-1]!=0:
            tmp=e.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    f.add(i)
                    e.appendleft(i)
        e.rotate()
    elif x%2==1 and len(u)>0:
        while u[-1]!=0:
            tmp=u.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    s.add(i)
                    u.appendleft(i)
        u.rotate()
    x+=1
print(["Fennec","Snuke"][len(f)<=len(s)])

Solution (Python):
n = int(input())
edge = [[] for i in range(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)
visited = [0]*n
visited[0] = 1
visited[n-1] = 1
visited_all = [1]*n
nextF = edge[0]
nextS = edge[n-1]
black = 1
white = 1
while visited != visited_all:
    l = []
    for f in nextF:
        if visited[f] == 0:
            visited[f] = 1
            black += 1
            for x in edge[f]:
                l.append(x)
            nextF = l
    l = []
    for s in nextS:
        if visited[s] == 0:
            visited[s] = 1
            white += 1
            for y in edge[s]:
                l.append(y)
            nextS = l
if black > white:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
n=int(input())
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
pre=[None]*(n+1)
pre[1]=1
q=[1]
while len(q)>0:
    t=q.pop()
    for i in edge[t]:
        if(pre[i]==None):
            pre[i]=t
            q.append(i)
route=[n]
t=n
while t!=1:
    t=pre[t]
    route.append(t)
route=route[::-1]
a=route[(len(route)+1)//2-1]
b=route[(len(route)+1)//2]
edge[a].remove(b)
edge[b].remove(a)
def v(s):
    a=1
    q=[s]
    c=[0]*(n+1)
    c[s]=1
    while len(q)>0:
        t=q.pop()
        for i in edge[t]:
            if(c[i]==0):
                c[i]=1
                a+=1
                q.append(i)
    return a
a=v(a)
b=v(b)
if(a>b):
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

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

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

df = dijkstra(g,N,0)
ds = dijkstra(g,N,N-1)

f = 0
for i in range(N):
    if df[i] <= ds[i]:
        f += 1
if f > N-f:
    print('Fennec')
else:
    print('Snuke')