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):
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(eval(dir()[741]),[Graph(t)]*2,['1']+N)
print('FSennunkeec'[len(t)<sum(x[k]>y[k]for k in x)*2::2])

Solution (Python):
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(vars()[dir()[741]],[Graph(t)]*2,['1']+N)
print('FSennunkeec'[len(t)<sum(x[k]>y[k]for k in x)*2::2])

Solution (Python):
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(vars()[dir()[741]],[Graph(t)]*2,['1']+N)
print('FSennunkeec'[len(x)<=sum(x[k]>y[k]for k in x)*2::2])

Solution (Python):
from networkx import*
N,*t=map(str.split,open(0))
x,y=map(vars()[dir()[741]],[Graph(t)]*2,['1',*N])
print('FSennunkeec'[len(x)<=sum(x[k]>y[k]for k in x)*2::2])

Solution (Python):
from networkx import*
N,*t=map(str.split,open(0))
s=vars()[dir()[741]]
y=s(G:=Graph(t),*N)
print('FSennunkeec'[len(x:=s(G,'1'))<=sum(x[k]>y[k]for k in x)*2::2])

Solution (Python):
from networkx import*
N,*t=map(str.split,open(0))
s=vars()[dir()[741]]
x=s(G:=Graph(t),'1')
y=s(G,*N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=len(x)::2])

Solution (Python):
from networkx import*
N,*t=map(str.split,open(0))
s=shortest_path_length
x=s(G:=Graph(t),'1')
y=s(G,*N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=len(x)::2])

Solution (Python):
from networkx import*
N,*t=map(str.split,open(0))
s=shortest_path_length
x=s(G:=Graph(t),'1')
y=s(G,*N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(*N)::2])

Solution (Python):
from networkx import*
(N,),*t=map(str.split,open(0))
x,y=[shortest_path_length(Graph(t),v)for v in('1',N)]
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Solution (Python):
from networkx import*
(N,),*t=map(str.split,open(0))
s=shortest_path_length
x=s(G:=Graph(t),'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Solution (Python):
from networkx import*
(N,),*t=map(str.split,open(0))
G=Graph(t)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Solution (Python):
from networkx import*
(N,),*t=map(str.split,open(0))
G=Graph()
G.add_edges_from(t)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Solution (Python):
from networkx import*
(N,),*t=[s.split()for s in open(0)]
G=Graph()
G.add_edges_from(t)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Solution (Python):
from networkx import*
N,*t=open(0)
G=Graph()
for s in t:a,b=s.split();G.add_edge(a,b)
s=shortest_path_length
x=s(G,'1')
y=s(G,N[:-1])
print('FSennunkeec'[sum(x[k]>y[k]for k in x)*2>=int(N)::2])

Solution (Python):
from networkx import*
(N,),*t=[s.split()for s in open(0)]
G=Graph()
for a,b in t:G.add_edge(a,b)
s=shortest_path_length
x=s(G,'1')
y=s(G,N)
c=0
for k in y:c+=x[k]>y[k]
print('FSennunkeec'[c*2>=int(N)::2])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n=int(input())
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
def dfs(node,dist,distl):
    distl[node]=dist
    for e in edge[node]:
        if distl[e]==-1:
            dfs(e,dist+1,distl)
dista,distb=[-1]*n,[-1]*n
dfs(0,0,dista)
dfs(n-1,0,distb)
a,b=0,0
for i in range(n):
    if dista[i]<=distb[i]:
        a+=1
    else:
        b+=1
print('Fennec' if a>b else 'Snuke')

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*ab = map(int,read().split())

m = iter(ab)
g = [[] for _ in range(n)]
for a,b in zip(m,m):
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dist(g,start):
    n = len(g)
    dist = [-1]*n
    q = [start]
    dist[start] = 0
    while q:
        v = q.pop()
        for c in g[v]:
            if dist[c] == -1:
                dist[c] = dist[v]+1
                q.append(c)
    return dist        

df = dist(g,0)
ds = dist(g,n-1)


cnt = 0
for i,j in zip(df,ds):
    if i <= j:
        cnt += 1
    else:
        cnt -= 1


if cnt >= 1:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque


def bfs(s, flag):
    if flag:
        global check
    else:
        check = [-1] * (n + 1)
    cnt = 0
    ans = 0
    q = deque([s, cnt])
    while q:
        now = q.popleft()
        cnt = q.popleft()
        check[now] = cnt
        ans += 1
        for next in graph[now]:
            if flag:
                if check[next] > cnt + 1:
                    q.append(next)
                    q.append(cnt + 1)
            else:
                if check[next] == -1:
                    q.append(next)
                    q.append(cnt + 1)
    if flag:
        return ans
    else:
        return check


n = int(readline())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
check = bfs(1, False)
print('Snuke' if bfs(n, True) >= n / 2 else 'Fennec')

Solution (Python):

import sys
from collections import deque


def solve(N: int, path):
    f, s = [1], [N]
    black = set([1])
    white = set([N])
    while True:
        fn = []
        for ff in f:
            for fnext in path[ff]:
                if fnext not in white and fnext not in black:
                    black.add(fnext)
                    fn.append(fnext)
        f = fn
        sn = []
        for ss in s:
            for snext in path[ss]:
                if snext not in white and snext not in black:
                    white.add(snext)
                    sn.append(snext)
        s = sn
        if not s and not f:
            break
    print("Fennec" if len(black) > len(white) else "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))  
    path = {}
    for i in range(N - 1):
        a = int(next(tokens))
        b = int(next(tokens))
        if a in path:
            path[a].append(b)
        else:
            path[a] = [b]
        if b in path:
            path[b].append(a)
        else:
            path[b] = [a]
    solve(N, path)

if __name__ == '__main__':
    main()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)


class Node:

    def __init__(self, num):
        self.num = num
        self.v = 1
        self.parent = 0
        self.deep = None


def LI():
    return list(map(int, input().split()))


N = int(input())
AB = [LI() for _ in range(N - 1)]


link = [[] for _ in range(N + 1)]
for a, b in AB:
    link[a].append(b)
    link[b].append(a)


nodes = [Node(i) for i in range(N + 1)]


def create_tree(parent):
    for child in link[parent.num]:
        if child == parent.parent:
            continue
        node = nodes[child]
        node.parent = parent.num
        node.deep = parent.deep + 1
        create_tree(node)
        parent.v += node.v


def main():
    nodes[1].deep = 1
    create_tree(nodes[1])

    x = (nodes[N].deep - nodes[1].deep - 1) // 2
    v = nodes[N]
    for _ in range(x):
        v = nodes[v.parent]
    
    snuke = v.v
    fennec = N - snuke
    ans = "Fennec" if fennec > snuke else "Snuke"
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
node=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
visited=[False]*n
def dfs(i):
	dis=[-1]*n
	dis[i]=0
	stack=[i]
	while stack:
		p=stack.pop()
		for x in node[p]:
			if dis[x]==-1:
				dis[x]=dis[p]+1
				stack.append(x)
	return dis
d0,dn=dfs(0),dfs(n-1)
cnt=0
for i in range(n):
	if d0[i]>dn[i]:
		cnt+=1
if cnt>=n/2:
	print("Snuke")
else:
	print("Fennec")

Solution (Python):
from collections import deque
n=int(input())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
distfrom1=[-1]*n
distfromn=[-1]*n
distfrom1[0]=0
distfromn[n-1]=0
d=deque([0])
while d:
    v=d.popleft()
    for i in graph[v]:
        if distfrom1[i]!=-1:continue
        distfrom1[i]=distfrom1[v]+1
        d.append(i)
d.append(n-1)
while d:
    v=d.popleft()
    for i in graph[v]:
        if distfromn[i]!=-1:continue
        distfromn[i]=distfromn[v]+1
        d.append(i)
F=0
for i in range(n):
    if distfrom1[i]<=distfromn[i]:F+=1
if F>n-F:print("Fennec")
else:print("Snuke")

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    adj_list = [[] for i in range(n)]
    for i in range(n - 1):
        a1, b1 = map(int, sys.stdin.readline().split())
        adj_list[a1 - 1].append(b1 - 1)
        adj_list[b1 - 1].append(a1 - 1)
    path = list(reversed(dfs(0, -1, adj_list, n)))
    assert len(path) >= 2
    fpath = len(path) - len(path) // 2
    cut = set(path[fpath - 1:fpath + 1])
    f = dfs2(0, -1, adj_list, n, cut)
    s = dfs2(n - 1, -1, adj_list, n, cut)
    assert f + s == n
    print("Fennec" if f > s else "Snuke")

def dfs(now, prev, adj_list, n):
    if now == n - 1:
        return [now]
    for next in adj_list[now]:
        if next == prev:
            continue
        p = dfs(next, now, adj_list, n)
        if p is not None:
            p.append(now)
            return p

def dfs2(now, prev, adj_list, n, cut):
    size = 1
    for next in adj_list[now]:
        if next == prev:
            continue
        if {now, next} == cut:
            continue
        s = dfs2(next, now, adj_list, n, cut)
        size += s
    return size

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N=int(input())
G=[[] for i in range(N)]
F=[0 for i in range(N)]
A=[]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
  A.append([a,b])
  
def dfs(s,R):
  F[s]=1
  
  if s==N-1:
    return [s]
  else:
    for n in G[s]:
      if F[n]==0:
        k=dfs(n,R)
        if len(k)!=0:
          k.append(s)
          return k
     
  return []
  
root=dfs(0,[])

p=root[::-1][len(root)//2+len(root)%2-1]
q=root[::-1][len(root)//2+len(root)%2]

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())

uf = UnionFind(N) 
for i in range(N-1):
  a,b=map(int,A[i])
  if a==p and b==q:
    continue
  if a==q and b==p:
    continue
  uf.union(a, b)

scoreA=uf.size(0)
scoreB=N-scoreA


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

Solution (Python):
n=int(input())
tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)
def dist(k):
  l=[-1]*n
  node=[k]
  while node:
    s=node.pop()
    d=l[s]
    for t in tree[s]:
      if l[t]!=-1:
        continue
      l[t]=d+1
      node.append(t)
  return l
from_fennec=dist(0)
from_snuke=dist(n-1)
res=0
for i,j in zip(from_fennec,from_snuke):
  if i<=j:
    res+=1
  else:
    res-=1
print('Snuke' if res<=0 else 'Fennec')

Solution (Python):

n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
now = [0]
pre = [10**6 for _ in range(n)]
pst = [[] for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        pre[y] = x
        pst[x].append(y)
        now.append(y)

r = 0
z = n-1
while True:
  r += 1
  z = pre[z]
  if z == 0:
    break
z = n-1
for _ in range(r-r//2-1):
  z = pre[z]
cnt = 0
nowz = [z]

while nowz:
  lastz = nowz
  nowz = []
  cnt += len(lastz)
  for x in lastz:
    nowz += pst[x]
  
if cnt >= (n+1)//2:
  print('Snuke')
else:
  print('Fennec')

Solution (Python):
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
root = 1
stack = [root]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
visited[0] = -1
visited[root] = 1
while stack:
  x = stack.pop()
  if x == n:
    break
  for y in graph[x]:
    if visited[y] == 0:
      stack.append(y)
      visited[y] = visited[x]+1
dist = visited[n]-1
way = n
while True:
  if visited[way] == dist//2+2:
    border = way
    break
  for y in graph[way]:
    if visited[y] == visited[way]-1:
      way = y
stack = [1]
visited = [0 for i in range(n+1)]
visited[border] = 1
fen = 0
while stack:
  x = stack.pop()
  fen += 1
  visited[x] = 1
  for y in graph[x]:
    if visited[y] == 0:
      stack.append(y)
snk = n-fen
if fen > snk:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
N, = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)

path = []
stack = [1]
vs = set()
while stack:
    v = stack.pop()
    if v > 0:
        vs.add(v)
        path.append(v)
        for u in G[v]:
            if u in vs:
                continue
            if u == N:
                stack = []
                path.append(u)
                break
            stack += [-v, u]
    else:
        path.pop()

x = path[-(-len(path)//2)]

stack = [1]
vs = set()
while stack:
    v = stack.pop()
    vs.add(v)
    for u in G[v]:
        if u in vs:
            continue
        if u == x:
            continue
        stack.append(u)
x = len(vs)-1
y = N - 2 - x
if x>y:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
 
 
def dist(n, lis):
    lis[n] = 0
    node = [n]
    while node:
        s = node.pop()
        d = lis[s]
        for t in tree[s]:
            if lis[t] != -1:
                continue
            lis[t] = d + 1
            node.append(t)
    return lis
 
 
from_feneck = dist(0, [-1]*N)
from_Snuke = dist(N-1, [-1]*N)
 
feneck = 0
for i,j in zip(from_feneck, from_Snuke):
    if i<=j:
        feneck += 1
    else:
        feneck -= 1
    
if feneck <= 0:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
import math
import sys
sys.setrecursionlimit(1000000)
N = int(input())
graph = {}
SCORE = 0
def dfs(visited,v,depth):
    visited[v] = depth
    for next_v in graph[v]:
        if  visited[next_v]  == -1 :
            dfs(visited,next_v,depth + 1)




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

    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)

vF = [-1] * (N + 1)
vF[1] = 0
dfs(vF,1,0)


vS = [-1] * (N + 1)
vS[N] = 0

dfs(vS,N,0)


fc = 0
sc = 0

for f,s in zip(vF[1:N + 1],vS[1:N + 1]):
    if f <= s:
        fc += 1
    else:
        sc += 1


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

Solution (Python):


from heapq import heappush,heappop
inf=10**10
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i
      cost=1
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
d1=dijkstra(1)
d2=dijkstra(n)
countp=0
counts=0
for i in range(1,n+1):
  if d1[i]>d2[i]:
    counts+=1
  else:
    countp+=1
if countp>counts:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):


import sys
sys.setrecursionlimit(10**8)
from heapq import heappush,heappop
inf=10**10
n=int(input())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
prev=[-1 for i in range(n+1)]
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i
      cost=1
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        prev[t]=v
        heappush(q,[dist[t],t])
  return dist
d=dijkstra(1)
p=[n]
num=n
next=[-1 for i in range(n+1)]
while num!=1:
  num1=prev[num]
  next[num1]=num
  p.append(num1)
  num=num1
countp=[0]
countf=[0]
def dfs(x,y):
  for i in l[x]:
    if prev[x]!=i and next[x]!=i:
      if y==1:
        countp[0]+=1
      else:
        countf[0]+=1
      prev[i]=x
      dfs(i,y) 
p=p[::-1]
num=len(p)
num1=(num-1)//2+1
for i in range(num1):
  countp[0]+=1
  dfs(p[i],1)
for i in range(num1,num):
  countf[0]+=1
  dfs(p[i],0)
if countp[0]>countf[0]:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def dijlstra_heap(N,s,edge):
    d = [float('inf')] * N
    used = [True] * N
    d[s] = 0
    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 main():
    N = int(input())
    edge = [[] for i in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append([1,b])
        edge[b].append([1,a])
    d0 = dijlstra_heap(N,0,edge)
    dn = dijlstra_heap(N,N-1,edge)

    f_cnt = 0
    s_cnt = 0
    for i in range(N):
        if d0[i] <= dn[i]:
            f_cnt += 1
        else:
            s_cnt += 1

    if f_cnt > s_cnt:
        print('Fennec')
    else:
        print('Snuke')


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
tree = [[] for i in range(N+1)]

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

dist_fennec = [100001] * (N+1)
dist_snuke = [100001] * (N+1)
q = [1]
dist_fennec[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist_fennec[next] == 100001:
            dist_fennec[next] = dist_fennec[now] + 1
            q.append(next)

q = [N]
dist_snuke[N] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist_snuke[next] == 100001:
            dist_snuke[next] = dist_snuke[now] + 1
            q.append(next)

fennec, snuke = 0, 0
for i in range(1, N+1):
    if dist_snuke[i] >= dist_fennec[i]:
        fennec += 1
    else:
        snuke += 1

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

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10000000)

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

    
    goal = N-1
    path = [0]
    candidates = [adj[0][:]]
    while path[-1] != goal:
        while not candidates[-1]:
            candidates.pop()
            path.pop()
        u = candidates[-1].pop()
        candidates.append([n for n in adj[u] if n != path[-1]])
        path.append(u)

    black = path[(len(path)-1)//2]
    white = path[(len(path)-1)//2+1]

    
    path = [black]
    candidates = [[n for n in adj[black] if n != white]]
    cnt = 0
    try:
        while True:
            while not candidates[-1]:
                cnt += 1
                candidates.pop()
                path.pop()
            u = candidates[-1].pop()
            candidates.append([n for n in adj[u] if n != path[-1]])
            path.append(u)
    except IndexError:
        pass
    bscore = cnt
    print('Fennec' if bscore*2 > N else 'Snuke')


if __name__ == '__main__':
    solve()

Solution (Python):

import math
import sys
sys.setrecursionlimit(1000000)
N = int(input())
graph = {}
SCORE = 0
def dfs(visted,v,depth):
    visted[v] = depth
    for next_v in graph[v]:
        if  visted[next_v]  == -1 :
            dfs(visted,next_v,depth + 1)




for _ in range(N-1):
    a,b = map(int,input().split(" "))
    if a not in graph:
        graph[a] = [b]
    else:
        graph[a].append(b)

    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)

vF = [-1] * (N + 1)
vF[1] = 0
dfs(vF,1,0)


vS = [-1] * (N + 1)
vS[N] = 0

dfs(vS,N,0)


fc = 0
sc = 0

for f,s in zip(vF[1:N + 1],vS[1:N + 1]):
    if f <= s:
        fc += 1
    else:
        sc += 1


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

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

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

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not x==y: 
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] 
                self.par[x] = y 
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
        
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y) 

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    from collections import defaultdict,deque
    G = defaultdict(list)
    D = []
    for i in range(N-1):
        a, b = map(int,input().split())
        D.append([a,b])
        G[a].append(b)
        G[b].append(a)
    
    que = deque()
    que.append(1)
    visited = {}
    oya = [-1]*(10**5+1)
    while que != deque():
        v = que.pop()
        visited[v] = 1
        if v == N:
            break
        else:
            for i in G[v]:
                if not i in visited:
                    oya[i] = v
                    que.append(i)
    now = N
    path = []
    while now != -1:
        path.append(now)
        now = oya[now]
    path = path[::-1]
    
    L = len(path)
    if L%2==0:
        d1,d2 = path[L//2-1],path[L//2]
    else:
        d1,d2 = path[L//2],path[L//2+1]
    G2 = UnionFind(N)
    
    for i in D:
        a,b = i
        if not {a,b} == {d1,d2}:
            G2.union(a,b)
    one = -G2.par[G2.find(1)]
    enu = -G2.par[G2.find(N)]
    
    if one>enu:
        print("Fennec")
    else:
        print("Snuke")
    

main()

Solution (Python):
from heapq import heappush, heappop
from collections import defaultdict

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

N = int(input())
V = list(range(1, N+1))
E = defaultdict(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a][b] = 1
    E[b][a] = 1
fen = dijkstra(V, E, 1)
sun = dijkstra(V, E, N)
black, white = 0, 0
for v in V:
    if fen[v] <= sun[v]: black += 1
    else: white += 1
print('Fennec' if black > white else 'Snuke')

Solution (Python):
N = int(input())
import sys

sys.setrecursionlimit(N+10)
ab = [[] for _ in range(N)]

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

dF = [0] * N
dS = [0] * N
def dfs(now, d, dlist, visited):
    
    if visited[now] == False:
        dlist[now] = d
        visited[now] = True

        for next in ab[now]:
            dfs(next, d+1, dlist, visited)


vF = [False] * N
dfs(0,0,dF, vF)
vS = [False] * N
dfs(N-1, 0, dS, vS)

cnt_F = 0
cnt_S = 0
for i in range(N):
    if dF[i] <= dS[i]:
        cnt_F += 1
    else:
        cnt_S += 1


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

Solution (Python):

from collections import deque


def bfs(s: int, d: "List[int]") -> None:
    q = deque([s])
    while q:
        v = q.popleft()
        for u in G[v]:
            if not d[u]:
                q.append(u)
                d[u] = d[v] + 1


def main():
    global G, DB, DW
    N, *E = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 2, 2):
        v, u = E[i : i + 2]
        G[v] += [u]
        G[u] += [v]
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    bfs(1, DB), bfs(N, DW)
    b, w = 0, 0
    for i, j in zip(DB[1:], DW[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

def dijkstra(v,s,path):
    inf = float('inf')

    
    d = [inf for i in range(v)]
    d[s] = 0

    
    q = [[0,s]]
    heapq.heapify(q)

    
    
    while q:
        p = heapq.heappop(q)

        
        if d[p[1]]<p[0]:
            continue

        
        for i in range(len(path[p[1]])):
            
            if d[path[p[1]][i][1]] > d[p[1]] + path[p[1]][i][0]:
                d[path[p[1]][i][1]] = d[p[1]]+path[p[1]][i][0]
                heapq.heappush(q,[d[path[p[1]][i][1]], path[p[1]][i][1]])
    return d

n = int(input())

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

d1 = dijkstra(n,0,l)
d2 = dijkstra(n,n-1,l)

a = 0
for i in range(n):
    if d1[i]<=d2[i]:
        a+=1
    else:
        a-=1
print('Fennec' if a>0 else 'Snuke')

Solution (Python):
import heapq

def dijkstra(v,s,path):
    inf = float('inf')

    
    d = [inf for i in range(v)]
    d[s] = 0

    
    q = [[0,s]]
    heapq.heapify(q)

    
    
    while q:
        p = heapq.heappop(q)

        
        if d[p[1]]<p[0]:
            continue

        
        for i in range(len(path[p[1]])):
            
            if d[path[p[1]][i][1]] > d[p[1]] + path[p[1]][i][0]:
                d[path[p[1]][i][1]] = d[p[1]]+path[p[1]][i][0]
                heapq.heappush(q,[d[path[p[1]][i][1]], path[p[1]][i][1]])
    return d

def path_recovery(e,d,path):
    
    route = [e]
    
    a = d[e]
    while a!=0:
        for i in range(len(path[e])):
            if d[path[e][i][1]]+path[e][i][0]==a:
                route.append(path[e][i][1])
                a -= path[e][i][0]
                e = path[e][i][1]
                break
    route.reverse()
    return route

class UnionFind:
    
    def __init__(self, n):
        
        self.par = [-1] * n
        
        self.rank = [0] * n

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

    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x != y:
            
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            
            self.par[x] += self.par[y]
            self.par[y] = x

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

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

n = int(input())

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

d = dijkstra(n,0,l)

p = path_recovery(n-1,d,l)

x = p[(len(p)-1)//2]
y = p[(len(p)-1)//2+1]

for i in range(len(l[x])):
    if l[x][i][1]==y:
        l[x].pop(i)
        break
for i in range(len(l[y])):
    if l[y][i][1]==x:
        l[y].pop(i)
        break

u = UnionFind(n)

for i in range(len(l)):
    for j in range(len(l[i])):
        u.unite(i,l[i][j][1])


if u.size(0)>u.size(n-1):
    print('Fennec')
else:
    print('Snuke')