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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
n=int(input())
edges=[[] for _ in range(n)]
dist=[0]*n
for i in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  edges[u].append(v)
  edges[v].append(u)
dist=[ [0]*n for _ in range(2)]

def dfs(u,p,idd):
  for nei in edges[u]:
    if nei==p:
      continue
    dist[idd][nei]=1+dist[idd][u]
    dfs(nei,u,idd)
dist[0][0]=0
dfs(0,0,0)
dist[1][n-1]=0
dfs(n-1,n-1,1)
cnt_f=cnt_s=0
for i in range(n):
  if dist[0][i]<=dist[1][i]:
    cnt_f+=1
  else:
    cnt_s+=1
print("Fennec") if cnt_f>cnt_s else print("Snuke")

Solution (Python):
from collections import deque
N = int(input())
path = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)

steps = [-99 for _ in range(N)]
steps[0] = 0
isVisited = [False for _ in range(N)]
toSearch = deque([0, ])
isVisited[0] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    nowStep = steps[nowP]
    if nowP == N-1:
        break
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
            steps[nextP] = nowStep + 1

fennecLength = ((nowStep-1)+1)//2

snukePoint = 0
isVisited = [False for _ in range(N)]
toSearch = deque([N-1, ])
isVisited[N-1] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    snukePoint += 1
    nowStep = steps[nowP]
    
    if nowStep == fennecLength:
        snukePoint -= 1
        continue
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
if snukePoint >= (N+1)//2:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
from collections import deque
N = int(input())
adj = [[] for i in range(N)]


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


dq = deque([(0, 'b'), (N-1, 'w')])

colors = [0] * N
colors[0] = 'b'
colors[-1] = 'w'


while dq:
    node, color = dq.popleft()
    for dest in adj[node]:
        if colors[dest] != 0:
            continue
        else:
            colors[dest] = color
            dq.append((dest, color))

print('Fennec' if colors.count('b') > N//2 else 'Snuke')

Solution (Python):
from collections import deque
N = int(input())
adj = [[] for i in range(N)]


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


dq = deque([(0, 1), (N-1, 2)])

colors = [0] * N
colors[0] = 1
colors[-1] = 2


while dq:
    node, color = dq.popleft()
    for dest in adj[node]:
        if colors[dest] != 0:
            continue
        else:
            colors[dest] = color
            dq.append((dest, color))

print('Fennec' if colors.count(1) > N//2 else 'Snuke')

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    dL=[[0,0] for _ in range(N)]
    
    q=queue.Queue()
    
    
    for j in range(2):
        if j==0:
            q.put((0,0,0))
        else:
            q.put((N-1,N-1,0))
        while not q.empty():
            v,p,d=q.get()
            dL[v][j]=d
            for i in range(len(adj[v])):
                nv=adj[v][i]
                if nv!=p:
                    q.put((nv,v,d+1))
                    
    s=0
    for i in range(N):
        if dL[i][0]>dL[i][1]:
            s+=1
    
        
    
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    bit=[-1]*N
    bit[0]=0
    bit[-1]=1
    pL=[0]*N
    dS=0
    
    q=queue.Queue()
    q.put((0,0,0))
    
    
    while not q.empty():
        v,p,d=q.get()
        pL[v]=p
        if v==N-1:
            dS=d
            break
        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v,d+1))
    
    
    v=N-1            
    for _ in range((dS-1)//2):
        v=pL[v]
        bit[v]=1
        
    q2=queue.Queue()
    q2.put((0,0))
    while not q2.empty():
        v,p=q2.get()
        if bit[v]==-1:
            bit[v]=bit[p]

        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q2.put((nv,v))
        
        
                    
    s=sum(bit)
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()

Solution (Python):
import numpy as np
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)


def dist_from_X(X:int):
    dist = np.full(N, -1)
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for e in E[v]:
            if dist[e] > -1:
                continue
            dist[e] = d + 1
            que.append(e)
    return dist

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

cnt = np.count_nonzero(Fennec <= Sunuke)

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

Solution (Python):
from collections import deque

n = int(input())
Tree_dict = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    if a in Tree_dict.keys():
        Tree_dict[a].append(b)
    else:
        Tree_dict.update({a:[b]})
    if b in Tree_dict.keys():
        Tree_dict[b].append(a)
    else:
        Tree_dict.update({b:[a]})

deque = deque()
deque.append(1)

Visited_one = [-1 for _ in range(n+1)]
Visited_one[1] = 0

while deque:
    node = deque.popleft()
    next_nodes = Tree_dict[node]
    for next_node in next_nodes:
        if Visited_one[next_node] != -1:
            continue
        else:
            Visited_one[next_node] = Visited_one[node] + 1
            deque.append(next_node)


deque.append(n)

Visited_n = [-1 for _ in range(n+1)]
Visited_n[n] = 0

while deque:
    node = deque.popleft()
    next_nodes = Tree_dict[node]
    for next_node in next_nodes:
        if Visited_n[next_node] != -1:
            continue
        else:
            Visited_n[next_node] = Visited_n[node] + 1
            deque.append(next_node)




fen = 0
snu = 0

for i in range(1,n+1):
    if Visited_n[i] >= Visited_one[i]:
        fen += 1
    else:
        snu += 1

if fen > snu:
    ans = 'Fennec'
else:
    ans = 'Snuke'
print(ans)

Solution (Python):



from collections import deque
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)

dist_f=[-1]*n
dist_s=[-1]*n
dist_f[0]=0
dist_s[n-1]=0

q = deque()
q.append(0)
while q:
    x = q.popleft()
    for nx in G[x]:
        if dist_f[nx] == -1:
            q.append(nx)
            dist_f[nx]=dist_f[x]+1
 
q = deque()
q.append(n-1)
while q:
    x = q.popleft()
    for nx in G[x]:
        if dist_s[nx] == -1:
            q.append(nx)
            dist_s[nx]=dist_s[x]+1
f,s=0,0
for i in range(n):
    if dist_f[i]<=dist_s[i]:
        f+=1
    else:
        s+=1
if f>s:
    print('Fennec')
else:
    print('Snuke')

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


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


def dfs(v, dist):
    for u in G[v]:
        if dist[u] != -1:
            continue
        dist[u] = dist[v] + 1
        ret = dfs(u, dist)


dist_fen = [-1] * N
dist_fen[0] = 0
dfs(0, dist_fen)

dist_snu = [-1] * N
dist_snu[N-1] = 0
dfs(N-1, dist_snu)

fen = 0
for v in range(N):
    if dist_fen[v] <= dist_snu[v]:
        fen += 1
if fen > N // 2:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)

    def bfs(start):
        q = [start]
        d = [inf]*N
        d[start] = 0
        for i in range(N):
            tmp = []
            while q:
                v = q.pop()
                for to in edge[v]:
                    if d[to]==inf:
                        tmp.append(to)
                        d[to] = i+1
            q = tmp
        return d        
    
    fennec = bfs(0)
    snuke = bfs(N-1)

    f,s = 0,0
    for i in range(N):
        if fennec[i]<=snuke[i]:
            f+=1
        else:
            s+=1
    if f>s:
        print("Fennec")
    else:
        print("Snuke")

    

if __name__ == '__main__':
    main()

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

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

dp0 = [0 for i in range(n)]
dp1 = [0 for i in range(n)]

dp0[0] = 1
dp1[-1] = 1

for i in range(n-1):
    o,p = m()
    o -= 1
    p -= 1
    tree[o].append(p)
    tree[p].append(o)

de = cl.deque([0,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp0[i] == 0:
            dp0[i] = co
            de.append(i)

de = cl.deque([n-1,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp1[i] == 0:
            dp1[i] = co
            de.append(i)

dp0[0] = 0
dp1[-1] = 0

co = 0

for i in range(n):
    co += 1 if dp0[i] - dp1[i] <= 0 else -1
if co > 0:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
n = int(input())
g = [[] for _ 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)


from collections import deque
q = deque()
visit = [-1]*n
q.append(0)
visit[0] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if visit[new_x] != -1:
            continue
        visit[new_x] = visit[x]+1
        q.append(new_x)
        
            


q = deque()
visit2 = [-1]*n
q.append(n-1)
visit2[n-1] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if visit2[new_x] != -1:
            continue
        visit2[new_x] = visit2[x]+1
        q.append(new_x)


fe = 0
sn = 0
for i in range(n):
    if visit[i] <= visit2[i]:
        fe += 1
    else:
        sn += 1
if fe > sn:
    print('Fennec')
else:
    print('Snuke')

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

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)


def dist(root):  
    res = [-1] * (N + 1)
    node = [root]
    res[root] = 0
    while node:
        s = node.pop()
        d = res[s]
        for t in edge[s]:
            if res[t] == -1:
                node.append(t)
                res[t] = d + 1
    return res[1:]


fenek = dist(1)
snuke = dist(N)
f, s = 0, 0
for i, j in zip(fenek, snuke):
    if i <= j:
        f += 1
    else:
        s += 1

ans = "Fennec" if f > s else "Snuke"
print(ans)

Solution (Python):
def main():
    from heapq import heappush, heappop
    N = int(input())
    ans = ["Fennec", "Snuke"]
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        edge[a].append((1, b))
        edge[b].append((1, a))

    def dijkstra(s):
        """ 始点sから各頂点への最短距離 O((|E|+|V|)log|V|) """
        d = [10**8]*N
        used = [True] * N  
        d[s] = 0
        used[s] = False
        edges = []
        for e in edge[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in edge[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

    d_s = dijkstra(0)
    d_g = dijkstra(N-1)
    
    get = [0, 0]
    for s, g in zip(d_s, d_g):
        if s <= g:
            get[0] += 1
        else:
            get[1] += 1
    if get[0] > get[1]:
        print(ans[0])
    else:
        
        print(ans[1])


if __name__ == '__main__':
    main()

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

from collections import deque
q = deque()
q.append((0, 0))
d = [10**6]*N
d[0] = 0
while q:
    temp = q.popleft()
    v = temp[0]
    r = temp[1]
    for t in E[v]:
        if d[t] == 10**6:
            d[t] = r+1
            q.append((t, r+1))

num = N-1
for k in range((d[N-1]-1)//2):
    for v in E[num]:
        if d[v] == d[N-1]-k-1:
            num = v
            break
used = [0]*N
used[num] = 1
q = deque([0])
while q:
    temp = q.pop()
    for v in E[temp]:
        if used[v] == 0:
            used[v] = 1
            q.append(v)

if sum(used)-1 > N-sum(used)+1:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Solution (Python):
import heapq

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


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

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

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

d0 = dijkstra_heap(0)
d1 = dijkstra_heap(n-1)

f = 0
s = 0
for i in range(1,n-1):
    if d0[i] <= d1[i]:
        f +=1
    else:
        s += 1

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

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def shortest_path(pt,s,t):
    n = len(pt)
    used = [False]*n
    pre = [-1]*n
    q = [s]
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if not used[j]:
                    used[j] = True
                    pre[j] = i
                    q1.append(j)
        q = q1

    if used[t]:
        path = [t]
        p = t
        while True:
            p = pre[p]
            path.append(p)
            if p == s:
                break
        return list(reversed(path))
    else:
        return []

N = I()
a,b = MI(N-1,2)

pt = edges_to_pt(a,b,N)
path = shortest_path(pt,0,N-1)

v = path[math.ceil(len(path)/2)]
visited = [False]*N
visited[v] = True
S = [v]
num = 1
while S:
    v1 = S.pop()
    for i in pt[v1]:
        if i == path[math.ceil(len(path)/2)-1]:
            continue
        if not visited[i]:
            visited[i] = True
            num += 1
            S.append(i)

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

Solution (Python):
from collections import defaultdict
N = int(input())
dic = defaultdict(list)

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

dist1 = [float('inf')]*N
dist2 = [float('inf')]*N

q1 = [0]
q2 = [N-1]

dist1[0] = 0
dist2[N-1] = 0

while q1:
  e = q1.pop()
  for p in dic[e]:
    if dist1[p]>dist1[e]+1:
      dist1[p] = dist1[e]+1
      q1 += [p]

while q2:
  e = q2.pop()
  for p in dic[e]:
    if dist2[p]>dist2[e]+1:
      dist2[p] = dist2[e]+1
      q2 += [p]

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):
from bisect import *
from collections import *
N=int(input())
AB=[map(int,input().split()) for i in range(N-1)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
stack=deque([[1,0]])
visited=set([1])
flag=0
while stack :
    a,m=stack.popleft()
    for p in data[a]:
        if p==N:
            flag=1
            break
        if not p in visited:
            visited.add(p)
            stack.append([p,m+1])
    if flag:
        break

M=m//2
countFennec=0
countSnuke=0
visited=set([1,N])
stackSnuke=deque([[N,0]])
while stackSnuke:
    a,m=stackSnuke.popleft()
    if m>=M:
        stackSnuke.append([a,m])
        break
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(p)
            stackSnuke.append([p,m+1])

stackFennec=deque([[1,0]])
while stackFennec:
    a,m=stackFennec.popleft()
    for p in data[a]:
        if not p in visited:
            countFennec+=1
            visited.add(p)
            stackFennec.append([p,m+1])

while stackSnuke:
    a,m=stackSnuke.popleft()
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(p)
            stackSnuke.append([p,m+1])


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

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



def dfs(startp, depth):
  visited = [False for i in range(N)]
  d = deque()
  d.append(startp)

  while len(d) > 0:
    p = d.pop()
    visited[p] = True
    for q in E[p]:
      if visited[q]:
        continue
      d.append(q)
      depth[q] = depth[p] + 1

distf = [0 for i in range(N)]
dists = [0 for i in range(N)]

dfs(0, distf)
dfs(N-1, dists)



cntf, cnts = 0,0
for i in range(N):
  if distf[i] <= dists[i]:
    cntf += 1
  else:
    cnts += 1
    
print("Fennec" if cntf > cnts else "Snuke")

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



def dfs(startp, depth):
  visited = [False for i in range(N)]
  d = deque()
  d.append(startp)

  while len(d) > 0:
    p = d.pop()
    visited[p] = True
    for q in E[p]:
      if visited[q]:
        continue
      d.append(q)
      depth[q] = depth[p] + 1

distf = [0 for i in range(N)]
dists = [0 for i in range(N)]

dfs(0, distf)
dfs(N-1, dists)



cntf, cnts = 0,0
for i in range(N):
  if distf[i] <= dists[i]:
    cntf += 1
  else:
    cnts += 1
    
print("Fennec" if cntf > cnts else "Snuke")

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    dst[a-1].append(b-1)
    dst[b-1].append(a-1)
b = [0]
w = [n-1]
c = [0]*n
c[0] = 1
c[n-1] = -1
while len(b)>0 or len(w)>0:
    nxtb = []
    while len(b)>0:
        x = b.pop()
        for y in dst[x]:
            if c[y]==0:
                c[y] = 1
                nxtb.append(y)
    b = nxtb
    nxtw = []
    while len(w)>0:
        x = w.pop()
        for y in dst[x]:
            if c[y]==0:
                c[y] = -1
                nxtw.append(y)
    w = nxtw
print('Snuke' if sum(c)<=0 else 'Fennec')

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

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

    def root(x):
        go = [False for _ in range(N)]
        d = [0 for _ in range(N)]
        go[x] = True
        q = deque([x])
        while q:
            now = q.pop()
            for fol in dist[now]:
                if go[fol]:
                    continue
                else:
                    d[fol] = d[now] + 1
                    go[fol] = True
                    q.append(fol)
        return d
    
    fen = root(0)
    snu = root(N-1)
    fg = sg = 0
    for i in range(N):
        if fen[i] <= snu[i]:
            fg += 1
        else:
            sg += 1
            
    print("Fennec" if fg > sg else "Snuke")

if __name__ == "__main__":
    main()

Solution (Python):







import sys
from collections import deque

sys.setrecursionlimit(10 ** 8)

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

table_from_one = [10 ** 5 for _ in range(n)]
table_from_one[0] = 0
table_from_n = [10 ** 5 for _ in range(n)]
table_from_n[-1] = 0
arr_from_one = deque([0])
arr_from_n = deque([n - 1])


def set_table(table, arr):
    while len(arr) > 0:
        cur = arr.popleft()
        for next_node in graph[cur]:
            if table[next_node] < 10 ** 5:
                continue
            table[next_node] = table[cur] + 1
            arr.append(next_node)


set_table(table_from_one, arr_from_one)
set_table(table_from_n, arr_from_n)
result = 0
for i in range(n):
    if table_from_one[i] <= table_from_n[i]:
        result += 1
    else:
        result -= 1
print("Fennec" if result > 0 else "Snuke")

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N = ir()
edges = [[] for _ in range(N+1)] 
for _ in range(N-1):
    a, b = lr()
    edges[a].append(b)
    edges[b].append(a)

fen = 0
snu = 0
used = set([1, N])
fen_list = [1]
snu_list = [N]
while fen_list or snu_list:
    f = []
    for x in fen_list:
        for next in edges[x]:
            if next in used:
                continue
            fen += 1
            f.append(next)
            used.add(next)
    fen_list = f
    s = []
    for y in snu_list:
        for next in edges[y]:
            if next in used:
                continue
            snu += 1
            s.append(next)
            used.add(next)
    snu_list = s

print('Fennec' if fen > snu else 'Snuke')

Solution (Python):
from collections import deque


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


def d(s):
    ret = [10 ** 18] * n
    ret[s] = 0
    q = deque()
    q.append(s)
    while len(q):
        now = q.popleft()
        for to in g[now]:
            if ret[to] < 10 ** 18:
                continue
            ret[to] = ret[now] + 1
            q.append(to)
    return ret




fennec = d(0)
snuke = d(n - 1)
cnt = 0
for i in range(n):
    if fennec[i] <= snuke[i]:
        cnt += 1
    else:
        cnt -= 1
if cnt > 0:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
N=int(input())
import collections
import heapq
ab=[tuple(map(int,input().split())) for i in range(N-1)]
G=[set() for i in range(N)]
for a,b in ab:
  a-=1
  b-=1
  G[a].add(b)
  G[b].add(a)
q=collections.deque()

dis=[[-1]*N for i in range(2)]
dis[0][0]=0
q.append(0)
while(q):
  x=q.popleft()
  for y in G[x]:
    if dis[0][y]==-1:
      q.append(y)
      dis[0][y]=dis[0][x]+1
dis[1][N-1]=0
q.append(N-1)
while(q):
  x=q.popleft()
  for y in G[x]:
    if dis[1][y]==-1:
      q.append(y)
      dis[1][y]=dis[1][x]+1

hqF=[(0,0)]
hqS=[(0,N-1)]
colord=[False]*N

while(1):
  if len(hqF)==0:
    print("Snuke")
    exit(0)
  _,x = heapq.heappop(hqF)
  while(colord[x]):
    if hqF:
      _,x = heapq.heappop(hqF)
    else:
      print("Snuke")
      exit(0)
  colord[x]=True
  for y in G[x]:
    if colord[y]==False:
      heapq.heappush(hqF,(dis[1][y],y))

  if len(hqS)==0:
    print("Fennec")
    exit(0)
  _,x = heapq.heappop(hqS)
  while(colord[x]):
    if hqF:
      _,x = heapq.heappop(hqS)
    else:
      print("Fennec")
      exit(0)
  colord[x]=True
  for y in G[x]:
    if colord[y]==False:
      heapq.heappush(hqS,(dis[0][y],y))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
ab = [LIST() for _ in range(N-1)]

def dijkstra(E, start):
   N_d = len(E)
   dist = [INF] * N_d
   dist[start] = 0
   q = [(0, start)]
   while q:
       dist_v, v = heappop(q)
       if dist[v] != dist_v:
           continue
       for u, dist_vu in E[v]:
           dist_u = dist_v + dist_vu
           if dist_u < dist[u]:
               dist[u] = dist_u
               heappush(q, (dist_u, u))
   return dist

E = [[] for _ in range(N)]

for a, b in ab:
	E[a-1].append((b-1, 1))
	E[b-1].append((a-1, 1))

d_f = dijkstra(E, 0)
d_s = dijkstra(E, N-1)

f = 0
s = 0
for i in range(N):
	if d_f[i] <= d_s[i]:
		f += 1
	else:
		s += 1

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

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

    input = sys.stdin.readline

    def dfs(s) -> list:
        init = n

        d = [init] * n
        d[s] = 0

        q = deque()
        q.append(s)
        while q:
            v = q.popleft()
            for u in g[v]:
                if d[u] != init:
                    continue
                d[u] = d[v] + 1
                q.append(u)

        return d

    n = int(input())

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

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

    fennec = sum(dist_1[v] <= dist_n[v] for v in range(n))
    snuke = n - fennec

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    def dfs(v, d):
        for u in g[v]:
            if d[u] != init:
                continue
            d[u] = d[v] + 1
            dfs(u, d)

    n = int(input())

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

    init = n

    dist_1 = [init] * n
    dist_1[0] = 0
    dfs(0, dist_1)

    dist_n = [init] * n
    dist_n[n - 1] = 0
    dfs(n - 1, dist_n)

    fennec = sum(dist_1[v] <= dist_n[v] for v in range(n))
    snuke = n - fennec

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


if __name__ == '__main__':
    main()