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):
N = int(input())
edge = [[]*N for _ in range(N)]

for _ in range(N-1):
    go,to = map(int,input().split())
    go -= 1
    to -= 1
    edge[go].append(to)
    edge[to].append(go)
    
from collections import deque
que = deque(maxlen=N)
que.append([0,0])
dist0 = [None]*N
distn = [None]*N
while(que):
    v = que.popleft()
    c = v[0]
    d = v[1]
    for i in edge[c]:
        if dist0[i] is None:
            dist0[i] = d + 1
            que.append([i,d+1])
que.append([N-1,0])
while(que):
    v = que.popleft()
    c = v[0]
    d = v[1]
    for i in edge[c]:
        if distn[i] is None:
            distn[i] = d + 1
            que.append([i,d+1])
w = b = 0
for d1,dn in zip(dist0,distn):
    if d1<=dn:
        b += 1
    else:
        w += 1
print('Fennec' if b-w > 0 else 'Snuke')

Solution (Python):
import heapq
N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
G = {}
for a, b in AB:
    a -= 1
    b -= 1
    
    G[a] = G.get(a, set())
    G[b] = G.get(b, set())
    G[a].add(b)
    G[b].add(a)


def dijkstra_stack(i):
    D = [-1] * N
    D[i] = 0
    stack = [i]
    while True:
        i = stack.pop(0)
        update = False
        for j in G[i]:
            if D[j] == -1:
                update = True
                D[j] = D[i] + 1
                stack += [j]
        if not stack:
            break
    return D


D_Fennec = dijkstra_stack(0)
D_Snuke = dijkstra_stack(N - 1)

f = 0
s = 0
for i in range(N):
    if D_Fennec[i] <= D_Snuke[i]:
        f += 1
    else:
        s += 1
if f > s:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
def bfs(graph,start,n,check):
    if check == False:
        arrival = [0 for i in range(n+1)]
    else:
        arrival = [0 for i in range(n+1)]
        arrival[check] = -1
    q = [start]
    arrival[start] = 1
    while len(q) != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == 0:
                q.append(graph[q[0]][i])
                arrival[graph[q[0]][i]] = arrival[q[0]]+1
        q.pop(0)
    return arrival

n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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


fstart = bfs(graph,1,n,False)
sstart = bfs(graph,n,n,False)
fennec = 0
snuke = 0
for i in range(1,n+1):
    if abs(fstart[i]-fstart[1]) <= abs(sstart[i]-sstart[n]):
        fennec += 1
    else:
        snuke += 1


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

Solution (Python):
from scipy.sparse import*;f=lambda*z:map(int,input().split());n,=f();c=[1]*~-n;g,h=csgraph.dijkstra(csr_matrix((c,list(zip(*map(f,c)))),[n+1]*2),0,[1,n]);print('FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2])

Solution (Python):
from scipy.sparse import*;f=lambda*z:map(int,input().split());n,=f();g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,list(zip(*map(f,[0]*~-n)))),[n+1]*2),0,[1,n]);print('FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2])

Solution (Python):
from scipy.sparse import*;f=lambda*z:map(int,input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,[1,n]);print('FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2])

Solution (Python):
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,[1,n]);print'FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2]

Solution (Python):
import sys

def main():
    sys.setrecursionlimit(1000000) 
    buf = input()
    N = int(buf)
    a = []
    b = []
    for i in range(N-1):
        buf = input()
        buflist = buf.split()
        a.append(int(buflist[0]) - 1)
        b.append(int(buflist[1]) - 1)
    graph = []
    for i in range(N):
        graph.append([])
    for i in range(N-1):
        graph[a[i]].append(b[i])
        graph[b[i]].append(a[i])
    path = find_path(graph, 0, N-1, [])
    split_point = (len(path) + 1) // 2
    fennec_base = path[0:split_point]
    snuke_base = path[split_point:len(path)]
    fennec_vertex_count = len(fennec_base)
    snuke_vertex_count = len(snuke_base)
    for i, v in enumerate(fennec_base):
        for j in graph[v]:
            if i != 0:
                if j == fennec_base[i-1]:
                    continue
            if i != len(fennec_base) - 1:
                if j == fennec_base[i+1]:
                    continue
            else:
                if j == snuke_base[0]:
                    continue
            fennec_vertex_count += get_vertex_count(graph, v, j)
    for i, v in enumerate(snuke_base):
        for j in graph[v]:
            if i != 0:
                if j == snuke_base[i-1]:
                    continue
            else:
                if j == fennec_base[-1]:
                    continue
            if i != len(snuke_base) - 1:
                if j == snuke_base[i+1]:
                    continue
            snuke_vertex_count += get_vertex_count(graph, v, j)
    if fennec_vertex_count > snuke_vertex_count:
        print("Fennec")
    else:
        print("Snuke")

def find_path(graph, current, target, path):
    path.append(current)
    if current == target:
        return path
    for i in graph[current]:
        if len(path) >= 2:
            if i == path[-2]:
                continue
        result = find_path(graph, i, target, path)
        if result:
            return path
    path.pop()
    return None

def get_vertex_count(graph, base, next):
    count = 1
    for i in graph[next]:
        if i == base:
            continue
        count += get_vertex_count(graph, next, i)
    return count

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

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

inf = float('inf')
ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
ctr = 1
now = {N}
distS = [inf for _ in range(N+1)]
distS[N] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distS[nb] > distS[na] + 1:  
                distS[nb] = distS[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
ctr = 0
for i in range(1,N+1):
    if distF[i] <=  distS[i]:
        ctr += 1
if 2*ctr > N:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

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

inf = float('inf')
ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
ctr = 1
now = {N}
distS = [inf for _ in range(N+1)]
distS[N] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distS[nb] > distS[na] + 1:  
                distS[nb] = distS[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
D = distF[N]
for i in range(1,N+1):
    if distF[i] == D//2 and distF[i]+distS[i] == D:
        St = i
    if distF[i] == D//2 + 1 and distF[i]+distS[i] == D:
        En = i
path[St].remove(En)
path[En].remove(St)

ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
ctr1 = 0
while ctr1 != ctr:
    ctr1 = ctr
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
if 2*ctr > N:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):

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

inf = 10**6


fvisited = [inf for _ in range(n+1)]
fvisited[1] = 0
q = deque([1])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if fvisited[e]==inf:
            fvisited[e] = fvisited[s]+1
            q.append(e)

svisited = [inf for _ in range(n+1)]
svisited[n] = 0
q = deque([n])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if svisited[e]==inf:
            svisited[e] = svisited[s]+1
            q.append(e)



fcnt = 0
scnt = 0
for i in range(1,n+1):
    if fvisited[i]<=svisited[i]:
        fcnt += 1
    else:
        scnt += 1

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

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

def dfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
    return d

ans=0
for i,j in zip(dfs(0),dfs(n-1)):
    if i<=j:ans+=1
if ans<=n/2:print('Snuke')
else:print('Fennec')

Solution (Python):
def dfs(x):
    d = [-1] * (N + 1)
    stack = [x]
    while stack:
        x = stack.pop()
        for i in G[x]:
            if d[i] == -1:
                d[i] = d[x] + 1
                stack.append(i)
    return d

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

d1, dn = dfs(1), dfs(N)
num = 0
for i in range(1, N + 1):
    if d1[i] <= dn[i]:
        num += 1
if num > N // 2:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())

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

from collections import deque
q = deque()
q.append(0)

d1 = [float('inf') for _ in range(n)]
d1[0] = 0
w = set()
while q:
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            d1[vv] = d1[v] + 1
            q.append(vv)


q = deque()
q.append(n-1)

dn = [float('inf') for _ in range(n)]
dn[n-1] = 0
w = set()
while q:
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            dn[vv] = dn[v] + 1
            q.append(vv)


d = [1 if d1[v] <= dn[v] else -1 for v in range(n)]

if sum(d) > 0:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1 << 30)

N = read()
edges = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = reads()
  a, b = a-1, b-1
  edges[a].append(b)
  edges[b].append(a)

def dist(u, d):
  for v in edges[u]:
    if d[v] >= 0:
      continue
    d[v] = d[u] + 1
    dist(v, d)
  return d

distf = dist(0, [0]+[-1]*(N-1))
dists = dist(N-1, [-1]*(N-1)+[0])

numf = sum(distf[i] <= dists[i] for i in range(N))
nums = N - numf

if numf > nums:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        visited.append(label)

        for v in d[label]:
            if tekazu[v] == float("inf"):
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

n = int(input())
d = [[] for _ in range(n)]

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

tekazu = [float("inf") for _ in range(n)]
tekazu[0] = 0
bfs(0)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)]
tekazu[-1] = 0
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

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

Solution (Python):
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        
        visited.append(label)

        for v in d[label]:
            if tekazu[v] == float("inf"):
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

n = int(input())
d = [[] for _ in range(n)]

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

tekazu = [float("inf") for _ in range(n)] 
tekazu[0] = 0
bfs(0)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] 
tekazu[-1] = 0
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1



if Fennec > Snuke:
    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())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
 
def bfs(v):
    q = []
    depth = [n]*n
    q.append(v)
    depth[v] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth
 
d1 = bfs(0)
d2 = bfs(n-1)
 
c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(2000000)
n = int(input())
p = []
for i in range(n-1):
    p.append(list(map(int, input().split()))+ [1])
l = [[] for i in range(n+1)]
for pi in p: 
    l[pi[0]].append([pi[0],pi[1]])
    l[pi[1]].append([pi[1],pi[0]])
kyo = [float("inf")]*(n+1)
kyo[1] = 0
memo = [0] * (n+1)
memo[1] = 1
ruto = []
def dfs(start,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    if memo[a[1]] == 1:
      continue
    kyo[a[1]] = kyo[a[0]] + 1
    dfs(a[1],ruto)
  return
dfs(1,ruto)

nkyo = [float("inf")]*(n+1)
nkyo[n] = 0
memo = [0] * (n+1)
memo[n] = 1
ruto = []
def dfs(start,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    if memo[a[1]] == 1:
      continue
    nkyo[a[1]] = nkyo[a[0]] + 1
    dfs(a[1],ruto)
  return
dfs(n,ruto)
iti = 0
nko = 0
for i in range(1,n+1):
  if kyo[i] <= nkyo[i]:
    iti += 1
  else:
    nko += 1
if iti <= nko:
  print("Snuke")
else:
  print("Fennec")

Solution (Python):
from collections import deque

N = int(input())

INF = 100001
G = [[] for i in range(N)]
dist1, dist2 = [INF for j in range(N)], [INF for k in range(N)]


def bfs(s, d):
    check, q = [0 for i in range(N)], deque()
    check[s], d[s] = 1, 0
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for i in G[u]:
            if check[i] == 0:
                check[i], d[i] = 1, d[u] + 1
                q.append(i)
        check[u] = 2


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

    bfs(0, dist1)
    bfs(N-1, dist2)

    cnt_f = 0
    for i in range(N):
        if dist1[i] <= dist2[i]:
            cnt_f += 1

    if N // 2 < cnt_f:
        print("Fennec")
    else:
        print("Snuke")


if __name__ == '__main__':
    main()

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

def bfs(v):
    q = []
    depth = [n]*n
    q.append(v)
    depth[v] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth

d1 = bfs(0)
d2 = bfs(n-1)

c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
def dfs(x):
	d,q = [-1 for i in range(n+1)],[x]
	d[x] = 0
	while q:
		x = q.pop()
		for i in r[x]:
			if d[i]==-1: d[i],q = d[x]+1,q+[i]
	return d
n = int(input())
x = [[int(i) for i in input().split()] for i in range(n-1)]
r = [[] for i in range(n+1)]
for i,j in x:
	r[i].append(j)
	r[j].append(i)
d1,dn,num = dfs(1),dfs(n),0
for i in range(1,n+1):
	if d1[i]<=dn[i]: num+=1
if num>n//2: print("Fennec")
else: print("Snuke")

Solution (Python):
N = int(input())
eda = {}
for i in range(1, N+1):
    eda[i] = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    eda[a].add(b)
    eda[b].add(a)
fennec = 0
snuke = 0
fenneccheck = set([1])
snukecheck = set([N])
checked = set([1, N])
while len(checked) < N:
    nextfennec = set()
    for i in fenneccheck:
        for j in eda[i]:
            if j in checked:
                continue
            checked.add(j)
            nextfennec.add(j)
            fennec += 1
    fenneccheck = nextfennec
    nextsnuke = set()
    for i in snukecheck:
        for j in eda[i]:
            if j in checked:
                continue
            checked.add(j)
            nextsnuke.add(j)
            snuke += 1
    snukecheck = nextsnuke
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

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

from collections import defaultdict

ns = defaultdict(list)

for a, b in ab:
    ns[a].append(b)
    ns[b].append(a)

from heapq import *

queue = []
heappush(queue, (0, 1))
heappush(queue, (1, N))

colors = defaultdict(lambda:None)
black_count, white_count = 0, 0

while queue:
    i, index = heappop(queue)
    color = i % 2
    if colors[index] is None:
        colors[index] = color
        if color:
            white_count += 1
        else:
            black_count += 1
        for t in ns[index]:
            if ns[t]:
                heappush(queue, (i + 2, t))

if black_count > white_count:
    print("Fennec")
else:
    print("Snuke")

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

ns = [[] for _ in range(N + 1)]

for a, b in ab:
    ns[a].append(b)
    ns[b].append(a)

from heapq import *

queue = []
heappush(queue, (0, 1))
heappush(queue, (1, N))

counts = [0, 0]

while queue:
    i, index = heappop(queue)
    if ns[index]:
        counts[i % 2] += 1
        for t in ns[index]:
            if ns[t]:
                heappush(queue, (i + 2, t))
    ns[index] = None

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

Solution (Python):
from collections import defaultdict

N=int(input())
M=defaultdict(list)

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

def bfs(s):
  res=[-1 for x in range(N)]
  res[s]=0
  queue=[s]
  while queue:
    np=queue.pop()
    for nx in M[np]:
      if res[nx]<0:
        res[nx]=res[np]+1
        queue.append(nx)
  return res

ans0=bfs(0)
ansN=bfs(N-1)
cnt=0
for i in range(N):
  if ans0[i]<=ansN[i]:
    cnt+=1
if cnt > N/2:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):

'''
深さ優先探索で解く
木構造で解く
'''


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

def dfs(v):
    d=[-1 for i in range(n)]
    q=[]
    d[v]=0
    q.append(v)
    while len(q):
        v=q.pop()

        for i in a[v]:
            if d[i]==-1:
                d[i]=d[v]+1
                q.append(i)
    return d
c1=dfs(0)
c2=dfs(n-1)
c=0
for i in range(n):
    if c1[i]>c2[i]:
        c+=1
if c>=n/2:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):

from collections import deque
def inpl(): return tuple(map(int, input().split()))

N = int(input())
G = [[] for i in range(N+1)]
for _ in range(N-1):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

F = ["" for i in range(N+1)]
S = ["" for i in range(N+1)]

visited = [False for i in range(N+1)]
Q = deque([(1, 0)])

while len(Q):
    m, d = Q.popleft()
    if visited[m]:
        continue
    else:
        F[m] = d
        visited[m] = True

    for nm in G[m]:
        Q.append((nm, d+1))

visited = [False for i in range(N+1)]
Q = deque([(N, 0)])

while len(Q):
    m, d = Q.popleft()
    if visited[m]:
        continue
    else:
        S[m] = d
        visited[m] = True

    for nm in G[m]:
        Q.append((nm, d+1))
    
black = 0    
for i in range(1, N+1):
    if F[i] <= S[i]:
        black += 1

if 2*black > N:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
def bfs(n, links):
    painted = set()
    queues = [{0}, {n - 1}]
    scores = [0, 0]
    i = 0
    while True:
        nq = set()
        for v in queues[i]:
            cq = links[v] - painted
            if cq:
                painted.update(cq)
                nq.update(cq)
        queues[i] = nq
        scores[i] += len(nq)
        if not nq:
            scores[i ^ 1] = n - scores[i]
            break
        i ^= 1
    return scores[0] > scores[1]


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('Fennec' if bfs(n, links) else 'Snuke')

Solution (Python):
def bfs(n, links):
    painted = set()
    fq = {0}
    sq = {n - 1}
    fs, ss = 0, 0
    while True:
        nfq, nsq = set(), set()
        for v in fq:
            cfq = links[v] - painted
            if cfq:
                fs += len(cfq)
                painted.update(cfq)
                nfq.update(cfq)
        fq = nfq
        for v in sq:
            csq = links[v] - painted
            if csq:
                ss += len(csq)
                painted.update(csq)
                nsq.update(csq)
        sq = nsq
        if not fq:
            ss = n - fs
            break
        if not sq:
            fs = n - ss
            break
    return fs > ss


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('Fennec' if bfs(n, links) else 'Snuke')

Solution (Python):
n = int(input())
node = [[] for i in range(n)]

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

def dfs(v):
    dis = [10 ** 10] * n
    dis[v] = 0
    q = []
    q.append(v)

    while q:
        u = q.pop()
        for i in node[u]:
            if dis[i] > dis[u] + 1:
                dis[i] = dis[u] + 1
                q.append(i)

    return dis

d1 = dfs(0)
d2 = dfs(n - 1)

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

if c > (n - 2) // 2:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,[1,n]);print['Snuke','Fennec'][sum(g[i]>h[i]for i in range(n+1))*2<n]

Solution (Python):

from collections import Counter

N = int(input())
graph =[[] for _ in range(N + 1)]
visited = [None] * (N + 1)

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

v = 1
adv_v = N
update = True
labels = [0, 1]
vs = [v, adv_v]
prev_vs = [-1, -1]
visited[1] = 0
visited[N] = 1
while update:
    update = False
    next_cand = []

    for label, v, prev_v in zip(labels, vs, prev_vs):
        for next_v in graph[v]:
            if next_v == prev_v:
                continue
            if (visited[next_v] is None):
                update = True
                next_cand.append((next_v, label, v))

    vs = []
    labels = []
    prev_vs = []
    for next_v, label, prev_v in next_cand:
        if visited[next_v] is None:
            visited[next_v] = label
            vs.append(next_v)
            prev_vs.append(prev_v)
            labels.append(label)


c = Counter(visited)
if c[0] > c[1]:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))
 
import copy
 
N = ri()
relation = [[] for _ in range(N+1)]
dist = [[0 for i in range(N+1)] for j in range(2)]
for i in range(N-1):
    a,b = rli()
    relation[a].append(b)
    relation[b].append(a)
 
def dfs_visit(u):
    start = u
    rel = copy.deepcopy(relation)
    s = []
    color = [-1 for _ in range(N+1)]
    s.append(u)
    color[u] = 0
    while(s != list()):
        u = s[-1]
        try:
            v = rel[u].pop()
        except IndexError:
            dist[0 if start == 1 else 1][s[-1]] = len(s)
            s.pop()
            color[u] = 1
            continue
        if(color[v] == -1):
            color[v] = 0
            s.append(v)
 
def dfs():
    dfs_visit(1)
    dfs_visit(N)
 
dfs()
fe = 0
sn = 0
 
for i in range(1, N+1):
    if(dist[0][i] <= dist[1][i]):
        fe += 1
    else:
        sn += 1
print("Fennec" if fe > sn else "Snuke")

Solution (Python):
import sys
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class mas_node():
    def __init__(self, now_number, pass_route):
        self.now_number = now_number
        self.pass_route = set(pass_route)
        self.pass_route.add(now_number)

    def set_now_number(self, now_number):
        self.now_number = now_number
        self.pass_route.add(now_number)

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]

    adj_list = {}
    for i in range(N):
        adj_list[i + 1] = []

    for i in range(N - 1):
        input_raw = list(read_func().strip().split())
        adj_list[int(input_raw[0])].append(int(input_raw[1]))
        adj_list[int(input_raw[1])].append(int(input_raw[0]))


    
    is_already_pass = [False] * N
    is_already_pass[0] = True
    node_list = [1]
    count = 0
    while 1:
        
        
        
        m_node = node_list[len(node_list) - 1]
        is_already_pass[m_node - 1] = True
        is_leaf_node = True
        if m_node == N:
            break;
        for next_node in adj_list[m_node]:
            if is_already_pass[next_node - 1] == False:
                is_leaf_node = False
                node_list.append(next_node)
        if is_leaf_node == True:
            node_list.pop()
        if len(node_list) == 0:
            break;

    to_N_pass_route = deque([])
    for i in range(len(node_list)):
        if is_already_pass[node_list[i] - 1] == True:
            to_N_pass_route.append(node_list[i])


    to_N_pass_route.popleft()
    to_N_pass_route.pop()
    already_colored_list = [False] * N
    mas_set = {}
    mas_set["b"] = [1]
    mas_set["w"] = [N]
    pass_len = len(to_N_pass_route)

    
    for i in range(pass_len):
        if len(to_N_pass_route) == 0:
            break;
        b = to_N_pass_route.popleft()
        already_colored_list[b - 1] = True
        mas_set["b"].append(b)
        if len(to_N_pass_route) == 0:
            break;
        w = to_N_pass_route.pop()
        already_colored_list[w - 1] = True
        mas_set["w"].append(w)

    black_mas_node = copy.deepcopy(mas_set["b"])
    white_mas_node = copy.deepcopy(mas_set["w"])
    while 1:
        new_black_mas_node = []
        for b_mas in black_mas_node:
            for next_b_mas in adj_list[b_mas]:
                if already_colored_list[next_b_mas - 1] == False:
                    mas_set['b'].append(next_b_mas)
                    new_black_mas_node.append(next_b_mas)
                    already_colored_list[next_b_mas - 1] = True
        black_mas_node = copy.deepcopy(new_black_mas_node)

        new_white_mas_node = []
        for w_mas in white_mas_node:
            for next_w_mas in adj_list[w_mas]:
                if already_colored_list[next_w_mas - 1] == False:
                    mas_set['w'].append(next_w_mas)
                    new_white_mas_node.append(next_w_mas)
                    already_colored_list[next_w_mas - 1] = True
        white_mas_node = copy.deepcopy(new_white_mas_node)

        if len(white_mas_node) == 0 & len(black_mas_node) == 0:
            break;

    if len(mas_set['b']) > len(mas_set['w']):
        print "Fennec"
    else:
        print "Snuke"



if __name__ == '__main__':
    main()

Solution (Python):
def black(now):
    nextb=[]
    while now:
        a=now.pop()
        while desn[a]:
            go=desn[a].pop()
            if nodes[go]=='N':
                nodes[go]='B'
                nextb.append(go)
    return nextb

def white(now):
    nextb=[]
    while now:
        a=now.pop()
        while desn[a]:
            go=desn[a].pop()
            if nodes[go]=='N':
                nodes[go]='W'
                nextb.append(go)
    return nextb

n = int(input())
nodes=[]
desn=[]
for i in range(0,n+1):
    nodes.append("N")
    desn.append([])
nodes[1]='B'
nodes[n]='W'
for i in range(0,n-1):
    b, c = (int(i) for i in input().split())
    desn[b].append(c)
    desn[c].append(b)

nowb=[1]
noww=[n]
while nowb or noww:
    nowb=black(nowb)
    noww=white(noww)

b=nodes.count('B')
w=nodes.count('W')
if b>w:
    print('Fennec')
else:
    print('Snuke')