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())
adj = [[] for _ in range(N + 1)]

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

def bfs(S):
    dist = [N] * (N + 1)
    dist[S] = 0
    q = deque([S])
    while q:
        u = q.pop()
        for v in adj[u]:
            if dist[v] == N:
                dist[v] = dist[u] + 1
                q.appendleft(v)
    return dist

db = bfs(1)
dw = bfs(N)

if sum(db[i] > dw[i] for i in range(1, N + 1)) >= N / 2:
    print('Snuke')
else:
    print('Fennec')

Solution (Python):
n = int(input())
c = []
for i in range(n - 1):
    c.append([int(m) - 1 for m in input().split()])
for i in range(n - 1):
    c[i].append(1)

def DFS(K, w,edges,N):
  cnt = 0
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    cnt += 1
    if label != w:
        for i,c in roots[label]:
          if dist[i]==-1:
            dist[i]=dist[label]+c
            stack+=[i]
  return cnt - 1

def DFS2(K,w,edges,N):
  htg = []
  prl = []
  for i in range(n):
      """htg.append([])"""
      prl.append([])
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  """htg[0].append(0)"""
  while stack:
      label = stack.pop(-1)
      """if label != 0:
        htg[label] += htg[prl[label][0]]
        htg[label].append(label)"""
      for i,c in roots[label]:
        if dist[i]==-1:
          dist[i]=dist[label]+c
          stack+=[i]
          prl[i].append(label)
        if i==w:
            htg.append(i)
            while i != 0:
                gg = prl[i][0]
                htg.append(gg)
                i = gg
            return htg

htgn = DFS2(0, n - 1, c, n)
sroot = len(htgn) // 2
pnt = htgn[sroot - 1]

fenneccnt = DFS(0, pnt, c, n)
snukecnt = n - fenneccnt
if fenneccnt > snukecnt:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
N = int(input())
AB = [[int(_) for _ in input().split()] for i in range(N - 1)]

from collections import defaultdict

rs = defaultdict(set)

for a, b in AB:
    rs[a].add(b)
    rs[b].add(a)

from heapq import *

cs = [0] * (N + 1)
cs[1] = 1
cs[N] = 2

h = []
heappush(h, (1, 1))
heappush(h, (2, N))

bcount = 0

while h:
    t, x = heappop(h)
    bcount += t % 2
    for n in rs[x]:
        if cs[n] == 0:
            cs[n] = t + 2
            heappush(h, (t + 2, n))

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

Solution (Python):
from collections import defaultdict
N = int(input())
g = [[] for i in range(N)]
 
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    g[a] += [b]
    g[b] += [a]
    
def bfs(g, st):
    queue = [st]
    distances = [-1 for i in range(N)]
    distances[st] = 0
    
    while queue:
        node = queue.pop(0)
        for h in g[node]:
            if distances[h] == -1:
                distances[h] = distances[node] + 1
                queue += [h]
 
    return distances
 
dB = bfs(g, 0)
dW = bfs(g, N-1)
 
B, W = 0, 0
for i in range(N):
    if dB[i] <= dW[i]:
        B += 1
    else:
        W += 1
print("Fennec" if B > W else "Snuke")

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

def dps(road,dist,node,d):
    for x in road[node]:
        if dist[x]<0:
            dist[x]=d
            dps(road,dist,x,d+1)
    
N=int(input())
road=[[] for _ in range(N)]
f_d=[-1 for _ in range(N)]
s_d=[-1 for _ in range(N)]
f_d[0]=0
s_d[-1]=0

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

dps(road,f_d,0,1)
dps(road,s_d,N-1,1)

white=0
black=0

for i in range(N):
    if f_d[i]<=s_d[i]:
        black+=1
    else:
        white+=1

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

Solution (Python):
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
dfs_stack_Fennec=[0]
dfs_stack_Snuke=[N-1]
depth_Fennec=[-1]*N
depth_Snuke=[-1]*N
depth_Fennec[0]=0
depth_Snuke[N-1]=0
while dfs_stack_Fennec or dfs_stack_Snuke:
  s1=dfs_stack_Fennec.pop()
  s2=dfs_stack_Snuke.pop()
  for t1 in graph[s1]:
    if depth_Fennec[t1]==-1:
      depth_Fennec[t1]=depth_Fennec[s1]+1
      dfs_stack_Fennec.append(t1)
  for t2 in graph[s2]:
    if depth_Snuke[t2]==-1:
      depth_Snuke[t2]=depth_Snuke[s2]+1
      dfs_stack_Snuke.append(t2)
ans=0
for i in range(N):
  if depth_Fennec[i]<=depth_Snuke[i]:
    ans+=1
if 2*ans>N:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
import heapq
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append([b, 1])
    T[b].append([a, 1])


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in T[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


B = dijkstra(0)
W = dijkstra(N - 1)

result = [("B" if b <= w else "W") for b, w in zip(B, W)]
print("Fennec" if result.count("B") - result.count("W") > 0 else "Snuke")

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

z=[[] for _ in range(n)]
for a,b in ab:
    z[a-1].append(b-1)
    z[b-1].append(a-1)
dis1=[0 for _ in range(n)]
dis2=[0 for _ in range(n)]

from collections import deque
que=deque([])
que.append((0,-1,0))
while que:
    v,p,d=que.pop()
    dis1[v]=d
    for t in z[v]:
        if t==p:
            continue
        que.append((t,v,d+1))
que.append((n-1,-1,0))
while que:
    v,p,d=que.pop()
    dis2[v]=d
    for t in z[v]:
        if t==p:
            continue
        que.append((t,v,d+1))

x,y=0,0
for i in range(n):
    if dis1[i]<=dis2[i]:
        x+=1
    else:
        y+=1

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

Solution (Python):
from collections import defaultdict
import queue
N = int(input())
edge = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

def bfs(s):
    dist = defaultdict(lambda:float('inf'))
    dist[s] = 0
    que = queue.Queue()
    que.put(s)
    while que.qsize():
        s = que.get()
        for t in edge[s]:
            if dist[t] > dist[s] + 1:
                dist[t] = dist[s] + 1
                que.put(t)
    return dist

fdist = bfs(1)
sdist = bfs(N)
f = 0
for i in range(1,N+1):
    if fdist[i] <= sdist[i]:
        f += 1
s = N-f
if f > s:
    print('Fennec')
else:
    print('Snuke')

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

from math import ceil
g = Graph()
N = int(input())
for i in range(N-1):
    a,b = map(int,input().split())
    g.add_edge(a,b)
    g.add_edge(b,a)

d = Dijkstra(g,1)
path = d.shortest_path(N)
n = ceil(len(path)/2)
flist = path[:n]
slist = path[n:]
a = flist[-1]
b = slist[0]
g.graph[a].pop(g.graph[a].index((b,1)))
g.graph[b].pop(g.graph[b].index((a,1)))
d = Dijkstra(g,1)
f = len(d.dist)
s = N-f

if f > s:
    print('Fennec')
else:
    print('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, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

INF = float("inf")
que = deque()
que.append(0)
d = [INF] * N
d[0] = 0
rec = [None] * N
while que:
    v = que.popleft()
    for w in G[v]:
        if d[w] != INF:
            continue
        d[w] = d[v] + 1
        que.append(w)
        rec[w] = v

rec1 = [N - 1]
while rec[rec1[-1]] is not None:
    q = rec[rec1[-1]]
    rec1.append(q)
rec1 = rec1[::-1]
mid = d[-1] // 2 + 1
f = rec1[mid]

visited = [False] * N
visited[f] = True
fnum = 0
que = deque()
que.append(0)
while que:
    v = que.popleft()
    visited[v] = True
    fnum += 1
    for w in G[v]:
        if visited[w]:
            continue
        que.append(w)

snum = N - fnum
if fnum > snum:
    print("Fennec")
else:
    print("Snuke")

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

Qb, Qw = [0], [N-1]
dB, dW = [-1 for i in range(N)], [-1 for i in range(N)]
dB[0], dW[N-1] = 0, 0
while Qb:
    temp = Qb.pop(0)
    for n in P[temp]:
        if dB[n] == -1:
            dB[n] = dB[temp] + 1
            Qb.append(n)
while Qw:
    temp = Qw.pop(0)
    for n in P[temp]:
        if dW[n] == -1:
            dW[n] = dW[temp] + 1
            Qw.append(n)

B, W = 0, 0
for i in range(N):
    if dB[i] <= dW[i]:
        B += 1
    else:
        W += 1
print("Fennec" if B > W else "Snuke")

Solution (Python):

import sys
sys.setrecursionlimit(200000)

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

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

print("Fennec" if f > s 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())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

parent = [-1 for i in range(n)]
dist = [-1 for i in range(n)]
flag = [0 for i in range(n)]

def dfs(s):
    flag[s] = 1
    dist[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag[i]:
                continue
            flag[i] = 1
            parent[i] = v[0]
            dist[i] = v[1] + 1
            q.append((i, v[1] + 1))

parent2 = [-1 for i in range(n)]
dist2 = [-1 for i in range(n)]
flag2 = [0 for i in range(n)]

def dfs_f(s):
    count2 = 0
    flag2[s] = 1
    dist2[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag2[i]:
                continue
            count2 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count2

parent3 = [-1 for i in range(n)]
dist3 = [-1 for i in range(n)]
flag3 = [0 for i in range(n)]

def dfs_s(s):
    count3 = 0
    flag3[s] = 1
    dist3[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag3[i]:
                continue
            count3 += 1
            flag3[i] = 1
            parent3[i] = v[0]
            dist3[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count3

dfs(0)
D = dist[n-1]

j = n-1
flag2[n-1] = 1
flag3[0] = 1
for i in range(D):
    if (D - i) >= (D+2)//2:
        flag2[j] = 1
        j = parent[j]
    else:
        flag3[j] = 1
        j = parent[j]

df = dfs_f(0)
ds = dfs_s(n-1)

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

Solution (Python):
N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

INF = float('inf')
dists = [INF] * N
dists[0] = 0
visited = [0]*N
back = [None]*N
stack = [0]
while stack:
    v = stack.pop()
    visited[v] = 1
    if v == N-1:
        break
    d = dists[v]
    for to in es[v]:
        if visited[to] : continue
        dists[to] = d+1
        back[to] = v
        stack.append(to)

path = [N-1]
while back[path[-1]] is not None:
    b = back[path[-1]]
    path.append(b)
path.reverse()

f_cantgo = path[dists[-1]//2 + 1]

visited = [0]*N
visited[f_cantgo] = 1
f_can_go = 0
stack = [0]
while stack:
    v = stack.pop()
    visited[v] = 1
    f_can_go += 1
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)

s_can_go = N - f_can_go
print('Fennec' if f_can_go > s_can_go else 'Snuke')

Solution (Python):

"""
Created on Sat Sep 22 16:27:11 2018

@author: maezawa
"""
from collections import deque
import copy

n = int(input())
adj = [[] for _ in range(n+1)]
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    adj[ai].append(bi)
    adj[bi].append(ai)
    


node = [0]*(n+1)
f = 1
s = n
node[f] = 1
node[s] = -1

stack1 = deque([f])
stack2 = deque([s])
nextstack1 = deque([])
nextstack2 = deque([])
cnt1 = 0
cnt2 = 0

turn = 1

while stack1 or stack2:
    turn += 1
    while stack1:
        f = stack1.pop()
        for m1 in adj[f]:
            if node[m1] != 0:
                continue
            else:
                node[m1] = turn
                nextstack1.append(m1)
    stack1 = copy.deepcopy(nextstack1)
    nextstack1 = deque([])

    while stack2:
        s = stack2.pop()
        for m2 in adj[s]:
            if node[m2] != 0:
                continue
            else:
                node[m2] = -turn
                nextstack2.append(m2)
    stack2 = copy.deepcopy(nextstack2)
    nextstack2 = deque([])

cnt = 0
for i in node:
    if i>0:
        cnt += 1
    elif i<0:
        cnt -= 1
if cnt > 0:
    print('Fennec')
else:
    print('Snuke')

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

input = sys.stdin.readline

N = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]


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

d1 = Dijkstra(g, 0)
d2 = Dijkstra(g, N - 1)

cnt1, cnt2 = 0, 0
for i in range(1, N - 1):
    x = d1.shortest_distance(i)
    y = d2.shortest_distance(i)
    if x <= y:
        cnt1 += 1
    else:
        cnt2 += 1

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

Solution (Python):
from collections import deque
INF = 10**6
n = int(input())
path = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [b]
    else:
        path[a].append(b)
    if not b in path.keys():
        path[b] = [a]
    else:
        path[b].append(a)


dist_f = [INF]*(n+1)
dist_f[1] = 0
que_f = deque([1])
while len(que_f) > 0:
    st_f = que_f.popleft()
    for en_f in path[st_f]:
        if dist_f[en_f] == INF:
            dist_f[en_f] = dist_f[st_f]+1
            que_f.append(en_f)

dist_s = [INF]*(n+1)
dist_s[n] = 0
que_s = deque([n])
while len(que_s) > 0:
    st_s = que_s.popleft()
    for en_s in path[st_s]:
        if dist_s[en_s] == INF:
            dist_s[en_s] = dist_s[st_s]+1
            que_s.append(en_s)


count_f, count_s = 0, 0
for d_f, d_s in zip(dist_f[1:], dist_s[1:]):
    if d_f <= d_s:
        count_f += 1
    else:
        count_s += 1
if count_f > count_s:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
import sys
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(1000000)



def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))



def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v



def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk



def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return




dp = None

F_MODE = 1
S_MODE = 2

N = None
D = None
D_from_1, D_from_N = [], []


def dfs(v, prev, depth, mode):
    global D_from_1
    global D_from_N

    for next in D[v]:
        if next != prev:
            if mode == F_MODE:
                D_from_1[next] = depth
            else:
                D_from_N[next] = depth

            dfs(next, v, depth + 1, mode)


def main():
    global D
    global N
    global D_from_1
    global D_from_N

    N = int(input())
    D = [[] for _ in range(N + 1)]

    for i in range(N - 1):
        a, b = li_input()
        D[a].append(b)
        D[b].append(a)

    D_from_1 = [-1] * (N + 1)
    D_from_1[1] = 0
    D_from_N = [-1] * (N + 1)
    D_from_N[N] = 0

    dfs(1, -1, 1, F_MODE)
    dfs(N, -1, 1, S_MODE)

    fennec, snuke = 0, 0

    for i in range(1, N + 1):
        if D_from_1[i] <= D_from_N[i]:
            fennec += 1
        else:
            snuke += 1

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


main()

Solution (Python):
from collections import deque
from copy import deepcopy
N = int( input())
Path = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    Path[a].append(b)
    Path[b].append(a)
Mass = [-1 for _ in range(N)]
F = deque([0])
S = deque([N-1])
while len(F) != 0 or len(S) != 0:
    KF = deque([])
    while len(F) != 0:
        f = F.pop()
        for x in Path[f]:
            if Mass[x] == -1:
                Mass[x] = 1
                KF.append(x)
    F = deepcopy(KF)
    KS = deque([])
    while len(S) != 0:
        s = S.pop()
        for y in Path[s]:
            if Mass[y] == -1:
                Mass[y] = 0
                KS.append(y)
    S = deepcopy(KS)
if sum(Mass) >= N//2+1:
    print('Fennec')
else:
    print('Snuke')

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

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

for i in range(n-1):
    f,t = map(int,raw_input().split())
    f -= 1
    t -= 1

    edge[f].append(t)
    edge[t].append(f)

inf = float("inf")
dist1 = [inf for i in range(n)]

dist1[0] = 0
stk = []
for i in edge[0]:
    stk.append([i,1])

while stk:
    t,c = stk.pop()
    if dist1[t] == inf :
        dist1[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

dist2 = [inf for i in range(n)]
dist2[n-1] = 0
for i in edge[n-1]:
    stk.append([i,1])
while stk:
    t,c = stk.pop()
    if dist2[t] == inf :
        dist2[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

fennec = 0
snuke = 0

for i in range(n):
    if dist1[i] <= dist2[i]:
        fennec += 1
    else :
        snuke += 1


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

Solution (Python):

import heapq
inf = float('inf')
N = int(input())
paths = [{} for i in range(N+1)]
for i in range(N-1):
    s,t = list(map(int, input().split()))
    paths[s][t] = 1
    paths[t][s] = 1

def dijkstra(start, nodes, N):
    cost = [inf] * (N + 1)
    cost[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q: 
        w, x = heapq.heappop(q)
        if cost[x] < w: continue
        for y in nodes[x]:
            if cost[x] + paths[x][y] < cost[y]:
                cost[y] = cost[x] + paths[x][y]

                heapq.heappush(q, (cost[y], y))
    return cost


score_f = dijkstra(1, paths, N)
score_s = dijkstra(N, paths, N)

score = 0
for i in range(1, N+1):
    if score_f[i] > score_s[i]:
        score -= 1
    else:
        score += 1

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

Solution (Python):
import queue
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)
q=queue.Queue()
P=[-1 for i in range(N)]
dist=[-1 for i in range(N)]
q.put(0)

dist[0]=0
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if dist[p]==-1:
            q.put(p)
            dist[p]=dist[r]+1
            P[p]=r

S=dist[-1]

L=[];k=N-1
while(k!=-1):
    L.append(k)
    k=P[k]


c=[0 for i in range(N)]
for p in L:
    snuke=dist[p]
    fennec=S-dist[p]
    if fennec>=snuke:
        c[p]=1
    else:
        c[p]=-1

q=queue.Queue()
q.put(0)
reached=[0 for i in range(N)]
reached[0]=1
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if reached[p]==0:
            if c[p]!=-1:
                q.put(p)
                c[p]=1
                reached[p]=1
for i in range(N):
    if c[i]==0:
        c[i]=-1
if sum(c)>0:
    print("Fennec")
else:
    print("Snuke")

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

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

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

c_f = dijkstra(adj, N, 1)
c_s = dijkstra(adj, N, N)

score = 0
for i in range(1, N + 1):
    if c_f[i] > c_s[i]:
        score -= 1
    else:
        score += 1

print("Fennec" if score > 0 else "Snuke")

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

N = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

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

d1 = Dijkstra(g, 0)
d2 = Dijkstra(g, N - 1)
c1, c2 = 0, 0
for i in range(N):
    if d1.shortest_distance(i) <= d2.shortest_distance(i):
        c1 += 1
    else:
        c2 += 1

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

Solution (Python):
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
  a, b = map(int, input().split())
  T[a - 1].append(b - 1)
  T[b - 1].append(a - 1)
def dijkstra(N, s0):
  D = [N] * N
  D[s0] = 0
  Q = [N] * N
  Q[0] = s0
  tail = 1
  for i in range(N):
    s = Q[i]
    for adj in T[s]:
      if D[s] + 1 < D[adj]:
        D[adj] = D[s] + 1
        Q[tail] = adj
        tail += 1
  return D
D1 = dijkstra(N, 0)
D2 = dijkstra(N, N - 1)
score = 0
for i in range(N):
  score += 1 if D1[i] <= D2[i] else -1
print('Fennec' if score > 0 else 'Snuke')

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

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

f = [n for _ in range(n)]
s = [n for _ in range(n)]

f[0] = 0
after = [] + p[0]
before = set()
dist = 0
while 1:
    dist += 1
    check = 0
    temp = []
    for x in after:
        if f[x] == n:
            f[x] = dist
            temp += p[x]
            check = 1
    if check == 0:
        break
    t2 = set(temp) - before
    before = set(after)
    after = list(t2)

s[n - 1] = 0
after = [] + p[n - 1]
before = set()
dist = 0
while 1:
    dist += 1
    check = 0
    temp = []
    for x in after:
        if s[x] == n:
            s[x] = dist
            temp += p[x]
            check = 1
    if check == 0:
        break
    t2 = set(temp) - before
    before = set(after)
    after = list(t2)

score_f = 0
for i in range(n):
    if f[i] <= s[i]:
        score_f += 1

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(dict)
    for a, b in AB:
        g[a][b] = 1
        g[b][a] = 1

    f = 1
    s = N

    def df(v):
        d = {v: 0}
        q = [(v, 0)]
        while q:
            v, c = q.pop()
            for u in g[v]:
                if u not in d:
                    d[u] = c + 1
                    q.append((u, c+1))
        return d

    sd = df(s)
    fd = df(f)

    
    

    fc = 0
    sc = 0
    for i in range(2, N):
        if i == s or i == f:
            continue

        if sd[i] >= fd[i]:
            fc += 1
        elif sd[i] < fd[i]:
            sc += 1

    return 'Fennec' if fc > sc else 'Snuke'


def main():
    N = read_int()
    
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()