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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


ans=0

n=I()
g,c=GI(n,n-1)


v=[-1]*n
v[0]=1
v[n-1]=0

def dfs(x,s):
    r=[]
    for i in x:
        for nb in g[i]:
            if v[nb]==-1:
                r.append(nb)
                v[nb]=s
    return r

F=[0]
S=[n-1]
while F or S:
    F=dfs(F,1)

    S=dfs(S,0)


if sum(v)>n//2:
    ans='Fennec'
else:
    ans='Snuke'
    
print(ans)

Solution (Python):

n=int(input())
tree_list={i:[] for i  in range(1,n+1)}
for i  in range(n-1):
    a,b=map(int,input().split())
    tree_list[a].append(b)
    tree_list[b].append(a)
painted=[False for i in range(n+1)]
painted[1]="black"
painted[n]="white"
from collections import deque
d_white=deque()
e_white=deque()

d_black=deque()
e_black=deque()

d_black.append(1)
d_white.append(n)

while(d_black or d_white):
    for some in d_black:
        for point in tree_list[some]:
            if painted[point]==False:
                painted[point]="black"
                e_black.append(point)
    d_black=e_black
    e_black=deque()
    
    for some in d_white:
        for point in tree_list[some]:
            if painted[point]==False:
                painted[point]="white"
                e_white.append(point)
    d_white=e_white
    e_white=deque()
sunke=0
fennec=0
for i in range(1,n+1):
  if painted[i]=="white":
    sunke+=1
  elif painted[i]=="black":
    fennec+=1
if fennec>sunke:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
import sys
input = sys.stdin.readline
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)
from collections import deque
que=deque()
que.append(0)
unvisited=[1]*n
unvisited[0]=0
lf=[0]*n
while que:
    v=que.pop()
    for u in g[v]:
        if unvisited[u]:
            lf[u]=lf[v]+1
            que.appendleft(u)
            unvisited[u]=0
que=deque()
que.append(n-1)
unvisited=[1]*n
unvisited[n-1]=0
ls=[0]*n
while que:
    v=que.pop()
    for u in g[v]:
        if unvisited[u]:
            ls[u]=ls[v]+1
            que.appendleft(u)
            unvisited[u]=0
f=0
for i in range(n):
    if lf[i]<=ls[i]:
        f+=1
if f>n-f:
    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, 1))
    edges[b].append((a, 1))

dists1 = [float('inf') for _ in range(N)]
used = [False for _ in range(N)]
dists1[0] = 0
used[0] = True

buf = [0]
while buf:
    src = buf.pop()
    for dst, w in edges[src]:
        if not used[dst]:
            dists1[dst] = dists1[src] + w
            used[dst] = True
            buf.append(dst)

dists2 = [float('inf') for _ in range(N)]
used = [False for _ in range(N)]
dists2[N - 1] = 0
used[N - 1] = True

buf = [N - 1]
while buf:
    src = buf.pop()
    for dst, w in edges[src]:
        if not used[dst]:
            dists2[dst] = dists2[src] + w
            used[dst] = True
            buf.append(dst)

num1, num2 = 0, 0
for d1, d2 in zip(dists1, dists2):
    if d1 <= d2:
        num1 += 1
    elif d1 > d2:
        num2 += 1

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

Solution (Python):
from collections import deque

def bfs(graph, stack, visited, times):
    cnt = 0
    while stack:
        a,cost = stack.popleft()
        if cost > times:
            stack.appendleft([a,cost])
            break
        for b in graph[a].keys():
            if not visited[b]:
                stack.append([b,cost+1])
                visited[b] += 1 
                cnt += 1
    return cnt

def bi_bfs(graph, start, goal):
    s_stack, g_stack = deque(), deque()
    s_stack.append([start,0])
    g_stack.append([goal, 0])
    visited = [0 for i in range(N+1)]
    visited[start] = visited[goal] = 1 
    s_cnt = g_cnt = 1
    times = 0

    while s_stack or g_stack:
        s_cnt += bfs(graph, s_stack, visited, times)
        g_cnt += bfs(graph, g_stack, visited, times)
        times += 1
    return s_cnt > g_cnt

N = int(input())
graph = {}
for i in range(N-1):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
print('Fennec' if bi_bfs(graph,1,N) else 'Snuke')

Solution (Python):
from collections import deque

def bfs(graph, start, goal):
    s_stack = deque()
    g_stack = deque()
    visited = [0 for i in range(N+1)]
    s_stack.append([start,0])
    g_stack.append([goal, 0])
    visited[start] = 1 
    visited[goal] = 1 
    s_cnt = 1
    g_cnt = 1
    round = 0
    while s_stack or g_stack:
        while s_stack:
            a,cost = s_stack.popleft()
            if cost > round:
                s_stack.appendleft([a,cost])
                break
            for b in graph[a].keys():
                if not visited[b]:
                    s_stack.append([b,cost+1])
                    visited[b] += 1 
                    s_cnt += 1
        while g_stack:
            a, cost = g_stack.popleft()
            if cost > round:
                g_stack.appendleft([a,cost])
                break
            for b in graph[a].keys():
                if not visited[b]:
                    g_stack.append([b,cost+1])
                    visited[b] += 1 
                    g_cnt += 1
        round += 1
    
    
    return s_cnt > g_cnt

N = int(input())
graph = {i:{} for i in range(1,N+1)}
for i in range(N-1):
    a,b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1
print('Fennec' if bfs(graph,1,N) else 'Snuke')

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みなし) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c = stack.pop()
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                stack.append((v, u, c+1))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)


res1 = dfs(N, nodes, 0)
res2 = dfs(N, nodes, N-1)

cnt = 0
for i in range(N):
    
    if res1[i] <= res2[i]:
        cnt += 1

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

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  distB = [0]*n
  distW = [0]*n
  def dfs(v, seen, dist):
    seen[v] = True
    for nv in F[v]:
      if seen[nv]:
        continue
      dist[nv] = dist[v] + 1
      dfs(nv, seen, dist)
  dfs(0, seenB, distB)
  dfs(n-1, seenW, distW)
  b, w = 0, 0
  for i in range(n):
    if distB[i] <= distW[i]:
      b += 1
    else:
      w += 1
  if b > w:
    print("Fennec")
  else:
    print("Snuke")
      
if __name__ == '__main__':
  main()

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

graph = [[] for _ in range(N + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)

def dfs(n):
  INF = 10 ** 10
  dist = [INF] * (N + 1)

  stack = [n]
  dist[n] = 0
  while stack:
    s = stack.pop()
    for g in graph[s]:
      if dist[s] + 1 < dist[g]:
        stack.append(g)
        dist[g] = dist[s] + 1
  return dist

dist_f = dfs(1)
dist_a = dfs(N)
D = dist_f[N]



f_cnt = 0
a_cnt = 0

color = [0] * (N + 1)
color[1] = 1
color[N] = -1

for i in range(1, N + 1):
  if dist_f[i] <= D // 2:
    if color[i] == 0:
      f_cnt += 1
      color[i] = 1
  if dist_a [i] <= (D - 1) // 2:
    if color[i] == 0:
      a_cnt += 1
      color[i] = -1



def paint(n):
  cnt = 0
  for i in range(1, N + 1):
    if color[i] == n:
      stack = [i]
      while stack:
        s = stack.pop()
        for g in graph[s]:
          if color[g] == 0:
            stack.append(g)
            color[g] = n
            cnt += 1
  return cnt

f_cnt += paint(1)
a_cnt += paint(-1)

if f_cnt >= a_cnt + 1:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
import sys

n, *ab = map(int, sys.stdin.read().split())
graph = [[]for _ in range(n+1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    stack = [v]
    dist = [None] * (n + 1)
    dist[v] = 0
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist

def main():
    dist_1 = dfs(1)
    dist_n = dfs(n)
    black_cnt = 0
    for i in range(1, n+1):
        if dist_1[i] <= dist_n[i]:
            black_cnt += 1

    if black_cnt <= n // 2:
        return 'Snuke'
    else:
        return 'Fennec'

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

Solution (Python):
n = int(input())
g = [[] for _ 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)
s = [0]
d1 = [-1] * n
d1[0] = 0
while s:
    d = s.pop()
    for node in g[d]:
        if d1[node] == -1:
            s.append(node)
            d1[node] = d1[d] + 1
s = [n - 1]
d2 = [-1] * n
d2[n - 1] = 0
while s:
    d = s.pop()
    for node in g[d]:
        if d2[node] == -1:
            s.append(node)
            d2[node] = d2[d] + 1
f, s = 0, 0
for i in range(n):
    if d1[i] <= d2[i]:
        f += 1
    else:
        s += 1
if f > s:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import deque

def dfs(si, ei):
  q = deque()
  q.append([si,0])
  done = set([si])
  ds = [0 for _ in range(N)]
  while len(q) > 0:
    prvi, d = q.pop()
    for i in g[prvi]:
      if i in done: continue
      ds[i] = d+1
      q.append([i,d+1])
      done.add(i)
  return ds

N = int(input())
g = {i:[] for i 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)

dslist = dfs(0,N-1)
delist = dfs(N-1,0)

cntb, cntw = 0, 0
for ds, de in zip(dslist[1:N-1], delist[1:N-1]):
  if ds <= de: cntb += 1
  else: cntw += 1
print('Fennec' if cntb>cntw else 'Snuke')

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

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

DF = [None]*N
DF[0] = 0
queue = [0]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if DF[e] is not None: continue
            DF[e] = DF[q]+1
            queue_new.append(e)
    queue = queue_new

DS = [None]*N
DS[N-1] = 0
queue = [N-1]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if DS[e] is not None: continue
            DS[e] = DS[q]+1
            queue_new.append(e)
    queue = queue_new
    
NF, NS = 0, 0
for df, ds in zip(DF,DS):
    if df<=ds: NF+=1
    else: NS+=1

print('Fennec' if NF>NS else 'Snuke')

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

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

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

Fennec = np.count_nonzero(d1 <= dn)

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

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

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

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

Fennec = np.count_nonzero(d1 <= dn)

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

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

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

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

Fennec = -1
for i, j in zip(d1, dn):
    if i <= j:
        Fennec += 1

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

Solution (Python):
def d_fennec_vs_snuke():
    from collections import deque
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    graph = [[] for _ in range(N)]
    for a, b in Edges:
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    def bfs(start, tree_size=N, tree=graph):
        """木のある頂点 start からの距離を求める (start は 0-origin)"""
        dist = [0] * tree_size
        is_visited = [False] * tree_size
        is_visited[start] = True

        queue = deque([start])
        while queue:
            current = queue.pop()
            for child in tree[current]:
                if is_visited[child]:
                    continue
                is_visited[child] = True
                dist[child] = dist[current] + 1
                queue.appendleft(child)
        return dist

    fennec_dist, snuke_dist = bfs(0), bfs(N - 1)
    fennec_point, snuke_point = 0, 0  

    for fennec, snuke in zip(fennec_dist, snuke_dist):
        if fennec <= snuke:
            fennec_point += 1
        else:
            snuke_point += 1
    return 'Fennec' if fennec_point > snuke_point else 'Snuke'

print(d_fennec_vs_snuke())

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


def dfs_f(now, kyori):
    kyori_f[now] = kyori
    
    for next in g[now]:
        
        if not memo_f[next] and next != n - 1:
            memo_f[next] = True
            dfs_f(next, kyori + 1)


def dfs_s(now, kyori):
    kyori_s[now] = kyori
    
    for next in g[now]:
        
        if not memo_s[next] and next != 0:
            memo_s[next] = True
            dfs_s(next, kyori + 1)


n = int(input())
g = [[] * n for i in range(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)


memo_f = [False for i in range(n)]  
kyori_f = [float("inf") for i in range(n)]  
memo_f[0] = True
dfs_f(0, 0)


memo_s = [False for i in range(n)]  
kyori_s = [float("inf") for i in range(n)]  
memo_s[n - 1] = True
dfs_s(n - 1, 0)

black = 0
white = 0
for i in range(n):
    if kyori_f[i] <= kyori_s[i]:
        black += 1
    else:
        white += 1

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())

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

def BFS(n, E, i0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

A = BFS(N, X, 0)
B = BFS(N, X, N-1)
print("Snuke" if sum([A[i] <= B[i] for i in range(N)]) * 2 <= N else "Fennec")

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

n = int(input())
graph = {i : [] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

stack = [0]
already = set()
parent = [i for i in range(n)]
flg = False
while len(stack) > 0:
    cur = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next not in already:
            stack.append(_next)
            parent[_next] = cur
            if _next == n - 1:
                flg = True
                break
    if flg:
        break

path = []
cur = n - 1
while cur != 0:
    path.append(cur)
    cur = parent[cur]
path.append(0)
path.reverse()
flg_2 = len(path) % 2 != 0
left = path[len(path) // 2 - 1 + flg_2]
right = path[len(path) // 2 + flg_2]

def dfs(x, last):
    res = 1
    for _next in graph[x]:
        if _next != last:
           res += dfs(_next, x)
    return res

left_res = dfs(left, right)

print("Fennec" if left_res > (n - left_res) else "Snuke")

Solution (Python):
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline

    N = int(input())

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

    check = [0] * (N + 1)
    que1 = deque() 
    que2 = deque() 

    que1.append(1)
    que2.append(N)

    check[1] = 1
    check[N] = 1

    fennec = 0
    snuke = 0

    flag = True

    while flag:
        flag = False

        tmp_lst = []
        while len(que1) != 0:
            flag = True
            tmp = que1.popleft()
            for next_ in graph[tmp]:
                if check[next_] == 0:
                    tmp_lst.append(next_)
                    fennec += 1
                    check[next_] = 1
        for i in tmp_lst:
            que1.append(i)
        
        tmp_lst = []
        while len(que2) != 0:
            flag = True
            tmp = que2.popleft()
            for next_ in graph[tmp]:
                if check[next_] == 0:
                    tmp_lst.append(next_)
                    snuke += 1
                    check[next_] = 1
        for i in tmp_lst:
            que2.append(i)

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

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

check = [0] * (N + 1)
que1 = deque() 
que2 = deque() 

que1.append(1)
que2.append(N)

check[1] = 1
check[N] = 1

fennec = 0
snuke = 0

flag = True

while flag:
    flag = False

    tmp_lst = []
    while len(que1) != 0:
        flag = True
        tmp = que1.popleft()
        for next_ in graph[tmp]:
            if check[next_] == 0:
                tmp_lst.append(next_)
                fennec += 1
                check[next_] = 1
    for i in tmp_lst:
        que1.append(i)
    
    tmp_lst = []
    while len(que2) != 0:
        flag = True
        tmp = que2.popleft()
        for next_ in graph[tmp]:
            if check[next_] == 0:
                tmp_lst.append(next_)
                snuke += 1
                check[next_] = 1
    for i in tmp_lst:
        que2.append(i)

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

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

F=[0]*N
S=[0]*N

stack=[]

stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]

stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

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

Solution (Python):
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)
res=[0]*n
res[0]=1
res[n-1]=-1
q=[0,n-1]
while q:
    qq=[]
    for i in q:
        v=res[i]
        for j in g[i]:
            if not res[j]:
                res[j]=v
                qq.append(j)
    q=qq
if sum(res)>0:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)

    
    path=[]
    def dfs(v,p=-1)->bool:
        if(v==n-1):
            path.append(v)
            return True
        for nv in E[v]:
            if(nv==p): continue
            if(dfs(nv,v)):
                path.append(v)
                return True
        return False
    dfs(0)
    path.reverse()
    k=len(path)
    a,b=path[(k+1)//2-1],path[(k+1)//2]

    
    E[a].remove(b)
    E[b].remove(a)

    
    from collections import deque
    Q=deque([0])
    visited=[0]*n
    while(Q):
        v=Q.popleft()
        visited[v]=1
        for nv in E[v]:
            if(visited[nv]): continue
            Q.append(nv)

    c=sum(visited)
    print("Fennec" if(c>n-c) else "Snuke")
resolve()

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
d1 = [float("inf")] * (N + 1)
d1[1] = 0
Q = dq([])
Q.append(1)
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if d1[q] > d1[p] + 1:
      d1[q] = d1[p] + 1
      Q.append(q)
dn = [float("inf")] * (N + 1)
dn[N] = 0
Q.append(N)
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if dn[q] > dn[p] + 1:
      dn[q] = dn[p] + 1
      Q.append(q)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N=int(input())
ab=[[] for _ in range(N)]
for _ in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)
"""
N=10**5
ab=[[]]*N
ab[0]=[2]
ab[N-1]=[N-1]
for i in range(1,N-1):
  ab[i]=[i,i+2]
"""
par=[0]*N
  
def dfs(pre,p):
  global path
  par[p-1]=pre
  if p==N:
    pass
  else:
    for i in ab[p-1]:
      if i!=pre:
        dfs(p,i)

dfs(-1,1)
path=[N]
p=N
while p!=1:
  p=par[p-1]
  path.append(p)
path.reverse()

spath=set(path)

def dfs2(pre,p):
  a=0
  for i in ab[p-1]:
    if i in spath:
      pass
    elif i==pre:
      pass
    else:
      a+=dfs2(p,i)
  return 1+a

ff=0
sf=0
L=len(path)
for i in range(L):
  if i<=(L-1)//2:
    ff+=dfs2(-1,path[i])
  else:
    sf+=dfs2(-1,path[i])
    
if ff>sf:
  print("Fennec")
else:
  print("Snuke")

Solution (Python):
from collections import deque

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    
q = deque()
q.append(0)
parents = [-1]*N
parents[0] = -2
while q:
    t = q.popleft()
    for i in E[t]:
        if parents[i] == -1:
            parents[i] = t
            q.append(i)
    if parents[N-1] >= 0:
        break

q_snuke = deque()
q_snuke.append(N-1)
idx = N-1
used = [0]*N
used[0] = 1
cnt = 0
while parents[idx] >= 0:
    q_snuke.append(parents[idx])
    idx = parents[idx]
    used[idx] = 1

n = len(q_snuke)
for _ in range(n//2+(n%2)):
    q_snuke.pop()
    

while q_snuke:
    t = q_snuke.popleft()
    for i in E[t]:
        if used[i] == 0:
            used[i] = 1
            q_snuke.append(i)

s = sum(used) - (n//2+(n%2))
if s >= N-s or N == 2:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
def bfs(n,e,fordfs):
    
    W = [-1]*n
    
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                
                return -1
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return len

def examD():
    N = I()
    v = [[] for i in range(N)]
    for i in range(N-1):
        a, b = LI()
        v[a-1].append(b-1)
        v[b-1].append(a-1)
    fennec = bfs(N,0,v)
    snuke = bfs(N,N-1,v)
    cur = 0
    for i in range(N):
        if fennec[i]>snuke[i]:
            cur +=1
    if cur>=(N+1)//2:
        ans = "Snuke"
    else:
        ans = "Fennec"
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
from collections import deque

n = int(input())
node_data = [[] for i in range(n+1)]
node_stuck = deque([])
Fennec = [0] * (n+1)
Snuke = [0] * (n+1)
for i in range(n-1):
    x, y = list(map(int, input().split()))
    node_data[x].append(y)
    node_data[y].append(x)
node_stuck.append([1,0])
finished = set()

while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Fennec[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count+1])
node_stuck.append([n,0])
finished = set()
while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Snuke[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count + 1]) 
f = 0
s = 0


for i in range(2, n):
    if Fennec[i] <= Snuke[i]:
        f += 1
    else:
        s += 1

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

Solution (Python):
from collections import deque

def dfs(si, ei):
  q = deque()
  q.append([si,0])
  done = set([si])
  ds = [0 for _ in range(N)]
  while len(q) > 0:
    prvi, d = q.pop()
    for i in g[prvi]:
      if i in done: continue
      ds[i] = d+1
      q.append([i,d+1])
      done.add(i)
  return ds

N = int(input())
g = {i:[] for i 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)

dslist = dfs(0,N-1)
delist = dfs(N-1,0)

cntb, cntw = 0, 0
for ds, de in zip(dslist[1:N-1], delist[1:N-1]):
  if ds <= de: cntb += 1
  else: cntw += 1
print('Fennec' if cntb>cntw else 'Snuke')

Solution (Python):
import itertools
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
N = int(input())
E = {i:[] for i in range(N+1)}
for i in range(N-1):
    a,b= inputs()
    E[a].append(b)
    E[b].append(a)
stkf = [[1,-1,0]]
visitedf=[0]*(N+1)
visiteds=[0]*(N+1)
stks = [[N,-1,0]]
cntf=0
cnts=0
while stkf:
    v,p,cost=stkf.pop()
    if v==N:
        visitedf[N]=cost
        continue
    visitedf[v]=cost
    cntf+=1
    for i in E[v]:
        if i!=p:
            stkf.append([i,v,cost+1])
while stks:
    v,p,cost=stks.pop()
    if v==1:
        visiteds[1]=cost
        continue
    visiteds[v]=cost
    cnts+=1
    for i in E[v]:
        if i!=p:
            stks.append([i,v,cost+1])
for i in range(1,N+1):
  if visitedf[i] and visiteds[i]:
    if visitedf[i]<=visiteds[i]:
      cnts-=1
    else:
      cntf-=1

"""
if (visitedf[N]-1)%2!=0:
  cntf=cntf-1-(visitedf[N]-1)//2
  cnts=cnts-1-(visitedf[N]-1)//2-1
else:
  cntf=cntf-1-(visitedf[N]-1)//2
  cnts=cnts-1-(visitedf[N]-1)//2
"""
print("Fennec" if cntf>cnts else "Snuke")