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):
def main():
    from collections import deque
    import sys
    buf = sys.stdin.buffer
    
    n = int(buf.readline())
    E = map(int, (buf.read().split()))
    edges = [[] for i in range(n)]
    
    for a, b in zip(E, E):
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    
    todo = deque([0, n-1])
    
    colors = [0] * n
    colors[0] = 1
    colors[-1] = 2
    
    while todo:
        node = todo.popleft()
        color = colors[node]
    
        for to in edges[node]:
            if colors[to]:
                continue
            else:
                colors[to] = color
                todo.append(to)
    
    fennec_count = colors.count(1)
    if fennec_count > n // 2:
        print('Fennec ')
    
    else:
        print('Snuke ')


if __name__ == '__main__':
    main()

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


n = int(input())
edges = [[] for i in range(n)]

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

todo = deque([(0, 1), (n-1, 2)])

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

while todo:
    node, color = todo.popleft()
    for to in edges[node]:
        if colors[to]:
            continue
        else:
            colors[to] = color
            todo.append((to, color))

fennec_count = colors.count(1)
if fennec_count > n // 2:
    print('Fennec ')

else:
    print('Snuke ')

Solution (Python):
from collections import deque


n = int(input())
edges = [[] for i in range(n)]

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

todo = deque([(0, 1), (n-1, 2)])

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

while todo:
    node, color = todo.popleft()
    for to in edges[node]:
        if colors[to]:
            continue
        else:
            colors[to] = color
            todo.append((to, color))

fennec_count = colors.count(1)
if fennec_count > n // 2:
    print('Fennec ')

else:
    print('Snuke ')

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


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)

seen = [-1] * n
todo = [(0, 0)]

while todo:
    node, prev = todo.pop()
    if seen[node] != -1:
        continue

    seen[node] = prev
    for to in edges[node]:
        if seen[to] != -1:
            continue
        todo.append((to, node))


colors = [0] * n

node = n-1
goal_to_start = [n-1]
while node:
    node = seen[node]
    goal_to_start.append(node)

length = len(goal_to_start)
limit = (length) // 2

colors = [0] * n
for node in goal_to_start[:limit]:
    colors[node] = 2

for node in goal_to_start[limit:]:
    colors[node] = 1

fennec_todo = [node for node in range(n) if colors[node] == 1]
snuke_todo = [node for node in range(n) if colors[node] == 2]


def paint(todo, my_color):
    while todo:
        node = todo.pop()
        for to in edges[node]:
            if colors[to]:
                continue

            colors[to] = my_color
            todo.append(to)


paint(fennec_todo, 1)
paint(snuke_todo, 2)

feccec_count = len([color for color in colors if color == 1])
snuke_count = len([color for color in colors if color == 2])

if feccec_count > snuke_count:
    print('Fennec ')

else:
    print('Snuke ')

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


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)

seen = [-1] * n


def dfs(node, prev):
    if seen[node] != -1:
        return
    seen[node] = prev

    for to in edges[node]:
        dfs(to, node)


dfs(0, 0)

colors = [0] * n

node = n-1
goal_to_start = [n-1]
while node:
    node = seen[node]
    goal_to_start.append(node)

length = len(goal_to_start)
limit = (length) // 2

colors = [0] * n
for node in goal_to_start[:limit]:
    colors[node] = 2

for node in goal_to_start[limit:]:
    colors[node] = 1

fennec_todo = [node for node in range(n) if colors[node] == 1]
snuke_todo = [node for node in range(n) if colors[node] == 2]


def paint(todo, my_color):
    while todo:
        node = todo.pop()
        for to in edges[node]:
            if colors[to]:
                continue

            colors[to] = my_color
            todo.append(to)


paint(fennec_todo, 1)
paint(snuke_todo, 2)

feccec_count = len([color for color in colors if color == 1])
snuke_count = len([color for color in colors if color == 2])

if feccec_count > snuke_count:
    print('Fennec ')

else:
    print('Snuke ')

Solution (Python):
import sys
from collections import deque

N = int(sys.stdin.readline().strip())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().strip().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

visited = set()
q = {"fennec": deque([0]), "snuke": deque([N-1])}


count = {"fennec": 0, "snuke": 0}
while q["fennec"] or q["snuke"]:
    for user in ("fennec", "snuke"):
        if not q[user]:
            continue
        nq = deque()
        while q[user]:
            point = q[user].popleft()
            for point_next in edges[point]:
                if point_next in visited:
                    continue
                visited.add(point_next)
                count[user] += 1
                nq.append(point_next)
        q[user] = nq

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

Solution (Python):
from collections import deque

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

def calc_dist(node):
  dist = [-1] * N
  dist[node] = 0
  d = deque([[node, -1]])
  while d:
    node, p = d.pop()
    children = tree[node]
    for child in children:
      if child == p:
        continue
      dist[child] = dist[node] + 1
      d.append([child, node])
  return dist

d1 = calc_dist(0)
dN = calc_dist(N-1)

fennec = snuke = 0
for node in range(1, N-1):
  if d1[node] <= dN[node]:
    fennec += 1
  else:
    snuke += 1

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

Solution (Python):



import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  
dist_from_fen = [-1 for i in range(N)]
dist_from_snk = [-1 for i in range(N)]

stack = []

stack.append([0,0,-1])
while stack:
  v,dist,parent = stack.pop()
  dist_from_fen[v] = dist
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child,dist + 1,v])

stack = []
stack.append([N - 1,0,-1])
while stack:
  v,dist,parent = stack.pop()
  dist_from_snk[v] = dist
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child,dist + 1,v])

black = 0
white = 0
for i in range(N):
  if dist_from_fen[i] <= dist_from_snk[i]:
    black += 1
  else:
    white += 1
print(("Snuke","Fennec")[black > white])

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

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


dist=[float("inf")]*N
dist[0]=0
prev=[None]*N

def dfs1(v,parent,d):
    prev[v]=parent
    dist[v]=d
    for v2 in graph[v]:
        if v2==parent:
            continue
        dfs1(v2,v,d+1)

dfs1(0,-1,0)

x=N-1
for _ in range((dist[-1]-1)//2):
    x=prev[x]
cant_go=prev[x]

sunuke_score=0
def dfs2(v,parent):
    global sunuke_score
    sunuke_score+=1
    for v2 in graph[v]:
        if v2==parent:
            continue
        if v2==cant_go:
            continue
        dfs2(v2,v)

dfs2(x,-1)

fennec_score=N-sunuke_score
if sunuke_score>=fennec_score:
    print("Snuke")
else:
    print("Fennec")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)
INF = 10**18
dist = [INF]*n
dist[0] = 0
prev = [None]*n


def dfs(v, parent, d):
    prev[v] = parent
    dist[v] = d
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, d+1)


dfs(0, -1, 0)

x = n-1
for _ in range((dist[-1]-1)//2):
    x = prev[x]
cant_go = prev[x]


def dfs2(v, parent):
    global snuke_v_cnt
    snuke_v_cnt += 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        if v2 == cant_go:
            continue
        dfs2(v2, v)


snuke_v_cnt = 0
dfs2(x, -1)

fennec_v_cnt = n-snuke_v_cnt
print('Fennec' if snuke_v_cnt < fennec_v_cnt else 'Snuke')

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

sd = [-1]*(N+1)
q = deque()
q.append((1, 0))
while len(q) > 0:
    u, c = q.popleft()
    sd[u] = c
    for v in ab[u]:
        if sd[v] == -1:
            q.append((v, c+1))

ed = [-1]*(N+1)
q = deque()
q.append((N, 0))
while len(q) > 0:
    u, c = q.popleft()
    ed[u] = c
    for v in ab[u]:
        if ed[v] == -1:
            q.append((v, c+1))

sc = 0
for i in range(1, N+1):
    if sd[i] <= ed[i]:
        sc += 1
ec = N-sc
if sc > ec:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
AB = [list(map(int,input().split())) for _ in range (N-1)]
edge = [[] for _ in range(N)]
for u,v in AB:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

dists = [0]*N
distn = [0]*N
def dfs_s(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        dists[nv] = dists[v] + 1
        dfs_s(nv, v)
    return 
def dfs_n(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        distn[nv] = distn[v] + 1
        dfs_n(nv, v)
    return 
dfs_s(0,-1)
dfs_n(N-1,-1)

B = 0
W = 0
for i in range(N):
    if dists[i]<=distn[i]:
        B += 1
    else:
        W += 1

if B>W:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):


import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

edge = [[] for _ in range(N)]
for u,v in ab:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

fromNode = [0] * N
def dfs(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        fromNode[nv] = v
        dfs(nv, v)
    return 

def pathFind(s, g, fromNode):
    path = []
    while s!=g:
        g = fromNode[g]
        if g==s:break
        path.append(g)
    path.reverse()
    return path
dfs(0,-1)
path = pathFind(0,N-1,fromNode)

colors = [-1]*N
colors[0] = 0
colors[N-1] = 1
for i in range(len(path)):
    if i<=(len(path)-1)//2:
        colors[path[i]] = 0
    else:
        colors[path[i]] = 1

def dfs_color(v, p, c):
    for nv in edge[v]:
        if nv==p:continue 
        if colors[nv]==-1:
            colors[nv] = c
            dfs_color(nv, v, c)
    return 

dfs_color(0,-1,0)
dfs_color(N-1, -1, 1)
for p in path:
    c = colors[p]
    dfs_color(p, -1, c)

B = 0
W = 0
for c in colors:
    if c==0:B+=1
    elif c==1:W+=1

if B>W:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
N=int(input())
D=[[] for i in range(N)]
F,S=[-1]*N,[-1]*N
F[0]=0
S[N-1]=0
for i in range(N-1):
  a,b=map(int, input().split())
  a-=1
  b-=1
  D[a].append(b)
  D[b].append(a)
 
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
dis=0

def bfs(n):
  t=0
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if F[i]==-1 and i!=x: 
        F[i]=F[x]+1
        q.append(i)

def bfs2(n):
  t=0
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if S[i]==-1 and i!=x:
        S[i]=S[x]+1
        q.append(i)
bfs(0)
bfs2(N-1)
f,s=0,0
for i in range(N):
  if F[i]<=S[i]:
    f+=1
  else:
    s+=1

if f<=s:
  print('Snuke')
else:
  print('Fennec')

Solution (Python):
from queue import deque

n = int(input())
li = [[] for _ in range(n+1)]

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

def width_prime(start,li,n):
    inf = 10**10
    visited = [False]*(n+1)
    length = [inf]*(n+1)
    length[start] = 0
    visited[start] = True
    work_queue = deque([])
    work_queue.append(start)
    while work_queue:
        now = work_queue.popleft()
        visited[now] = True
        for i in li[now]:
            if visited[i]:
                continue
            work_queue.append(i)
            visited[i] = True
            if length[i] > length[now]+1:
                length[i] = length[now]+1
    return length

le_fe = width_prime(1,li,n)
le_su = width_prime(n,li,n)

su = 0
fe = 0
for i in range(1,n+1):
    if le_fe[i] <= le_su[i]:
        fe += 1
    else:
        su += 1

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

Solution (Python):


import sys








from collections import deque                





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def restore_path(seq, start, goal):
        buf = []
        current = goal
        while current != start:
            buf.append(current)
            current = seq[current]
        buf.append(start)
        buf.reverse()
        return buf


    def calc_dist_path_in_bfs(adj, start, goal):
        q = deque()
        q.append([[start, None], 0])
        prev_memo = [None] * n
        while q:
            (u, prev), dist = q.popleft()
            if u == goal:
                prev_memo[u] = prev
                return dist, restore_path(prev_memo, start, goal)
            if not visited[u]:
                visited[u] = True
                prev_memo[u] = prev
                for v in adj[u]:
                    if not visited[v]:
                        q.append([[v, u], dist+1])
    
    def calc_node_in_dfs(adj, start):
        cnt = 1
        stack = [start]
        visited[start] = True
        while stack:
            
            u = stack[-1]
            for v in adj[u]:
                if not visited[v]:
                    stack.append(v)
                    visited[v] = True
                    cnt += 1                  
                    break
            else:
                stack.pop()
        return cnt


    n = ii()
    adj = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = mi_0()
        adj[a].append(b)
        adj[b].append(a)
    
    visited = [False] * n
    dist, path = calc_dist_path_in_bfs(adj, start=0, goal=n-1)
    
    
    
    visited = [False] * n
    if dist % 2 == 1:
        i = path[(dist-1)//2]
        j = path[(dist-1)//2 + 1]
        adj[i].remove(j)
        adj[j].remove(i)
        
        i_color = calc_node_in_dfs(adj, i)
        j_color = calc_node_in_dfs(adj, j)
        print('Fennec') if i_color > j_color else print('Snuke')
    else:
        i = path[dist//2]
        j = path[dist//2+1]
        adj[i].remove(j)
        adj[j].remove(i)
        
        i_color = calc_node_in_dfs(adj, i)
        j_color = calc_node_in_dfs(adj, j)
        print('Fennec') if i_color >= j_color else print('Snuke')


if __name__ == "__main__":
    main()

Solution (Python):
from queue import Queue

INF = 10 ** 5
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
d1 = [INF] * N
d2 = [INF] * N
d1[0] = 0
d2[N-1] = 0

q1 = Queue()
q1.put((0,0))

while not q1.empty():
    x, c = q1.get()
    for u in edges[x]:
        if d1[u] == INF:
            d1[u] = c + 1
            q1.put((u,c+1))

q2 = Queue()
q2.put((N-1,0))

while not q2.empty():
    x, c = q2.get()
    for u in edges[x]:
        if d2[u] == INF:
            d2[u] = c + 1
            q2.put((u,c+1))

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

if black <= white:
    print('Snuke')
else:
    print('Fennec')

Solution (Python):
from collections import defaultdict
import heapq
INF = 10**6


def dijkstra(N, adj_nodes, start_node, non_use_node):
    assert start_node != non_use_node
    d = [INF for _ in range(N)]
    d[start_node] = 0
    frontier = [(0, start_node)]
    while len(frontier) > 0:
        dist, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if next_node == non_use_node:
                continue
            if d[next_node] > dist + 1:
                d[next_node] = dist + 1
                heapq.heappush(frontier, (d[next_node], next_node))
    return d


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    fen_node, snu_node = 0, N - 1
    d_fen = dijkstra(N, adj_nodes, fen_node, snu_node)
    d_snu = dijkstra(N, adj_nodes, snu_node, fen_node)
    fen_score = 0
    for f, s in zip(d_fen, d_snu):
        fen_score += 1 if f <= s else 0
    snu_score = N - fen_score
    
    if fen_score <= snu_score:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    main()

Solution (Python):
import queue
N = int(input())
G = [[] for _ in range(N)]

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

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist

FE = dfs(G, N, 0)
SN = dfs(G, N, N-1)

get_count = sum(FE[i] <= SN[i] for i in range(N))
print('Fennec' if get_count > N-get_count else 'Snuke')

Solution (Python):
from collections import defaultdict
from collections import deque
dic = defaultdict(set)
n = int(input())
for i in range(n-1):
    a, b = map(int, input().split())
    dic[a].add(b)
    dic[b].add(a)
q = deque([(1, 'F'), (n, 'S')])
seen = set([1, n])
f = 1
s = 1
while q:
    p, player = q.popleft()
    for child in dic[p]:
        if child not in seen:
            seen.add(child)
            q.append((child, player))
            if player == 'F':
                f += 1
            else:
                s += 1
print('Fennec' if f > s else 'Snuke')

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


def input(): return sys.stdin.readline().strip()


def resolve():

    
    
    from heapq import heapify, heappop, heappush

    inf = 10 ** 17

    def dijkstra_heap(start, edge):
        
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)

        while len(edgelist):
            
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d

    
    N = int(input())
    W = N-1

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

    fen = dijkstra_heap(0, edge)
    sun = dijkstra_heap(N-1, edge)
    f = 0
    s = 0

    for i in range(1, N-1):
        if fen[i] <= sun[i]:
            f += 1
        elif fen[i] > sun[i]:
            s += 1
    print('Fennec' if f > s else 'Snuke')


resolve()

Solution (Python):
from collections import defaultdict

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

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

def dfs(source):
    dist = [-1]*(N+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1, d2 = dfs(1), dfs(N)
a = sum(d1[i]<=d2[i] for i in range(1, N+1))
print("Fennec" if 2*a>N else "Snuke")

Solution (Python):
from collections import defaultdict

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

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

def dfs(source):
    dist = [-1]*(N+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1, d2 = dfs(1), dfs(N)
a = sum(d1[i]<=d2[i] for i in range(1, N+1))
print("Fennec" if a>N-a else "Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
def getSP(v,d):
    p=v
    if dist[v]==d:
        return v
    for nv in G[v]:
       if dist[nv]<dist[v]:
           p=getSP(nv,d)
    return p
    
def Sdepth(v):
    res=1
    if not G[v]:
        return 1
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        res+=Sdepth(nv)
    return res
    
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dist=[-1]*N
dfs(0,-1,0)
P=(dist[N-1]-1)//2
sp=getSP(N-1,dist[N-1]-P)
dep=Sdepth(sp)
Sunu=dep-(dist[N-1]-dist[sp]+1)
Fene=N-dep-dist[sp]
if dist[N-1]%2:
    print('Fennec' if Fene>Sunu else 'Snuke')
else:
    print('Fennec' if Fene>=Sunu else 'Snuke')

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(edges, n_nodes):
    visited = [None] * n_nodes
    visited[0] = "B"
    visited[-1] = "W"

    q = deque([0, n_nodes - 1])

    while q:
        i = q.popleft()

        for j in edges[i]:
            if visited[j] is None:
                visited[j] = visited[i]
                q.append(j)

    return visited


def main():
    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)

    visited = bfs(edges, N)
    if visited.count("B") > visited.count("W"):
        print("Fennec")
    else:
        print("Snuke")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b=map(int1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    cost=[INF]*N
    cost[0]=0
    stack=[0]
    while stack:
        v=stack.pop()
        for nv in edge[v]:
            if cost[nv]==INF:
                cost[nv]=cost[v]+1
                stack.append(nv)
                if nv==N-1:
                    break
    d=cost[N-1]
    v=N-1
    for i in range(d+1):
        if i==(d-1)//2:
            sv=v
        elif i==(d+1)//2:
            fv=v
            break
        for nv in edge[v]:
            if cost[nv]==cost[v]-1:
                v=nv
                break

    stack=[sv]
    used=[False]*N
    used[fv]=True
    c=0
    while stack:
        v=stack.pop()
        used[v]=True
        c+=1
        for nv in edge[v]:
            if not used[nv]:
                stack.append(nv)
    if c>=N-c:
        print('Snuke')
    else:
        print('Fennec')
    

if __name__ == '__main__':
    main()

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

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

fnc = deque()
snk = deque()

fnc.appendleft(0)
snk.appendleft(n-1)

check = [0]*(n)

check[0] = 1
check[n-1] = 1

fnc_num = 0
snk_num = 0

while len(fnc) > 0 or len(snk) > 0:
    for i in range(len(fnc)):
        tmp = fnc.popleft()
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                fnc_num += 1
                check[ab[tmp][j]] = 1
                fnc.append(ab[tmp][j])
                
    for i in range(len(snk)):
        tmp = snk.popleft()
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                snk_num += 1
                check[ab[tmp][j]] = 1
                snk.append(ab[tmp][j])
                
    
    
    
if fnc_num > snk_num:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import deque


def bfs(v, N):
    dist = [-1 for _ in range(N)]
    que = deque()
    que.append((v, 0, -1))
    while que:
        (now, cost, par) = que.popleft()
        dist[now] = cost
        for edge in edges[now]:
            if edge == par:
                continue
            que.append((edge, cost + 1, now))
    return dist


N = int(input())
edges = {i: [] for i in range(N)}
for _ in range(N - 1):
    a, b = map(int, input().split(' '))
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

dist_from_one = bfs(0, N)
dist_from_N = bfs(N - 1, N)
fennec = 0
for i in range(N):
    fennec += int(dist_from_one[i] <= dist_from_N[i])

print('Fennec' if 2 * fennec > N else 'Snuke')

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

qf = queue.Queue()
qs = queue.Queue()
qf.put(1)
qs.put(n)
who = ["" for i in range(n+1)]
wht = [10**5+5 for i in range(n+1)]
who[0] = "N"
who[1] = "F"
who[n] = "S"
wht[0] = 0
wht[1] = 0
wht[n] = 1


while not(qf.empty() and qs.empty()):
    if not qf.empty():
        fi = qf.get()
        if who[fi] == "F":
            for i in way[fi]:
                if wht[i] > wht[fi] + 2:
                    qf.put(i)
                    wht[i] = wht[fi] + 2
                    who[i] = "F"
    if not qs.empty():
        si = qs.get()
        if who[si] == "S":
            for i in way[si]:
                if wht[i] > wht[si] + 2:
                    qs.put(i)
                    wht[i] = wht[si] + 2
                    who[i] = "S"

if who.count("F") > who.count("S"):
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
from collections import deque

n = int(input())
node = [[] for _ 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)

not_yet = deque(node[0])
dist = [0]*n
par = [0]*n
for v in node[0]:
  dist[v] = 1
  par[v] = 0

while not_yet:
  key = not_yet.popleft()
  for v in node[key]:
    if dist[v] or v == 0:
      continue
    dist[v] = dist[key]+1
    par[v] = key
    not_yet.append(v)

k = n-1
for _ in range((dist[n-1]-1)//2):
  k = par[k]

ans = 0
not_yet = deque([])
already = [False]*n
already[0] = True
already[k] = True
already[n-1] = True
for v in node[0]:
  if already[v]:
    continue
  ans += 1
  not_yet.append(v)
  already[v] = True
while not_yet:
  key = not_yet.popleft()
  for v in node[key]:
    if already[v]:
      continue
    ans += 1
    not_yet.append(v)
    already[v] = True

judge = (n-2)//2+1
if ans >= judge:
  print("Fennec")
else:
  print("Snuke")