Problem:
 Score : 400 points    Problem Statement Fennec and Snuke are playing a board game.  On the board, there are N cells numbered 1 through N , and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i -th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.  Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored.
Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell.
More specifically, each player performs the following action in her/his turn:   Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black .  Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white .   A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.      Constraints  2 \leq N \leq 10^5  1 \leq a_i, b_i \leq N  The given graph is a tree.         Input Input is given from Standard Input in the following format:  N  a_1  b_1  :  a_{N-1}  b_{N-1}       Output If Fennec wins, print Fennec ; if Snuke wins, print Snuke .        Sample Input 1 7
3 6
1 2
3 1
7 4
5 7
1 4      Sample Output 1 Fennec  For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.       Sample Input 2 4
1 4
4 2
2 3      Sample Output 2 Snuke

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

int1 = lambda x: int(x) - 1

N = int(input())
P = np.array([tuple(map(int1, input().split())) for _ in range(N - 1)]).T

matr = csr_matrix((np.ones(N - 1, dtype=int), P), shape=(N, N))
way_F = dijkstra(matr, indices=0, directed=False).astype(int)
way_F[way_F < 0] = N + 1
way_S = dijkstra(matr, indices=N - 1, directed=False).astype(int)
way_S[way_F < 0] = N + 1

fc = np.count_nonzero(way_F <= way_S)
print('Fennec' if fc > N - fc else 'Snuke')

Solution (Python):
from collections import deque
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
V=[0]*n
V[0]=1
P=[0]*n
P[0]=-1
C=[1]*n
D=deque([0])
DD=deque([0])
GG=[[] for i in range(n)]
while len(D)>0:
  v=D[0]
  D.popleft()
  for i in range(len(G[v])):
    if V[G[v][i]]==0:
      V[G[v][i]]=1
      D.append(G[v][i])
      DD.append(G[v][i])
      P[G[v][i]]=v
DD=list(DD)[::-1]
for i in range(n):
  if DD[i]!=0:
    C[P[DD[i]]]+=C[DD[i]]
a=0
i=n-1
while i!=0:
  i=P[i]
  a=a+1
i=n-1
for _ in range((a-1)//2):
  i=P[i]
s=C[i]
f=n-C[i]
if f>s:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
N=int(input())
hen={i:set([]) for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    hen[a].add(b)
    hen[b].add(a)

parent={i:-1 for i in range(1,N+1)}
parent[1]=0
q=set([])
sub=set([])
q.add(1)
while q:
    while q:
        x=q.pop()
        for p in hen[x]:
            if parent[p]==-1:
                parent[p]=x
                sub.add(p)

        if not q:
            q=sub
            sub=set([])
            break

subtreesize={i:1 for i in range(1,N+1)}
q=set([])
for i in range(1,N+1):
    if i!=1 and len(hen[i])==1:
        q.add(i)
sub=set([])
flag={i:0 for i in range(1,N+1)}
while q:
    while q:
        x=q.pop()
        p=parent[x]
        if p!=1:
            subtreesize[p]+=subtreesize[x]
            flag[p]+=1
            if flag[p]==len(hen[p])-1:
                sub.add(p)
        else:
            subtreesize[1]+=subtreesize[x]

        if not q:
            q=sub
            sub=set([])
            break

s=N
load=[N]
while s!=1:
    s=parent[s]
    load.append(s)


depth=len(load)
white=subtreesize[load[depth//2-1]]
black=N-white
if white>=black:
    print('Snuke')
else:
    print('Fennec')

Solution (Python):






import sys
read = sys.stdin.readline
from collections import defaultdict, deque


def read_ints():
    return list(map(int, read().split()))


class Tree:
    def __init__(self, N):
        '''重み付き無向木構造をクラスにしてみる(余り意味はなさそう)'''
        from collections import defaultdict, deque
        self.N = N
        self.tree = defaultdict(lambda: [])
        self.dists = None
        self.parents = None
        self.root = None

    def _link(self, a, b, d):
        '''
        d is a distance between a and b
        '''
        self.tree[a].append((b, d))
        self.tree[b].append((a, d))

    def _init_dists(self, root=0):
        self.dists = [-1] * self.N
        self.parents = [-1] * self.N
        que = deque([(root, -1, 0)])  
        self.dists[root] = 0
        while que:
            u, p, d = que.popleft()
            self.parents[u] = p
            for nu, dadd in self.tree[u]:
                if nu == p:  
                    continue
                nd = d + dadd
                self.dists[nu] = nd
                que.append((nu, u, nd))

    def ret_dist(self, a, b):
        '''
        a,b間の距離を高速に取得する
        '''
        raise NotImplementedError()
        if self.parents == None:
            self._init_dists()
        
        

    def ret_dists(self, u):
        '''
        uを始点とした各点への距離を返す (うまくやれば二度目は高速化できそう？)
        '''
        ret = [-1] * self.N
        que = deque([(u, -1, 0)])  
        ret[u] = 0
        while que:
            u, p, d = que.popleft()
            for nu, dadd in self.tree[u]:
                if nu == p:  
                    continue
                nd = d + dadd
                ret[nu] = nd
                que.append((nu, u, nd))
        return ret


N = int(input())
graph = Tree(N)
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph._link(a, b, 1)

















fennec_dist = graph.ret_dists(0)
snuke_dist = graph.ret_dists(N - 1)

n_snuke = 0  
n_fennec = 0  
for f, s in zip(fennec_dist, snuke_dist):
    if f > s:  
        n_snuke += 1
    else:
        n_fennec += 1


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

Solution (Python):






import sys
read = sys.stdin.readline
from collections import defaultdict, deque


def read_ints():
    return list(map(int, read().split()))


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


def ret_dists(u):
    ret = [-1] * N
    que = deque([(u, -1, 0)])  
    ret[u] = 0
    while que:
        u, p, d = que.popleft()
        nd = 1 + d
        for nu in graph[u]:
            if nu == p:  
                continue
            ret[nu] = nd
            que.append((nu, u, nd))

    return ret


fennec_dist = ret_dists(0)
snuke_dist = ret_dists(N - 1)

n_snuke = 0  
n_fennec = 0  
for f, s in zip(fennec_dist, snuke_dist):
    if f > s:  
        n_snuke += 1
    else:
        n_fennec += 1


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

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

def tree(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        par[x]=p
        descend[p]+=tree(x)
    return descend[p]

n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
if l%2==0: print("Fennec" if p<q else "Snuke")
else: print("Fennec" if p<=q else "Snuke")

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

def tree(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        par[x]=p
        descend[p]+=tree(x)
    return descend[p]

n=int(input())
neighbor=[set()  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
if l%2==0: print("Fennec" if p<q else "Snuke")
else: print("Fennec" if p<=q else "Snuke")

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

def cur(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        else:
            par[x]=p
            descend[p]+=cur(x)
    neighbor[p].remove(par[p])
    return descend[p]

n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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


x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
if l%2==0: print("Fennec" if p<q else "Snuke")
else: print("Fennec" if p<=q else "Snuke")

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
def even(n): return 1 if n%2==0 else 0

n = int(readline())
g = [[] for i in range(n)] 
for i in range(n-1):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)

dist_fe = [10**10]*n
dist_su = [10**10]*n

dist_fe[0] = 0
dist_su[n-1] = 0

def bfs(d,v,dist):
    for i in g[v]:
        if d[i] == 10**10:
            d[i] = dist+1
            bfs(d,i,dist+1)

bfs(dist_fe,0,0)
bfs(dist_su,n-1,0)

b = 0
w = 0

for i in range(n):
    if dist_fe[i] <= dist_su[i]: 
        b += 1
    else:
        w += 1

ans = "Fennec" if b > w else "Snuke"
print(ans)

Solution (Python):
n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)
 
from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=1
prev=[-1]*n
 
while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=1
        Q.append(nxt)
        prev[nxt]=now
 
rt=[n-1]
now=n-1
while prev[now]!=-1:
    now=prev[now]
    rt.append(now)
rt.reverse()
cut= -(-len(rt)//2)
f_node=rt[cut-1]
s_node=rt[cut]
 
Q = deque()
Q.append([0,0]) 
visited=[-1]*n
visited[0]=0
 
while Q:
    now,fs = Q.popleft()
    for nxt in link[now]:
        nxt_fs=fs
        if now==f_node and nxt==s_node:
            nxt_fs=1
        if visited[nxt]!=-1:
            continue
        visited[nxt]=nxt_fs
        Q.append([nxt,nxt_fs])
s_score = sum(visited)
f_score = n-s_score
if s_score >= f_score:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
from collections import deque
n = int(input())
G = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)

dist_zero = [-1]*n
dist_zero[0] = 0
queue = deque()
queue.append(0)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_zero[to] == -1:
            dist_zero[to] = dist_zero[now] + 1
            queue.append(to)

dist_n = [-1]*n
dist_n[-1] = 0
queue = deque()
queue.append(-1)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_n[to] == -1:
            dist_n[to] = dist_n[now] + 1
            queue.append(to)

f = sum([(dist_zero[i]<=dist_n[i]) for i in range(n)])

print("Fennec" if 2*f > n else "Snuke")

Solution (Python):
from collections import deque

N = int(input())

data = [[] for i in range(N)]

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

stack = deque([0])
visit_in = [-1]*N
visit_in[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if visit_in[y] >= 0:
            continue
        visit_in[y] = x
        stack.append(y)

path = [N-1]

while path[-1] != 0:
    path.append(visit_in[path[-1]])



group = [-1]*N

for x in path:
    group[x] = x

stack = deque(path[:])

while stack:
    x = stack.pop()
    for y in data[x]:
        if group[y] != -1:
            continue
        group[y] = group[x]
        stack.append(y)



num = [0]*N
for i in range(N):
    num[group[i]] += 1



p = len(path)-1
q = 0
fennec = num[0]
snuke = num[N-1]

while q < p - 1:
    p -= 1
    fennec += num[path[p]]
    if q < p -1:
        q += 1
        snuke += num[path[q]]
    
    

if fennec <= snuke:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter, 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)

d_F = [0] + [-1]*(N-1)
d_S = [-1]*(N-1) + [0]

q_F = deque([0])
q_S = deque([N-1])

while len(q_F) > 0:
    u = q_F.popleft()
    for v in G[u]:
        if d_F[v] == -1:
            d_F[v] = d_F[u] + 1
            q_F.append(v)

while len(q_S) > 0:
    u = q_S.popleft()
    for v in G[u]:
        if d_S[v] == -1:
            d_S[v] = d_S[u] + 1
            q_S.append(v)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    fen_dist, sun_dist = [0] * N, [0] * N
    
    def dfs1(node, parent, dist):
        fen_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs1(child, node, dist + 1)
    
    def dfs2(node, parent, dist):
        sun_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs2(child, node, dist + 1)
    
    dfs1(0, -1, 0)
    dfs2(N - 1, -1, 0)
    
    cnt_fen, cnt_sun = 0, 0
    for i in range(N):
        if fen_dist[i] <= sun_dist[i]:
            cnt_fen += 1
        else:
            cnt_sun += 1
    
    if cnt_fen <= cnt_sun:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    solve()

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

from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=1
prev=[-1]*n

while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=1
        Q.append(nxt)
        prev[nxt]=now

rt=[n-1]
now=n-1
while prev[now]!=-1:
    now=prev[now]
    rt.append(now)
rt.reverse()
cut= -(-len(rt)//2)
f_node=rt[cut-1]
s_node=rt[cut]

Q = deque()
Q.append([0,0]) 
visited=[-1]*n
visited[0]=0

while Q:
    now,fs = Q.popleft()
    for nxt in link[now]:
        nxt_fs=fs
        if now==f_node and nxt==s_node:
            nxt_fs=1
        if visited[nxt]!=-1:
            continue
        visited[nxt]=nxt_fs
        Q.append([nxt,nxt_fs])
s_score = sum(visited)
f_score = n-s_score
if s_score >= f_score:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    depth = [-1] * n
    depth[0] = 0
    snuke = [0] * n
    snuke[-1] = 1
    children = [1] * n

    def dfs(i):
        if len(G[i]) == 0:
            return
        else:
            for e in G[i]:
                if depth[e] == -1:
                    depth[e] = depth[i] + 1
                    dfs(e)
                    snuke[i] |= snuke[e]
                    children[i] += children[e] 
  
    dfs(0)
    white = depth[-1]//2 + 1
    for i in range(n):
        if depth[i] == white and snuke[i]:
            sp = children[i]
            fp = n - sp
            break
    
    if  fp > sp:
        print('Fennec')
    else:
        print('Snuke')  
if __name__=='__main__':
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(200000)
lf,ls=[None]*N,[None]*N
lf[0]=0
ls[-1]=0
def hu(n,c,l):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            hu(i,c+1,l)
hu(0,1,lf)
hu(-1,1,ls)
af=0
for i in range(N):
    if lf[i]<=ls[i]:
        af+=1
if af*2>N:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque

def bfs(i, c):
    q = deque()
    q.append(i)
    while q:
        p = q.popleft()
        for j in g[p]:
            if c[j] == 0 and i != j:
                q.append(j)
                c[j] = c[p] + 1
    return c

n = int(input())
g = [-1] * n
c1 = [0] * n
c2 = [0] * n
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if g[a] == -1:
        g[a] = [b]
    else:
        g[a].append(b)
    if g[b] == -1:
        g[b] = [a]
    else:
        g[b].append(a)

c1 = bfs(0, c1)
c2 = bfs(n - 1, c2)

F, S = 0, 0
for i in range(n):
    if c1[i] <= c2[i]:
        F += 1
    else:
        S += 1
print("Fennec" if F > S else "Snuke")

Solution (Python):

import heapq

N = int(input())

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

INF = float("inf")



dist_f = [INF] * N
dist_f[0] = 0
q = [(0,0)]
while q:
    cost, curr = heapq.heappop(q)
    if dist_f[curr] < cost:
        continue
    for nxt in es[curr]:
        if dist_f[nxt] < dist_f[curr] + 1:
            continue
        dist_f[nxt] = dist_f[curr] + 1
        heapq.heappush(q, (dist_f[nxt], nxt))


dist_s = [INF] * N
dist_s[N-1] = 0
q = [(0,N-1)]
while q:
    cost, curr = heapq.heappop(q)
    if dist_s[curr] < cost:
        continue
    for nxt in es[curr]:
        if dist_s[nxt] < dist_s[curr] + 1:
            continue
        dist_s[nxt] = dist_s[curr] + 1
        heapq.heappush(q, (dist_s[nxt], nxt))

cnt_f = 0
cnt_s = 0
for i in range(1,N-1):
    if dist_f[i] <= dist_s[i]:
        cnt_f += 1
    else:
        cnt_s += 1

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

Solution (Python):

import heapq

N = int(input())

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

INF = float("inf")



dist_f = [INF] * N
dist_f[0] = 0
q = [(0,0)]
while q:
    cost, curr = heapq.heappop(q)
    if dist_f[curr] < cost:
        continue
    for nxt in es[curr]:
        if dist_f[nxt] < dist_f[curr] + 1:
            continue
        dist_f[nxt] = dist_f[curr] + 1
        heapq.heappush(q, (dist_f[nxt], nxt))


dist_s = [INF] * N
dist_s[N-1] = 0
q = [(0,N-1)]
while q:
    cost, curr = heapq.heappop(q)
    if dist_s[curr] < cost:
        continue
    for nxt in es[curr]:
        if dist_s[nxt] < dist_s[curr] + 1:
            continue
        dist_s[nxt] = dist_s[curr] + 1
        heapq.heappush(q, (dist_s[nxt], nxt))

cnt_f = 0
cnt_s = 0
for i in range(1,N-1):
    if dist_f[i] <= dist_s[i]:
        cnt_f += 1
    else:
        cnt_s += 1

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

Solution (Python):
import sys
sys.setrecursionlimit(2 * 10 ** 5)

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

d1 = [0] * n
dn = [0] * n

def dfs(v, ng, dis, d):
    d[v] = dis
    ng.add(v)
    for n in connect[v]:
        if n not in ng:
            dfs(n, ng, dis+1, d)

dfs(0, set(), 0, d1)
dfs(n-1, set(), 0, dn)

black = 0
white = 0
for i in range(n):
    if d1[i] <= dn[i]:
        black += 1
    else:
        white += 1
if black > white:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):

from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


def bfs(G: "List[List[int]]", a: int):
    q = deque()  
    q.append(a)
    dist = [-1] * len(G)
    dist[a] = 0
    while q:
        s = q.popleft()
        for t in G[s]:
            if dist[t] >= 0:
                continue
            q.append(t)
            dist[t] = dist[s] + 1
    return dist


def solve(N: int, a: "List[int]", b: "List[int]"):
    G = [[] for i in range(N)]
    for ai, bi in zip(a, b):
        ai -= 1
        bi -= 1
        G[ai].append(bi)
        G[bi].append(ai)
    db = bfs(G, 0)
    dw = bfs(G, N - 1)
    bn = sum((dbi <= dwi) for dbi, dwi in zip(db, dw))
    wn = N - bn
    if bn > wn:
        print("Fennec")
    else:
        print("Snuke")


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


if __name__ == '__main__':
    main()

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

class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    stack.append(adj)

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

Tf = Tree(N, E)
Tf.setroot(0)

Ts = Tree(N, E)
Ts.setroot(N - 1)

fennec = 0
snuke = 0

for i in range(N):
    if Tf.depth[i] <= Ts.depth[i]:
        fennec += 1
    else:
        snuke += 1

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

Solution (Python):
from collections import deque
N, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a,b in zip(*[iter(L)]*2):
  dic[a] += [b]
  dic[b] += [a]
fdist = [-1]*(N+1)
sdist = [-1]*(N+1)
fdist[1] = 0
sdist[N] = 0
q = deque([1])
while q:
  v = q.popleft()
  for u in dic[v]:
    if fdist[u] == -1:
      fdist[u] = fdist[v] + 1
      q.append(u)
q = deque([N])
while q:
  v = q.popleft()
  for u in dic[v]:
    if sdist[u]==-1:
      sdist[u] = sdist[v] + 1
      q.append(u)
ans = sum(a<=b for a,b in zip(fdist,sdist))-1
if 2*ans>N:
  print('Fennec')
else:
  print('Snuke')

Solution (Python):
N = int(input())
G = [[] for _ in range(N)]
que_f = [0]
que_s = [N-1]
dis_f = [-1]*N
dis_s = [-1]*N
for i in range(N-1):
  a, b = map(int,input().split())
  a -= 1
  b -= 1
  G[a].append(b)
  G[b].append(a)

visited_f = [False]*N
dis_f[0] = 0
while que_f:
  pos = que_f.pop(0)
  for next_pos in G[pos]:
    if visited_f[next_pos] == True:
      continue
    que_f.append(next_pos)
    visited_f[pos] = True
    dis_f[next_pos] = dis_f[pos] + 1

visited_s = [False]*N
dis_s[N-1] = 0
while que_s:
  pos = que_s.pop(0)
  for next_pos in G[pos]:
    if visited_s[next_pos] == True:
      continue
    que_s.append(next_pos)
    visited_s[pos] = True
    dis_s[next_pos] = dis_s[pos] + 1
    
f = 0
s = 0
for i in range(N):
  if dis_f[i] <= dis_s[i]:
    f += 1
  else:
    s += 1

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

Solution (Python):


import sys

sys.setrecursionlimit(10**6)

def killme(num,lis):
    visited[num]=1
    if num==N-1:
        lis.append(num)
        for index,item in enumerate(lis):
            highway[item]=index
    else:
        for next_n in way[num]:
            if visited[next_n]==0:
                lis.append(num)
                killme(next_n,lis)
                lis.pop(-1)
    return 

def dfs(num,root):
    visited[num]=1
    cluster[root].append(num)
    for next_n in way[num]:
        if visited[next_n]==0 and highway[next_n]==-1:
            
            dfs(next_n,root)
    return 

N=int(input())

way=[[] for i in range(N)]
visited=[0]*N
highway=[-1]*N

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

killme(0,[])





visited=[0]*N
cluster=[[] for i in range(highway[-1]+1)]

for index,item in enumerate(highway):
    if item!=-1:
        dfs(index,item)

F=0
S=0
for i in range(highway[-1]+1):
    if i<=highway[-1]//2:
        F+=len(cluster[i])
    else:
        S+=len(cluster[i])

if F>S:
    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)

INF=10**9

d=[INF for i in range(N)]
edges=[0 for i in range(N)]
d[0]=0
queue=[]
queue.append(0)

while queue:
    u=queue.pop(0)
    for i in range(len(G[u])):
        if d[G[u][i]]==INF:
            queue.append(G[u][i])
            d[G[u][i]]=d[u]+1

k=d[N-1]
m=N-1
queue.append(N-1)

while k>d[N-1]//2+1:
    u=queue.pop(0)
    for i in range(len(G[u])):
        if d[G[u][i]]==d[u]-1:
            queue.append(G[u][i])
            k=d[u]
            m=u

queue=[]
queue.append(m)
unused=[True for i in range(N)]
unused[m]=False

sunuke=1

while queue:
    u=queue.pop(0)
    sunuke+=len(G[u])-1
    for i in range(len(G[u])):
        if d[G[u][i]]>d[u] and unused[G[u][i]]:
            queue.append(G[u][i])
            unused[G[u][i]]=False

if sunuke>=-(-N//2):
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def dfs(s):
    d = [-1] * n
    p = [-1] * n
    d[s] = 0
    stack = [s]
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                stack.append(v)

    return d, p


depth, par = dfs(0)
rev = (depth[n-1] - 1) // 2
root = n - 1
for _ in range(rev):
    root = par[root]

p = par[root]
adj[p].remove(root)
adj[root].remove(p)

depth, _ = dfs(n-1)
snuke = len([e for e in depth if e != -1])
fennec = n - snuke
if fennec > snuke:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Solution (Python):
from collections import deque

def BFS_que_tree_2(list_tree,start1,start2,visited):
    visited[start1] = 1
    visited[start2] = -1
    q = deque([[start1,1],[start2,-1]])
    while q:
        start,color  = q.popleft()
        bfs_1step(list_tree,start,visited,q,tag=color)


def bfs_1step(list_tree,start,visited,q,tag=1):
    for node in list_tree[start]:  
        if visited[node] != 0:
            continue
        else:
            visited[node] = tag
            q.append([node,tag])
    return


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

visited = [0]*n
BFS_que_tree_2(tr,0,n-1,visited)
print("Fennec" if sum(visited) > 0 else "Snuke")

Solution (Python):
from collections import defaultdict,Counter
import queue

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

q1=queue.Queue()
qN=queue.Queue()

dist=[None for i in range(N)]
dist[0]=1
dist[N-1]=-1

phase=1
for i in ab[1]:
    q1.put((i,phase))
for g in ab[N]:
    qN.put((g,phase))

while not (q1.empty() and qN.empty()):
    while True:
        if q1.empty():
            break
        next1,p=q1.queue[0]
        if p==phase:
            if dist[next1-1]==None:
                dist[next1-1]=1
            next1,p=q1.get()
            for i in ab[next1]:
                if dist[i-1]==None:
                    q1.put((i,phase+1))
        else:
            break


    while True:
        if qN.empty():
            break
        nextN,p=qN.queue[0]
        if p==phase:
            if dist[nextN-1]==None:
                dist[nextN-1]=-1
            nextN,p=qN.get()
            for i in ab[nextN]:
                if dist[i-1]==None:
                    qN.put((i,phase+1))
        else:
            break
    phase+=1

c=Counter(dist)
if c[-1]<c[1]:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import defaultdict,Counter
import queue

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

q1=queue.Queue()
qN=queue.Queue()

dist=[None for i in range(N)]
dist[0]=1
dist[N-1]=-1

phase=1
F=0
S=0
for i in ab[1]:
    q1.put((i,phase))
    F+=1
for g in ab[N]:
    qN.put((g,phase))
    S+=1

while not (q1.empty() and qN.empty()):
    while True:
        if q1.empty():
            break
        next1,p=q1.queue[0]
        if p==phase:
            if dist[next1-1]==None:
                F+=1
                dist[next1-1]=1
            next1,p=q1.get()
            for i in ab[next1]:
                if dist[i-1]==None:
                    q1.put((i,phase+1))
        else:
            break


    while True:
        if qN.empty():
            break
        nextN,p=qN.queue[0]
        if p==phase:
            if dist[nextN-1]==None:
                S+=1
                dist[nextN-1]=-1
            nextN,p=qN.get()
            for i in ab[nextN]:
                if dist[i-1]==None:
                    qN.put((i,phase+1))
        else:
            break
    phase+=1

c=Counter(dist)
if c[-1]<c[1]:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import defaultdict,Counter
import queue

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

q1=queue.Queue()
qN=queue.Queue()

dist=[None for i in range(N)]
dist[0]=1
dist[N-1]=-1

phase=1
for i in ab[1]:
    q1.put((i,phase))
for g in ab[N]:
    qN.put((g,phase))

while not (q1.empty() and qN.empty()):
    while True:
        if q1.empty():
            break
        next1,p=q1.queue[0]
        if p==phase:
            if dist[next1-1]==None:
                dist[next1-1]=1
            next1,p=q1.get()
            for i in ab[next1]:
                if dist[i-1]==None:
                    q1.put((i,phase+1))
        else:
            break


    while True:
        if qN.empty():
            break
        nextN,p=qN.queue[0]
        if p==phase:
            if dist[nextN-1]==None:
                dist[nextN-1]=-1
            nextN,p=qN.get()
            for i in ab[nextN]:
                if dist[i-1]==None:
                    qN.put((i,phase+1))
        else:
            break
    phase+=1

c=Counter(dist)
if c[-1]<c[1]:
    print("Fennec")
else:
    print("Snuke")