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

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

edges = [[] for _ in range(N + 1)]
for u, v in X:
    edges[u].append(v)
    edges[v].append(u)


def bfs(s, x):
    inf = 10 ** 9 + 7
    d = [inf] * (N + 1)
    d[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in edges[u]:
            if d[v] != inf:
                continue

            d[v] = d[u] + 1
            if v != x:
                q.append(v)

    return d


d1 = bfs(1, N)
d2 = bfs(N, 1)

cnt = 0
for i in range(1, N + 1):
    cnt += d1[i] <= d2[i]

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

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

import heapq
def dijkstra(s):
    
    d = [float('inf')]*n
    d[s] = 0
    
    used = [False]*n
    used[s] = True
    
    que = []
    for e in edge[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d


n = int(input()) 
w = n - 1

edge = [[] for i in range(n)]

for i in range(w):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    z = 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

dis_from_f = dijkstra(0)
dis_from_s = dijkstra(n - 1)

cnt = 0
for i, j in zip(dis_from_f, dis_from_s):
    if i <= j:
        cnt += 1
if cnt > n - cnt:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
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)

dist = [0] * N
def dfs(u, d, p=-1):
    global dist
    dist[u] = d
    for v in edges[u]:
        if v == p:
            continue
        dfs(v, d + 1, u)
    return dist

dist1 = dfs(0, 0, -1)
dist = [0] * N
dist2 = dfs(N - 1, 0, -1)

cnt = 0
for d1, d2 in zip(dist1, dist2):
    if d1 <= d2:
        cnt += 1
if N - cnt < cnt:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
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)


from collections import deque
seen = [False for _ in range(n)]
child = [[] for _ in range(n)]
par = [0 for _ in range(n)]
order = []
que = deque()
que.append(0)
seen[0] = True

while que:
    v = que.popleft()
    order.append(v)
    for to in edges[v]:
        if not seen[to]:
            seen[to] = True
            par[to] = v
            que.append(to)
            child[v].append(to)

d = [-1 for _ in range(n)]
c = [0 for _ in range(n)]
for i in order:
    d[i] = d[par[i]] + 1
for i in order[::-1]:
    if len(child[i]) == 0:
        continue
    for ch in child[i]:
        c[i] += c[ch] + 1



point = n - 1
move_s = (d[n-1] - 1) // 2
move_f = d[n-1] - 1 - move_s
for i in range((d[n-1] - 1) // 2):
    point = par[point]

cnt_s = c[point]
cnt_f = n - (c[point] + 1) - 1


print('Fennec' if cnt_f > cnt_s else 'Snuke')

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


import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n = int(input()) 
w = n - 1

edge = [[] for i in range(n)]

for i in range(w):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    z = 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

dis_from_f = dijkstra_heap(0)
dis_from_s = dijkstra_heap(n - 1)

cnt = 0
for i, j in zip(dis_from_f, dis_from_s):
    if i <= j:
        cnt += 1
if cnt > n - cnt:
    print("Fennec")
else:
    print("Snuke")

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

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

def dfs(v,d,dist):
    dist[v] = d
    for ve in edge[v]:
        if dist[ve] is None:
            dist = dfs(ve, d+1, dist)
    return dist
    
    
f_dist = dfs(0,0,[None]*n)
s_dist = dfs(n-1,0,[None]*n)

fget = sum(1 for f,s in zip(f_dist,s_dist) if f<=s)
print("Fennec" if fget*2>n else "Snuke")

Solution (Python):
from collections import deque
n = int(input())
tree = [[] for _ 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)

visit = [-1 for _ in range(n)]
f, s = 0, 0
f_q = deque([0])
s_q = deque([n-1])

while f_q or s_q:
    g = []
    while f_q:
        p = f_q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                f += 1
                g.append(i)
                visit[i] = 0
    f_q = deque(g)

    g = []
    while s_q:
        p = s_q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                s += 1
                g.append(i)
                visit[i] = 0
    s_q = deque(g)
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque
n = int(input())
tree = [[] for _ 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)

visit = [-1 for _ in range(n)]
f, s = 0, 0
f_q = deque([0])
s_q = deque([n-1])

while f_q or s_q:
    g = []
    while f_q:
        p = f_q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                f += 1
                g.append(i)
                visit[i] = 0
    f_q = deque(g)

    g = []
    while s_q:
        p = s_q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                s += 1
                g.append(i)
                visit[i] = 0
    s_q = deque(g)
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
N = int(input())
g = [[] for _ in range(N + 5)]
Fennec = [0]*(N+10)
Sunuke = [0]*(N+10)
sys.setrecursionlimit(10**8)

def dfs(r,f,d,dist):
	dist[r]=d
	for x in range(len(g[r])):
		if g[r][x]==f : continue
		else : dfs(g[r][x],r,d+1,dist)



for i in range(N-1):
	a,b=map(int,input().split())
	a-=1
	b-=1
	g[a].append(b)
	g[b].append(a)
dfs(0,-1,0,Fennec)
dfs(N-1,-1,0,Sunuke)
ans = int(0)

for i in range(N):
	if Fennec[i]<=Sunuke[i] : ans+=1
	else : ans-=1
if(ans>0):
	print("Fennec")
else:
	print("Snuke")

Solution (Python):
import sys
N = int(input())
g = [[] for _ in range(N + 5)]
Fennec = [0]*(N+10)
Sunuke = [0]*(N+10)
sys.setrecursionlimit(10**8)

def dfs(r,f,d,dist):
	dist[r]=d
	for x in range(len(g[r])):
		if g[r][x]==f : continue
		else : dfs(g[r][x],r,d+1,dist)



for i in range(N-1):
	a,b=map(int,input().split())
	a-=1
	b-=1
	g[a].append(b)
	g[b].append(a)
dfs(0,-1,0,Fennec)
dfs(N-1,-1,0,Sunuke)
ans = int(0)

for i in range(N):
	if Fennec[i]<=Sunuke[i] : ans+=1
	else : ans-=1
if(ans>0):
	print("Fennec")
else:
	print("Snuke")

Solution (Python):
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
read = sys.stdin.read

N, *ab = map(int, read().split())
a, b = zip(*zip(*[iter(ab)] * 2))

graph = csr_matrix(([1] * (N - 1), (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False, indices=[1, N])
d1 = distance[0][1:]
dn = distance[1][1:]

Fennec = np.count_nonzero(d1 <= dn)

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

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

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

for x,y in a:
    b[x-1].append(y-1)
    b[y-1].append(x-1)


import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1


        return dis
    return bfs()

fennec=tree(0)
snuke=tree(n-1)



ans1=0
ans2=0
for i in range(n):
    if fennec[i]<=snuke[i]:
        ans1+=1
    else:
        ans2+=1

if ans1>ans2:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import sys
input = sys.stdin.buffer.readline
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 get_dists(f):
    dists = [0 for _ in range(n)]
    q = deque()
    q.append((f, -1, 0))
    while len(q) > 0:
        num, f_num, dist = q.popleft()
        for node in edges[num]:
            if node == f_num:
                continue
            else:
                dists[node] = dist + 1
                q.append((node, num, dist+1))
    return dists

dist_1 = get_dists(0)
dist_n = get_dists(n-1)

ans = 0
for i in range(n):
    if dist_1[i] <= dist_n[i]:
        ans += 1

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

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

from collections import deque



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

    
    def dfs(q, path, hist):
        p = q.pop()
        if p == n:
            return path

        for e in edge[p]:
            if not hist[e]:
                q.append(e)
                path.append(e)
                hist[e] = True
                ret = dfs(q, path, hist)
                if ret:
                    return ret
                path.pop(-1)
        return None


    q = deque()
    q.append(1)
    hist = {i: False for i in range(n + 1)}
    hist[1] = True
    direct_path = dfs(q, [1], hist)
    d = len(direct_path) 
    if d % 2:
        fennec = direct_path[:d // 2 + 1]
        snuke = direct_path[d // 2 + 1:]
    else:
        fennec = direct_path[:d // 2]
        snuke = direct_path[d // 2:]

    edge[fennec[-1]].remove(snuke[0])
    
    
    color = 0
    picked = [False for _ in range(n)]
    q = deque()
    q.append(1)
    picked[0] = True
    while len(q):
        p = q.pop()
        color += 1
        for e in edge[p]:
            if not picked[e - 1]:
                q.append(e)
                picked[e - 1] = True
    
    if color > n - color:
        print("Fennec")
    else:
        print("Snuke")


submit()

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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


lst=[0]*(n+1)
f=deque([1])
s=deque([n])
fcnt,scnt=0,0
while 1:
    flag=0
    for i in range(len(f)):
        tmp=f.popleft()
        if lst[tmp]==0:
            lst[tmp]=1
            fcnt+=1
            flag=1
            for j in dic[tmp]:
                f.append(j)
    
    for i in range(len(s)):
        tmp=s.popleft()
        if lst[tmp]==0:
            lst[tmp]=1
            scnt+=1
            flag=1
            for j in dic[tmp]:
                s.append(j)
    
    if flag==0:
        break
    

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

Solution (Python):
from collections import deque
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)

dist_f = [None]*n
dist_s = [None]*n

que = deque([(0,0)])
while que:
    node, cost = que.popleft()
    if dist_f[node] != None:
        continue
    dist_f[node] = cost
    for to in g[node]:
        que.append((to, cost+1))

que = deque([(n-1, 0)])
while que:
    node, cost = que.popleft()
    if dist_s[node] != None:
        continue
    dist_s[node] = cost
    for to in g[node]:
        que.append((to, cost+1))
        
cnt = 0
for i in range(n):
    if dist_f[i] <= dist_s[i]:
        cnt += 1
print('Fennec' if cnt>n-cnt else 'Snuke')

Solution (Python):
import queue
import sys
sys.setrecursionlimit(10 ** 7)

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

G = [[] for _ in range(N + 1)]
for el in ab:
    a, b = el
    G[a].append(b)
    G[b].append(a)

seen = [False] * (N + 1)
todo = queue.Queue()
dist = [0] * (N + 1)
prev = [None] * (N + 1)

def bfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            todo.put(child)
            dist[child] = dist[parent] + 1
            prev[child] = parent
    if not todo.empty():
        bfs(todo.get())

bfs(1)


min_dist = dist[N]


route = []
temp = N
for _ in range(min_dist + 1):
    route.append(temp)
    temp = prev[temp]



seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    cnt[0] += 1
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)


S = route[(min_dist + 1) // 2 - 1]
F = route[(min_dist + 1) // 2]

seen[S] = True
seen[F] = True
cnt = [0]
dfs(S)
arround_S = cnt[0]
cnt = [0]
dfs(F)
arround_F = cnt[0]


if arround_F > arround_S:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    N = int(input())
    Graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        Graph[a].add(b)
        Graph[b].add(a)

    Fennec = [-1] * N
    Snuke = [-1] * N

    def bfs(start, arr):
        arr[start] = 0
        dq = deque()
        dq.append(start)
        while dq:
            v = dq.popleft()
            d = arr[v]
            for u in Graph[v]:
                if ~arr[u]:
                    continue
                arr[u] = d + 1
                dq.append(u)

    bfs(start=0, arr=Fennec)
    bfs(start=N - 1, arr=Snuke)

    cnt_f = sum(1 for f, s in zip(Fennec, Snuke) if f <= s)
    cnt_s = N - cnt_f

    print('Fennec' if cnt_f > cnt_s else 'Snuke')


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n = int(input())
edge = []
hand_a = [100005]*(n+1)
hand_b = [100005]*(n+1)
for i in range(n+1):
    edge.append([])
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)


def dfs(start, goal, hand):
    cnt = 0
    hand[start] = 0
    stack = [start]
    used = set()
    used.add(start)
    while stack:
        here = stack.pop()
        cnt += 1
        for i in edge[here]:
            if i == goal:
                pass
            elif i not in used:
                stack.append(i)
                used.add(i)
                hand[i] = hand[here] + 1
    return cnt, used


cnt_a, used_a = dfs(1, n, hand_a)
cnt_b, used_b = dfs(n, 1, hand_b)



a_ans = b_ans = 0
for i in range(1,n+1):
    if hand_a[i] <= hand_b[i]:
        a_ans += 1
    else:
        b_ans += 1
if a_ans > b_ans:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):



import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
G = [[] for _ in [0]*N]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)


def bfs(s):
    q = deque()
    q.append(s)
    D = [0]*N
    visited = [False]*N
    while q:
        v = q.popleft()
        visited[v] = True
        d = D[v]

        for u in G[v]:
            if visited[u]:
                continue
            D[u] = d+1
            q.append(u)

    return D


Df = bfs(0)
Ds = bfs(N-1)

cnt_f = 0
cnt_s = 0
for df, ds in zip(Df, Ds):
    if df <= ds:
        cnt_f += 1
    else:
        cnt_s += 1

print('Fennec' if cnt_f > cnt_s else 'Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n = int(input())
ki = [[]for _ in range(n)]
dist1 = [0]*n
distN = [0]*n
def dfs1(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        dist1[next] = dist1[now]+1
        dfs1(next,now)
def dfsN(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        distN[next] = distN[now]+1
        dfsN(next,now)
        
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
fs = 0
dfs1(0)
dfsN(n-1)
for i in range(n):
    if dist1[i] <= distN[i]:fs+=1
ss = n-fs
if fs > ss:print('Fennec')
else:print('Snuke')

Solution (Python):
import collections
N = int(input())
G = [set() for i in range(N)]

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


F = [-1]*N
F[0] = 0
q = collections.deque()
q.append(0)
while(q):
    x = q.popleft()
    for y in G[x]:
        if F[y] < 0:
            F[y] = F[x] + 1
            q.append(y)

S = [-1]*N
S[N-1] = 0
q.append(N-1)
while(q):
    x = q.popleft()
    for y in G[x]:
        if S[y] < 0:
            S[y] = S[x] + 1
            q.append(y)


ans = 0

q = collections.deque()
r = [True]*N
for i in range(N):
    if F[i] + S[i] == F[-1]:
        if F[i] <= S[i]:
            q.append(i)
            r[i] = False
        else:
            r[i] = False
ans = len(q)

while(q):
    x = q.popleft()
    for y in G[x]:
        if r[y]:
            ans += 1
            q.append(y)
            r[y] = False

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

Solution (Python):
n=int(input())
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)

from collections import deque
dist_f=[-1]*n
dist_f[0]=0
q=deque()
q.append(0)
while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_f[nx]==-1:
            dist_f[nx]=dist_f[cur]+1
            q.append(nx)

dist_s=[-1]*n
dist_s[n-1]=0
q=deque()
q.append(n-1)
while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_s[nx]==-1:
            dist_s[nx]=dist_s[cur]+1
            q.append(nx)
fenec,sunuke=0,0
for i in range(n):
    if dist_f[i]<=dist_s[i]:
        fenec+=1
    else:
        sunuke+=1
print("Fennec") if fenec>sunuke else print("Snuke")

Solution (Python):
def examA():
    def calc_L(x1,y1,x2,y2):
        return ((x2-x1)**2 + (y2-y1)**2)**0.5
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    for x in itertools.permutations(X):
        cur = 0
        for i in range(1,N):
            cur += calc_L(x[i-1][0],x[i-1][1],x[i][0],x[i][1])
        
        ans += cur
    for i in range(1,N+1):
        ans /= i
    print(ans)
    return

def examB():
    def judge(n):
        sn = 0
        for i in n:
            sn += int(i)
        if int(n)%sn==0:
            return "Yes"
        return "No"
    N = SI()
    ans = judge(N)
    print(ans)
    return

def examC():
    N, K = LI()
    P = LI()
    ans = 0
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    for i in range(N-K+1):
        cur = S[i+K] - S[i]
        if cur>ans:
            ans = cur
    print(ans)
    return

def examD():
    def bfs(n,V,s,W):
        visited = [False]*n
        que = deque()
        que.append(s)
        while(que):
            now = que.pop()
            visited[now] = True
            for ne in V[now]:
                if visited[ne]:
                    continue
                W[ne] += W[now]
                que.append(ne)
        return W
    N, Q = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    W = [0] * N
    for _ in range(Q):
        p, x = LI()
        W[p-1] += x
    ans = bfs(N,V,0,W)
    print(" ".join(map(str,ans)))
    return

def examE():
    def bfs(n,edges,s):
        L = [inf]*n
        que = deque()
        que.append(s)
        L[s] = 0
        while(que):
            now = que.popleft()
            for ne in edges[now]:
                if L[ne]>L[now]+1:
                    L[ne] = L[now]+1
                    que.append(ne)
        return L
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    F = bfs(N,V,0)
    S = bfs(N,V,N-1)
    f = 0; s = 0
    for i in range(N):
        if F[i]>S[i]:
            s += 1
        else:
            f += 1
    if f>s:
        print("Fennec")
    else:
        print("Snuke")
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

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

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

def calc(s):
    st = [s]
    minDist = [10**18] * N
    minDist[s] = 0
    while st:
        now = st.pop()
        for to in edges[now]:
            if minDist[to] > minDist[now] + 1:
                minDist[to] = minDist[now] + 1
                st.append(to)
    return minDist

A = calc(0)
B = calc(N - 1)

ans = 0
for i in range(N):
    ans += 1 if A[i] <= B[i] else -1
print('Fennec' if ans > 0 else 'Snuke')

Solution (Python):
def dijkstra(G, s):
    
    inf = 10**18
    n = len(G)
    D = [inf for i in range(n)]
    D[s] = 0
    Q = [s]
    while Q:
        x = Q.pop()
        for y in G[x]:
            if D[y] > D[x] + 1:
                D[y] = D[x] + 1
                Q.append(y)
    return D


n = int(input())
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)
D0 = dijkstra(G, 0)
D1 = dijkstra(G, n-1)
c0, c1 = 0, 0
for i in range(n):
    if D0[i] <= D1[i]:
        c0 += 1
    else:
        c1 += 1
if c0 > c1:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):


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

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)


dist2 = [-1]*N
que = deque([N-1])
dist2[N-1] = 0
while que:
    v = que.popleft()
    d = dist2[v]
    for w in G[v]:
        if dist2[w] > -1:
            continue
        dist2[w] = d + 1
        que.append(w)

ans = [0, 0]
for a,b in zip(dist, dist2):
    if a <= b:
        ans[0] += 1
    else:
        ans[1] += 1



if ans[0] > ans[1]:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque

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

def dist_from_X(X:int):
    """ BFSで距離を求める """
    dist = [-1] * N
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        for w in edge[v]:
            if dist[w] < 0:
                dist[w] = dist[v] + 1
                que.append(w)
    return dist

Fennec = dist_from_X(0)
Snuke = dist_from_X(N - 1)


cntF, cntS = 0,0
for f,s in zip(Fennec, Snuke):
    if f <= s:
        cntF += 1
    else:
        cntS += 1


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

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

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
def dfs(v):
  dist = [-1]*n
  dist[v] = 0
  stack = [v]
  while stack:
    nv = stack.pop()
    for i in T[nv]:
      if dist[i] == -1:
        dist[i] = dist[nv] + 1
        stack.append(i)
  return dist
B = dfs(0)
W = dfs(n-1)
cnt_b, cnt_w = 0, 0
for i in range(n):
  if B[i] <= W[i]:
    cnt_b += 1
  else:
    cnt_w += 1
if cnt_b > cnt_w:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
n = int(input())

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')

Solution (Python):









def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n = int(input())
    adj = [[] 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)

    black = [-1] * n
    white = [-1] * n
    f = deque([0])
    black[0] = 0
    s = deque([n-1])
    white[-1] = 0

    def bfs(q, color):
        while q:
            v = q.popleft()
            for nv in adj[v]:
                if color[nv] < 0:
                    color[nv] = color[v] + 1
                    q.append(nv)

    bfs(f, black)
    bfs(s, white)
    cnt = 0
    for i in range(n):
        if black[i] <= white[i]:
            cnt += 1
    if cnt > n-cnt:
        print('Fennec')
    else:
        print('Snuke')



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys


def bfs(s, trail):
    q = deque()
    q.append((s, 0))
    trail[s] = 0
    while q:
        p, step = q.popleft()
        for np in edge[p]:
            nstep = step + 1
            if trail[np] > nstep:
                q.append((np, nstep))
                trail[np] = nstep


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)


INF = 10 ** 9
path0 = [INF] * N
pathN = [INF] * N

bfs(0, path0)
bfs(N - 1, pathN)

fennec = 0
snuke = 0
for i in range(N):
    if path0[i] <= pathN[i]:
        fennec += 1
    else:
        snuke += 1

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

Solution (Python):
from collections import deque
import sys


def bfs(s, trail):
    q = deque()
    q.append((s, 0))
    trail[s] = 0
    while q:
        p, step = q.popleft()
        for np in edge[p]:
            nstep = step + 1
            if trail[np] > nstep:
                q.append((np, nstep))
                trail[np] = nstep


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)


INF = 10 ** 9
path0 = [INF] * N
pathN = [INF] * N

bfs(0, path0)
bfs(N - 1, pathN)

fennec = 0
snuke = 0
for i in range(N):
    if path0[i] <= pathN[i]:
        fennec += 1
    else:
        snuke += 1

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

Solution (Python):
from collections import deque

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(b)
    edge[b].append(a)

distF = [-1]*N
distS = [-1]*N
def bfs(s,dist):
    q = deque([])
    q.append([s,0])
    while len(q) != 0:
        v = q.popleft()
        dist[v[0]] = v[1]
        for nv in edge[v[0]]:
            if dist[nv] != -1:
                continue

            dist[nv] = dist[v[0]] + 1
            q.append([nv,dist[nv]])

bfs(0,distF)
bfs(N-1,distS)


Fennec = 0
Snuke = 0
for i in range(N):
    if distF[i] <= distS[i]:
        Fennec += 1
    else:
        Snuke += 1


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

Solution (Python):
from scipy.sparse.csgraph import dijkstra
n=int(input())
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)
d1=[-1]*n
d2=[-1]*n
q1=[0]
d1[0]=0
while q1:
  x=q1.pop()
  for t in g[x]:
    if d1[t]==-1:
      d1[t]=d1[x]+1
      q1.append(t)
q2=[n-1]
d2[n-1]=0
while q2:
  x=q2.pop()
  for t in g[x]:
    if d2[t]==-1:
      d2[t]=d2[x]+1
      q2.append(t)
cnt=0
for i in range(n):
  if d1[i]<=d2[i]:
    cnt+=1
if cnt>n//2:
  print('Fennec')
else:
  print('Snuke')