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 collections import deque
import sys
sys.setrecursionlimit(1000000000)
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)
que = deque([0])
parent = [-1]*N
parent[0] = 0
while que:
    cur = que.pop()
    for nxt in edges[cur]:
        if parent[nxt] < 0:
            parent[nxt] = cur
            que.append(nxt)
cur = N-1
route = [N-1]
while cur:
    cur = parent[cur]
    route.append(cur)
i = len(route)//2
a, b = route[i-1:i+1]
edges[a].remove(b)
edges[b].remove(a)
que = deque([0])
flag = [True]*N
score = 0
flag[0] = False
while que:
    v0 = que.pop()
    score+=1
    for v in edges[v0]:
        if flag[v]:
            que.append(v)
            flag[v] = False
if score>N//2:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import deque
def F(m):
	q=deque([m])
	d=[-1]*n
	while q:
		cur=q.popleft()
		for nxt in G[cur]:
			if d[nxt]<0:
				q.append(nxt)
				d[nxt]=d[cur]+1
	return d
def solve():
	global n,G
	n,*L=map(int,open(0).read().split())
	G=[[]for _ in range(n)]
	for a,b in zip(*[iter(L)]*2):
		G[a-1]+=[b-1]
		G[b-1]+=[a-1]
	print("FSennunkeec"[sum(i>j or-1 for i,j in zip(F(0),F(n-1)))>=0::2])
if __name__=="__main__":solve()

Solution (Python):
from collections import*
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
def F(m):
	q=deque([m])
	d=[-1]*n
	while q:
		cur=q.popleft()
		for nxt in G[cur]:
			if d[nxt]<0:
				q.append(nxt)
				d[nxt]=d[cur]+1
	return d
print("FSennunkeec"[sum(i>j or-1 for i,j in zip(F(0),F(n-1)))>=0::2])

Solution (Python):
from collections import deque
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n;db[0]=0
dw=[-1]*n;dw[-1]=0
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=deque([0])
while q:
	cur=q.popleft()
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append(nxt)
			db[nxt]=db[cur]+1
q=deque([n-1])
while q:
	cur=q.popleft()
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append(nxt)
			dw[nxt]=dw[cur]+1
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:print("Snuke")
else:print("Fennec")

Solution (Python):
from collections import deque
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n
dw=[-1]*n
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=deque([(0,0)])
while q:
	cur,d=q.popleft()
	db[cur]=d
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append((nxt,d+1))
q=deque([(n-1,0)])
while q:
	cur,d=q.popleft()
	dw[cur]=d
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append((nxt,d+1))
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:
	print("Snuke")
else:
	print("Fennec")

Solution (Python):
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n;db[0]=0
dw=[-1]*n;dw[-1]=0
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=[0]
while q:
	cur=q.pop(0)
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append(nxt)
			db[nxt]=db[cur]+1
q=[n-1]
while q:
	cur=q.pop(0)
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append(nxt)
			dw[nxt]=dw[cur]+1
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:print("Snuke")
else:print("Fennec")

Solution (Python):
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n
dw=[-1]*n
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=[(0,0)]
while q:
	cur,d=q.pop(0)
	db[cur]=d
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append((nxt,d+1))
q=[(n-1,0)]
while q:
	cur,d=q.pop(0)
	dw[cur]=d
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append((nxt,d+1))
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:
	print("Snuke")
else:
	print("Fennec")

Solution (Python):
from collections import deque

N = int(input())

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

alis = [""] * N
alis[0] = 0

Q = deque([])
Q.append(0)

while len(Q) > 0:

    now = Q.pop()

    if now not in dic:
        continue

    for b in dic[now]:

        if alis[b] == "":
            alis[b] = alis[now] + 1

            Q.append(b)

blis = [""] * N
blis[N-1] = 0

Q = deque([])
Q.append(N-1)

while len(Q) > 0:

    now = Q.pop()

    if now not in dic:
        continue

    for b in dic[now]:

        if blis[b] == "":
            blis[b] = blis[now] + 1

            Q.append(b)

F = 0
S = 0

for i in range(N):
    if alis[i] <= blis[i]:
        F += 1
    else:
        S += 1

if F <= S:
    print ("Snuke")
else:
    print ("Fennec")

Solution (Python):

from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)

def set_distance(t, l, now, prev, pos):
    d = l[now][pos]

    for child in t[now]:
        if child == prev:
            continue
        l[child][pos] = d+1
        set_distance(t, l, child, now, pos)


n = int(input())
t = defaultdict(list)
for _ in range(n-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    t[a].append(b)
    t[b].append(a)


l = [[n, n] for _ in range(n)]
l[0][0] = 0
l[n-1][1] = 0

set_distance(t, l, 0, -1, 0)
set_distance(t, l, n-1, -1, 1)

f, s = 0, 0
for df, ds in l:
    if df <= ds:
        f += 1
    else:
        s += 1

if f > s:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
N = int(input())
import sys
sys.setrecursionlimit(N+10)

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

"""
相手の取れるマス目を減らすようにとるとよい
相手よりそのマスに近ければそのマスを取得できる
フェネックくん、すぬけ君について初期地点からそれぞれへの距離が必要
"""
def solve(now, depth, depth_list, es, visited):
    visited[now] = True
    depth_list[now] = depth
    for next in es[now]:
        if visited[next] == False:            
            solve(next, depth+1, depth_list, es, visited)

depth_list_F = [0] * N
visited_F = [False] * N
solve(0, 0, depth_list_F, es, visited_F)

depth_list_S = [0] * N
visited_S = [False] * N
solve(N-1, 0, depth_list_S, es, visited_S)

cnt_F = cnt_S = 0
for f,s in zip(depth_list_F, depth_list_S):
    if f <= s:
        cnt_F += 1 
    else:
        cnt_S += 1

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)

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)
prevs=[0]*N
def dfs(prev,curr):
    prevs[curr]=prev
    if curr == N-1:
        return
    for c in edges[curr]:
        if c!=prev:
            dfs(curr,c)
dfs(-1,0)
paths=[N-1]
tmp=N-1
while tmp!=0:
    paths.append(prevs[tmp])
    tmp=prevs[tmp]
paths=paths[::-1]

points=[0,0]
def count(prev,curr,player):
    points[player]+=1
    for c in edges[curr]:
        if c!=prev:
            count(curr,c,player)

nf = (len(paths)+1)//2
f,s = paths[nf-1],paths[nf]
count(s,f,0)
count(f,s,1)
pf,ps=points
print("Fennec" if pf>ps else "Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

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

V = [-1 for _ in range(N)]
def dfs(u,count):
  V[u] = count
  for v in E[u]:
    if V[v] == -1:
      dfs(v,count+1)
dfs(0,0)
Path = []
v = N-1
while (v != 0):
  Path.append(v)
  for u in E[v]:
    if V[u] == V[v] -1:
      v = u
Path.append(0)


def dfs2(u):
  visited[u] = True
  res = 1
  for v in E[u]:
    if not visited[v]:
      res += dfs2(v)
  return res
visited = [False for _ in range(N)]
for i in Path:
  visited[i] = True
fennec = 0
for i in range((len(Path)+1)//2):
  fennec += dfs2(Path[-i-1])
snuke = 0
for i in range(len(Path)//2):
  snuke += dfs2(Path[i])

print('Fennec' if fennec > snuke else 'Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

N = int(input())

G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    
    G[a].append(b)
    G[b].append(a)


def dfs(v, p, c, distance):  
    distance[v] = c
    for nv in G[v]:
        if visited[nv] is False:
            if nv == p:
                continue
            dfs(nv, v, c+1, distance)
    return


distance_f = [-1]*(N+1)
visited = [False] * (N+1)
dfs(1, -1, 0, distance_f)

distance_s = [-1]*(N+1)
visited = [False] * (N+1)
dfs(N, -1, 0, distance_s)




c = 0
for i in range(2, N):
    if distance_f[i] <= distance_s[i]:
        c += 1
    elif distance_f[i] > distance_s[i]:
        c -= 1

if c > 0:
    print('Fennec')
elif c <= 0:
    print('Snuke')

Solution (Python):
N = int(input())
E = [set() for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  E[a].add(b)
  E[b].add(a)
DF = [-1]*N
q = [0]
DF[0] = 0
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if DF[n] < 0:
      DF[n] = DF[c]+1
      q.append(n)

DS = [-1]*N
q = [N-1]
DS[N-1] = 0
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if DS[n] < 0:
      DS[n] = DS[c]+1
      q.append(n)
NF = 0
NS = 0
for i in range(N):
  if DF[i] <= DS[i]:
    NF += 1
  else:
    NS += 1

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

Solution (Python):
import collections
def main():

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

    cur1 = [1]
    cur2 = [N]
    visited1 = {1}
    visited2 = {N}

    while cur1 or cur2:
        temp1, temp2 = [], []
        for a in cur1:
            for b in graph[a]:
                if b not in visited1 and b not in visited2:
                    temp1.append(b)
                    visited1.add(b)
        cur1 = temp1

        for a in cur2:
            for b in graph[a]:
                if b not in visited1 and b not in visited2:
                    temp2.append(b)
                    visited2.add(b)
        cur2 = temp2

    if len(visited1) > len(visited2):
        return "Fennec"
    return "Snuke"


if __name__ == '__main__':
    print(main())

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):
from collections import*
N,*AB=map(int,open(0).read().split())
E=[[]for _ in range(N+1)]
for a,b in zip(*[iter(AB)]*2):
	E[a]+=[b]
	E[b]+=[a]
def g(s):
	Q=deque([s]);d=[0]*(N+1)
	while Q:
		v=Q.popleft()
		for u in E[v]:
			if d[u]==0:
				Q+=[u]
				d[u]=d[v]+1
	return d[1:]
print("SFneunknee c"[0<sum(1 if f<=s else-1 for f,s in zip(g(1),g(N)))::2])

Solution (Python):
from collections import deque
N,*AB=map(int,open(0).read().split())
E=[[]for _ in range(N+1)]
for a,b in zip(*[iter(AB)]*2):
	E[a].append(b)
	E[b].append(a)
def g(s):
	Q=deque([s])
	d=[0]*(N+1)
	while Q:
		v=Q.popleft()
		for u in E[v]:
			if d[u]==0:
				Q.append(u)
				d[u]=d[v]+1
	return d[1:]
print("Fennec"if 0<sum(1 if f<=s else-1 for f,s in zip(g(1),g(N))) else"Snuke")

Solution (Python):
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

def get_dist(src):
    Q = deque([src])
    dist = [0] * (N + 1)
    while Q:
        v =  Q.popleft()
        for u in E[v]:
            if dist[u] == 0:
                Q.append(u)
                dist[u] = dist[v] + 1
    return dist[1:]

F = get_dist(1)
S = get_dist(N)

fennec = sum(1 if f <= s else -1 for f, s in zip(F, S))

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

Solution (Python):
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)


def get_dist(src):
    Q = deque([src])
    dist = [0] * (N + 1)
    while Q:
        v =  Q.popleft()
        for u in E[v]:
            if dist[u] == 0:
                Q.append(u)
                dist[u] = dist[v] + 1
    return dist[1:]

F = get_dist(1)
S = get_dist(N)

fennec, snuke = 0, 0
for f, s in zip(F, S):
    if f <= s:
        fennec += 1
    else:
        snuke += 1

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

Solution (Python):
from collections import deque


N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)


def get_dist(src):
    Q = deque([(src, 0)])
    dist = [-1] * (N + 1)
    while Q:
        v, d = Q.popleft()
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                Q.append((u, d + 1))
    return dist[1:]

F = get_dist(1)
S = get_dist(N)
fennec, snuke = 0, 0
for f, s in zip(F, S):
    if f <= s:
        fennec += 1
    else:
        snuke += 1

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

d1 = [-1] * n
d2 = [-1] * n
def dfs(v, d):
    for v_next in edge[v]:
        if d[v_next] == -1:
            d[v_next] = d[v] + 1
            dfs(v_next, d)

d1[0] = 0
dfs(0, d1)
d2[-1] = 0
dfs(n-1, d2)

n_f = 0
for i in range(n):
    if d1[i] <= d2[i]:
        n_f += 1

if n_f > n // 2:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

import math

N=int(input())

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

depth=[[0]*N for i in range(2)]

def dfs(d, i, p, k=0):
	for t in G[i]:
		if t!=p:
			depth[k][t]=d
			dfs(d+1, t, i,k)


dfs(1,0,-1, 0)
dfs(1,N-1,-1, 1)

cnt=0
for i,j in zip(depth[0], depth[1]):
	if i<=j:
		cnt+=1

print('Fennec' if cnt*2>N else 'Snuke')

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

distance1=[-1 for i in range(n)]
distance1[0]=0
next=connection[0]
next2=[]
check=[-1 for i in range(n)]
check[0]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

distanceN=[-1 for i in range(n)]
distanceN[n-1]=0
next=connection[n-1]
next2=[]
check=[-1 for i in range(n)]
check[n-1]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distanceN[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

ctF=0;ctS=0
for i in range(n):
  if distance1[i]<=distanceN[i]:
    ctF+=1
  else:
    ctS+=1
if ctF>ctS:
  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):

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 sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, x: int, d: "List[int]") -> None:
    d[v] = x
    for u in G[v]:
        if not d[u]:
            dfs(u, x + 1, d)


def main():
    global G, DB, DW
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    dfs(1, 1, DB), dfs(N, 1, 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 sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

from collections import deque


def bfs(s, d) -> 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 = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        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 sys
sys.setrecursionlimit(600000)

N = int(input())

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

def dfs(p, checked, now):
    
    if p == N-1:
        return now, True
    ok = False
    for q in graph[p]:
        if not checked[q]:
            now.append(q)
            checked[q] = True
            nbw, ok1 = dfs(q, checked, now)
            if ok1:
                bw = nbw
                ok = True
    if not ok:
        now.pop()
        return now, False
    return bw, True

checked = [False for _ in range(N)]
checked[0] = True
bw, ok = dfs(0, checked, [0])


between = [0 for _ in range(N)]
k = len(bw)
if k % 2 == 0:
    s0 = bw[k//2-1]
    sN = bw[k//2]
else:
    s0 = bw[k//2]
    sN = bw[k//2+1]
between[s0] = True
between[sN] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(s0, between, 0)
cN = dfs2(sN, between, 0)




if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(2000000)
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
ki=[[] for i in range(n+1)]
for i in range(n-1):
    ki[ab[i][0]].append(ab[i][1])
    ki[ab[i][1]].append(ab[i][0])

kyori=[[float("INF"), float("INF")] for i in range(n+1)]
def tansaku(m, dis, hito):
    q=[[m,dis]]
    while q:
        po=q.pop()
        for i in ki[po[0]]:
            if kyori[i][hito]>po[1]:
                kyori[i][hito]=po[1]
                q.append([i,po[1]+1])

tansaku(1,1,0)
tansaku(n,1,1)
fe,su=0,0

for i in range(1,n+1):
    if kyori[i][0]<=kyori[i][1]:
        fe+=1
    else:
        su+=1

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

nbr=[[] for _ in range(n)]
for i in range(n-1):
    nbr[l[i][0]-1].append(l[i][1]-1)
    nbr[l[i][1]-1].append(l[i][0]-1)
def sm(i,p):
    s=0
    for x in nbr[i]:
        if x!=p:s+=sm(x,i)
    return s+1
flg=False
f=0
c=[]
def dfs(i,p):
    global flg
    global c
    if i==n-1:flg=True
    if not flg:
        for x in nbr[i]:
            if x!=p:dfs(x,i)
            if flg:break
    if flg:
        c.append(i)
dfs(0,-1)
idx=(len(c)+1)//2
print('Fennec' if sm(c[::-1][idx],c[::-1][idx-1])*2<n else 'Snuke')

Solution (Python):
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    l[x].append(y)
    l[y].append(x)
from collections import deque
q=deque([0])
lf=[10**100 for i in range(n)]
lf[0]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if lf[p]+1<lf[i]:
            lf[i]=lf[p]+1
            q.append(i)
q=deque([n-1])
ls=[10**100 for i in range(n)]
ls[n-1]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if ls[p]+1<ls[i]:
            ls[i]=ls[p]+1
            q.append(i)
s,f=0,0
for i in range(n):
    if lf[i]<=ls[i]:
        f+=1
    else:
        s+=1
if f<=s:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    l[x].append(y)
    l[y].append(x)
from collections import deque
q=deque([0])
lf=[10**100 for i in range(n)]
lf[0]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if lf[p]+1<lf[i]:
            lf[i]=lf[p]+1
            q.append(i)
q=deque([n-1])
ls=[10**100 for i in range(n)]
ls[n-1]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if ls[p]+1<ls[i]:
            ls[i]=ls[p]+1
            q.append(i)
s,f=0,0
for i in range(n):
    if lf[i]<=ls[i]:
        f+=1
    else:
        s+=1
if f<=s:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b = LI()
    if not (a % 3 and b % 3 and (a + b) % 3):
        print("Possible")
    else:
        print("Impossible")
    return


def B():
    _, n = LI()
    l = LI()
    l.sort(reverse = True)
    print(sum(l[:n]))
    return


def C():
    n = II()
    a = LI()
    for i in range(n-1):
        a[i + 1] += a[i]
    maxa = a[-1]
    ans = inf
    for i in range(n-1):
        ans = min(ans, abs(2 * a[i] - maxa))
    print(ans)
    return


def D():
    n = II()
    edg = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    rank = [0] * n
    q = deque()
    q.append(0)
    rank[0] = 1
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i]:
                continue
            rank[i] = rank[p] + 1
            q.appendleft(i)
    k = 2
    q = deque()
    q.append(n - 1)
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i] < rank[p]:
                if rank[i] <= k:
                    a = p
                    break
                q.appendleft(i)
                k += 1
    ans1 = 1
    ans2 = 1
    check = [True] * n
    q = deque()
    q.append(a)
    check[a] = False
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i] > rank[p]:
                q.append(i)
                ans1 += 1
                check[i] = False
    q = deque()
    q.append(0)
    check[0] = False
    while q:
        p = q.pop()
        for i in edg[p]:
            if check[i]:
                q.append(i)
                ans2 += 1
                check[i] = False
    print(["Fennec", "Snuke"][ans1 >= ans2])
    return


if __name__ == '__main__':
    D()

Solution (Python):
from collections import deque

N = int(input())
to = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    to[a - 1].append(b - 1)
    to[b - 1].append(a - 1)
dist = None
pars = [0] * N
q = deque()
q.append((0, 0, 0))
while len(q):
    a, d, p = q.pop()
    pars[a] = p
    if a == N - 1:
        dist = d
        break
    for b in to[a]:
        if b != p:
            q.append((b, d + 1, a))

boundw = N - 1
for _ in range((dist - 1) // 2):
    boundw = pars[boundw]

q = deque()
q.append((0, 1, 0))
ans = 0
while len(q):
    a, sgn, p = q.pop()
    if a == boundw:
        sgn = -1
    ans += sgn
    for b in to[a]:
        if b != p:
            q.append((b, sgn, a))
print("Fennec" if ans > 0 else "Snuke")

Solution (Python):

from collections import deque


def bfs(s, distance):
    visited = [False] * N
    q = [(s, 1)]
    visited[s] = True

    while q:
        u, dist = q.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                distance[v] = dist
                q.append((v, dist+1))




N = int(input())
graph = [deque() for i in range(N)]
distance = [[0] * N for i in range(2)]

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



bfs(0, distance[0])
bfs(N-1, distance[1])


b = w = 0
for i in range(1, N-1):
    if distance[0][i] <= distance[1][i]:
        b += 1
    else:
        w += 1
if b <= w:
    print('Snuke')
else:
    print('Fennec')

Solution (Python):

from collections import deque


def bfs(s, distance):
    visited = [False] * (N+1)
    q = [(s, 1)]
    visited[s] = True

    while q:
        u, dist = q.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                distance[v] = dist
                q.append((v, dist+1))



N = int(input())
graph = [deque() for i in range(N+1)]
distance = [[0] * (N+1) for i in range(2)]

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



bfs(1, distance[0])
bfs(N, distance[1])


b = w = 0
for i in range(2, N):
    if distance[0][i] <= distance[1][i]:
        b += 1
    else:
        w += 1
if b <= w:
    print('Snuke')
else:
    print('Fennec')

Solution (Python):

from collections import deque

def bfs(s, dist):
    visited = [False] * (N+1)
    q = [(s, 1)]
    visited[s] = True

    while q:
        u, c = q.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                dist[v] = c
                q.append((v, c+1))


N = int(input())
graph = [deque() for i in range(N+1)]
dist = [[0] * (N+1) for i in range(2)]

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

bfs(1, dist[0])
bfs(N, dist[1])

b = w = 0
for i in range(2, N):
    if dist[0][i] <= dist[1][i]:
        b += 1
    else:
        w += 1
if b <= w:
    print('Snuke')
else:
    print('Fennec')

Solution (Python):
from collections import deque

def bfs(s, dist):
    visited = [False] * (N+1)
    q = [(s, 1)]
    visited[s] = True

    while q:
        u, c = q.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                dist[v] = c
                q.append((v, c+1))

def main():
    dist = [[0] * (N+1) for i in range(2)]
    
    for i in range(N-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    bfs(1, dist[0])
    bfs(N, dist[1])
    
    b = w = 0
    for i in range(2, N):
        if dist[0][i] <= dist[1][i]:
            b += 1
        else:
            w += 1
    if b <= w:
        print('Snuke')
    else:
        print('Fennec')

if __name__ == '__main__':
    N = int(input())
    graph = [deque() for i in range(N+1)]

    dist = [[0] * (N+1) for i in range(2)]
    
    main()