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

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

class Graph(object):

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

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

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

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

class Dijkstra(object):

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

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

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

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

        return path[::-1]

N = int(input())
g = Graph()

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

dij = Dijkstra(g,1)
path = dij.shortest_path(N)
c1 = path[ceil(len(path)/2)-1]
c2 = path[ceil(len(path)/2)]

g.graph[c1] = [(to,cost) for to,cost in g.graph[c1] if to != c2]
g.graph[c2] = [(to,cost) for to,cost in g.graph[c2] if to != c1]

dij = Dijkstra(g,1)
f = 0
for i in range(1,N):
    if dij.shortest_distance(i) != float('inf'):
        f += 1
if f > N-f:
    print('Fennec')
else:
    print('Snuke')

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

class Graph(object):

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

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

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

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

class Dijkstra(object):

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

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

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

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

        return path[::-1]

N = int(input())
g = Graph()

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

dij = Dijkstra(g,1)
path = dij.shortest_path(N)
c1 = path[ceil(len(path)/2)-1]
c2 = path[ceil(len(path)/2)]

g.graph[c1] = [(to,cost) for to,cost in g.graph[c1] if to != c2]
g.graph[c2] = [(to,cost) for to,cost in g.graph[c2] if to != c1]

dij = Dijkstra(g,1)
f = 0
for i in range(1,N):
    if dij.shortest_distance(i) != float('inf'):
        f += 1
if f > N-f:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from queue import Queue

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

q = Queue()
count = [0, 0]
used = [False] * N

q.put((0, 0))
count[0] += 1
used[0] = True

q.put((N - 1, 1))
count[1] += 1
used[N - 1] = True

while not q.empty():
    u, color = q.get()
    for v in g[u]:
        if not used[v]:
            q.put((v, color))
            count[color] += 1
            used[v] = True

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

Solution (Python):
from collections import defaultdict




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]
    graph_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)

    black, white = 0, 0
    b_ind_now, w_ind_now = set(), set()
    b_ind_next, w_ind_next = set(), set()
    
    pre_ind = set()
    b_ind_now.add(1)
    w_ind_now.add(num)
    
    
    pre_ind.add(1)
    pre_ind.add(num)

    while len(b_ind_now) > 0 or len(w_ind_now) > 0:
        for ele_now in b_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                b_ind_next.add(ele_next)
                black += 1
        b_ind_now = b_ind_next
        b_ind_next = set()


        for ele_now in w_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                w_ind_next.add(ele_next)
                white += 1
        w_ind_now = w_ind_next
        w_ind_next = set()

        

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





if __name__ == '__main__':
    main()

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


def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]
    graph_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)

    black, white = 0, 0
    b_ind_now, w_ind_now = set(), set()
    b_ind_next, w_ind_next = set(), set()
    
    pre_ind = set()
    b_ind_now.add(1)
    w_ind_now.add(num)
    
    
    pre_ind.add(1)
    pre_ind.add(num)

    while len(b_ind_now) > 0 or len(w_ind_now) > 0:
        for ele_now in b_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                b_ind_next.add(ele_next)
                black += 1
        b_ind_now = b_ind_next
        b_ind_next = set()


        for ele_now in w_ind_now:
            for ele_next in graph_data[ele_now]:
                if ele_next in pre_ind:
                    continue
                pre_ind.add(ele_next)
                w_ind_next.add(ele_next)
                white += 1
        w_ind_now = w_ind_next
        w_ind_next = set()

        

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





if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    S[a-1].append(b-1)
    S[b-1].append(a-1)
M = [0]*N
M[0],M[N-1] = 1,-1 
F_que = S[0]
S_que = S[-1]
while F_que != S_que:
    n_que = []
    for i in F_que:
        if M[i] == 0:
            M[i] = 1
            for j in S[i]:
                n_que.append(j)
    F_que = n_que
    n_que = []
    for i in S_que:
        if M[i] == 0:
            M[i] = -1
            for j in S[i]:
                n_que.append(j)
    S_que = n_que
print(["Snuke","Fennec"][sum(M) > 0])

Solution (Python):
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
stack1=deque(G[0])
stack2=deque(G[N-1])
X=[-1]*N
X[0]=1
X[N-1]=0
while(stack1 or stack2):
    Stack1=deque()
    for i in stack1:
        if X[i]==-1:
            X[i]=1
            for j in G[i]:
                if X[j]==-1:
                    Stack1.append(j)
    stack1=Stack1
    Stack2=deque()
    for i in stack2:
        if X[i]==-1:
            X[i]=0
            for j in G[i]:
                if X[j]==-1:
                    Stack2.append(j)
    stack2=Stack2
f,s=0,0
for i in range(N):
    if X[i]==1:
        f+=1
    else:
        s+=1
if f>s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def dfs(idx, cur, conn, dis):
        dis[idx] = cur
        for nex in conn[idx]:
            if dis[nex] is None:
                dfs(nex, cur + 1, conn, dis)
        return None

    f_dis = [None] * N
    f_dis[0] = 0
    dfs(0, 0, conn, f_dis)

    s_dis = [None] * N
    s_dis[N - 1] = 0
    dfs(N - 1, 0, conn, s_dis)

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

    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


def _solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def find_path(idx, target, conn, visited):
        visited[idx] = True
        if idx == target:
            return [target]
        for nex in conn[idx]:
            if not visited[nex]:
                path = find_path(nex, target, conn, visited)
                if path is not None:
                    return [idx] + path
        return None

    visited = [False] * N
    path_to_n = find_path(0, N - 1, conn, visited)
    

    colors = [None] * N
    for i, node in enumerate(path_to_n):
        if i < (len(path_to_n) + 1) // 2:
            colors[node] = 1
        else:
            colors[node] = 0

    def dfs(idx, conn, colors, visited):
        visited[idx] = True
        colors[idx] = 1
        for nex in conn[idx]:
            if not visited[nex] and (colors[nex] is None or colors[nex] == 1):
                dfs(nex, conn, colors, visited)
        return

    visited = [False] * N
    dfs(0, conn, colors, visited)
    

    cnt = 0
    for c in colors:
        if c == 1:
            cnt += 1
    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def dfs(idx, cur, conn, dis):
        dis[idx] = cur
        for nex in conn[idx]:
            if dis[nex] is None:
                dfs(nex, cur + 1, conn, dis)
        return None

    f_dis = [None] * N
    f_dis[0] = 0
    dfs(0, 0, conn, f_dis)

    s_dis = [None] * N
    s_dis[N - 1] = 0
    dfs(N - 1, 0, conn, s_dis)

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

    if cnt > (N - cnt):
        ret = 'Fennec'
    else:
        ret = 'Snuke'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Solution (Python):











import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
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 [input() 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)

    set_A = set()
    set_B = set()
    a_stack = [0]
    b_stack = [N - 1]
    for _ in range(N - 1):
        tmp_a = []
        tmp_b = []
        while a_stack:
            from_ = a_stack.pop()
            for to in edge[from_]:
                if to not in set_A and to not in set_B:
                    tmp_a.append(to)
                    set_A.add(to)
        while b_stack:
            from_ = b_stack.pop()
            for to in edge[from_]:
                if to not in set_A and to not in set_B:
                    tmp_b.append(to)
                    set_B.add(to)
        a_stack = tmp_a
        b_stack = tmp_b
    if len(set_A) > len(set_B):
        print("Fennec")
    else:
        print("Snuke")


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import numpy as np

sys.setrecursionlimit(2 ** 31 - 1)
INF = float('inf')

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().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)

s1 = [1]
s2 = [N]
fennec = 0
snuke = 0
fixed = np.zeros(N + 1, dtype=bool)
while s1 or s2:
    u1 = []
    for v in s1:
        if fixed[v]:
            continue
        fixed[v] = True
        fennec += 1
        u1.extend(graph[v])
    s1 = u1

    u2 = []
    for v in s2:
        if fixed[v]:
            continue
        fixed[v] = True
        snuke += 1
        u2.extend(graph[v])
    s2 = u2

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

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
Edges=[]
for i in range(n-1):
  a,b=map(int,input().split())
  Edges.append([a,b,1])
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
F,S=BFS(0,Edges,n),BFS(n-1,Edges,n)
count=0
for i in range(1,n-1):
  if F[i]<=S[i]:
    count+=1
  else:
    count-=1
print("Fennec" if count>0 and n!=2 else "Snuke")

Solution (Python):
class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )
  def count(me,a):
    ua = me.up[a] if me.up[a]!=-1 else a
    return len(me.down[ua])+1

N = int(input())

li = [ [ int(it) -1 for it in input().split() ] for i in range(N-1) ]

down = [ [] for i in range(N) ]

for a,b in li:
  down[a].append(b)
  down[b].append(a)

mita = [0]*N
mita[0]=1
kouho = [0]
dist = [100000000000000000]*N
dist[0] = 0

for i in range(10000000000000000):
  if ( len(kouho) == 0 ):
    break
  n = kouho.pop()
  for k in down[n]:
    if ( mita[k] == 0 ):
      dist[k] = min(dist[k],dist[n]+1)
      mita[k] = 1
      kouho.append(k)

route = [N-1]
for i in range(10000000000000000):
  n = route[-1]
  if ( n == 0 ):
    break
  s = 100000000000000
  sk = -1
  for k in down[n]:
    if (s > dist[k] - dist[n]):
      s = dist[k] - dist[n]
      sk = k
  route.append(sk)   
route.reverse()
x,y = route[ (len(route)-1)//2 ],route[ 1+((len(route)-1)//2) ]

u = Union(N)
for a,b in li:
  if (a==x and b==y) or (a==y and b==x):
      continue
  u.union(a,b)

if ( u.count(0) <= u.count(N-1) ):
  print ( "Snuke" )
else:
  print ( "Fennec" )

Solution (Python):
import sys
sys.setrecursionlimit(114514)
N=int(input())
path=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b=map(int,input().split())
	path[a].append(b)
	path[b].append(a)
fenne=[-1 for _ in range(N+1)]
snuke=[-1 for _ in range(N+1)]
def walk(ar, i, d):
	if ar[i] == -1:
		ar[i] = d
		for x in path[i]:
			walk(ar, x, d+1)
walk(fenne, 1, 0)
walk(snuke, N, 0)
f,s=0,0
for i in range(1, N+1):
	if snuke[i] < fenne[i]:
		s+=1
	else:
		f+=1


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

Solution (Python):
N=int(input())
E=[[] for _ in [0]*N]
for _ in [0]*(N-1):
    a,b=map(int,input().split())
    E[a-1]+=[b-1]
    E[b-1]+=[a-1]
V=[1]+[0]*(N-2)+[-1]
q=[0,N-1]
while q:
    p=[]
    for i in q:
        for j in E[i]:
            if not V[j]:
                V[j]=V[i]
                p+=[j]
    q=p
print("Fennec" if sum(V)>0 else "Snuke")

Solution (Python):
N = int(input())
E = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
V = [0]*N
V[0] = 1
V[-1] = -1
q = [0,N-1]
while q:
    qq = []
    for i in q:
        Vi = V[i]
        for j in E[i]:
            if not V[j]:
                V[j] = Vi
                qq.append(j)
    q = qq
print("Fennec" if sum(V)>0 else "Snuke")

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

adja_dict={}

for a,b in AB:
  adja_dict.setdefault(a, set()).add(b)
  adja_dict.setdefault(b, set()).add(a)

nodes = [None] * (N+2) 
nodes[0] = nodes[1] = 1
nodes[N] = nodes[N+1] = -1

from collections import deque
dq = deque([1, N])
while dq:
  x = dq.popleft()
  for y in adja_dict[x]:
    if nodes[y] is None:
      nodes[y] = nodes[x]
      dq.append(y)

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

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


N = int(input())

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

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

INF = 10**18

d_fe = [INF]*N
d_sn = [INF]*N

d_fe[0] = 0
d_sn[N-1] = 0

def f(d,x):
  dx = d[x]
  for v in edge[x]:
    if d[v] == INF:
      d[v] = dx+1
      f(d,v)
      
f(d_fe,0)
f(d_sn,N-1)

black = 0
white = 0

for x in range(N):
  if d_fe[x] <= d_sn[x]:
    black += 1
  else:
    white += 1

answer = 'Fennec' if black > white else 'Snuke'
print(answer)

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

N = int(readline())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    s,t = map(lambda x:int(x)-1, readline().split())
    edges[s].append(t)
    edges[t].append(s)

def bfs(edges, s)->list:
    V = len(edges)
    dist = [float('inf')]*V
    visited = [False]*V
    dist[s] = 0
    visited[s] = True
    q = deque([s])
    while q:
        cur = q.popleft()
        for nex in edges[cur]:
            if visited[nex]:
                continue
            q.append(nex)
            visited[nex] = True
            dist[nex] = dist[cur] + 1
    return dist

dist1 = bfs(edges, 0)
dist2 = bfs(edges, N-1)
score1 = 0
for d1,d2 in zip(dist1, dist2):
    if d1 <= d2:
        score1 += 1

print("Fennec" if score1 > N/2 else "Snuke")

Solution (Python):
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    s,t = map(lambda x:int(x)-1, input().split())
    edges[s].append(t)
    edges[t].append(s)

from collections import deque
def bfs(edges, s)->list:
    V = len(edges)
    dist = [float('inf')]*V
    visited = [False]*V
    dist[s] = 0
    visited[s] = True
    q = deque([s])
    while q:
        cur = q.popleft()
        for nex in edges[cur]:
            if visited[nex]:
                continue
            q.append(nex)
            visited[nex] = True
            dist[nex] = dist[cur] + 1
    return dist

dist1 = bfs(edges, 0)
dist2 = bfs(edges, N-1)
score1 = 0
for d1,d2 in zip(dist1, dist2):
    if d1 <= d2:
        score1 += 1

print("Fennec" if score1 > N/2 else "Snuke")

Solution (Python):
import queue 

N = int(input())
graph = [[] for i in range(N)]

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

f = [0]*N
vf = [False] * N
qf = queue.Queue()
qf.put(0)
vf[0] = True

while not qf.empty():
    now = qf.get()
    edge = len(graph[now])
    if not edge == 0:
        for i in range(edge):
            if not vf[graph[now][i]]:
                qf.put(graph[now][i])
                f[graph[now][i]] = f[now]+1
                vf[graph[now][i]] = True

s = [0]*N
vs = [False] * N
qs = queue.Queue()
qs.put(N-1)
vs[N-1] = True

while not qs.empty():
    now = qs.get()
    edge = len(graph[now])
    if not edge == 0:
        for i in range(edge):
            if not vs[graph[now][i]]:
                qs.put(graph[now][i])
                s[graph[now][i]] = s[now]+1
                vs[graph[now][i]] = True

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

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

Solution (Python):
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def bfs(i,d,N):
    q = deque()
    q.append(i)
    d_from_1 = [-1]*(N+1)
    d_from_1[i] = 0
    i = 1
    while q:
        l = len(q)
        for j in range(l):
            next_node = q.popleft()
            for succ in d[next_node]:
                if d_from_1[succ] == -1:
                    d_from_1[succ] = i
                    q.append(succ)
        i += 1
    return d_from_1
    
def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)       
    f= 0
    s= 0
    d_from_1 = bfs(1,d,N)
    d_from_N = bfs(N,d,N)
        
    
    
    for i in range(1,N+1):
        if(d_from_1[i] <= d_from_N[i]):
            f += 1
        else:
            s += 1
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce
import math
from collections import deque
from collections import defaultdict

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input().rstrip())
    a = []
    b = []
    d = defaultdict(list)
    
    for i in range(N-1):
        s1,s2 = list(int(_) for _ in input().split())
        d[s1].append(s2)
        d[s2].append(s1)
        
    bw = defaultdict(str)
    bw[1] = 'b'
    bw[N] = 'w'
    f= 0
    s= 0
    q = deque()
    q.append(1)
    q.append(N)
    while q:
        next_node = q.popleft()
        if(bw[next_node] == 'b'):
            f+=1
        elif(bw[next_node] == 'w'):
            s+=1
        for succ in d[next_node]:
            if bw[succ] == '':
                bw[succ] = bw[next_node]
                q.append(succ)
    if(f>s):
        print('Fennec')
    else:
        print('Snuke')
if __name__ == '__main__':
    main()

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


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

    
    hq = [(0, x)]

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

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


Black = dijkstra(0)
White = dijkstra(N - 1)

Black_point = 0
for b, w in zip(Black, White):
    if b <= w:
        Black_point += 1

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

Solution (Python):

import sys
from collections import deque

N=input()

nl=[ [] for i in range(N+1)]
D=[ 0 for i in range(N+1)]	
V=[ 0 for i in range(N+1)]	

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


def bfs(v):	
	q = deque([]) 
	V[v]=1
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if V[i]==0:
				D[i]=D[v]+1
				V[i]=1
				q.append(i)

bfs(1)


L=deque([]) 	
def bfs2(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if D[i]==D[v]-1 and i!=1:
				q.append(i)
				L.appendleft(i)

bfs2(N)


color=[ None for i in range(N+1)]
color[1]="b"
color[N]="w"

l=len(L)
for i in range( (l+1)/2 ):
	color[ L[i] ]="b"

for i in range( (l+1)/2, l ):
	color[ L[i] ]="w"


def bfs3(v):
	q = deque([]) 
	q.append(v)
	while q:
		v=q.popleft()
		for i in nl[v]:
			if color[i] is None:
				color[i]=color[v]
				q.append(i)

L.append(1)
L.append(N)
for i in L:
	bfs3(i)
		

b_cnt=color.count("b")
w_cnt=color.count("w")


if N%2==1:
	if b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"
else:
	if b_cnt==w_cnt:	
		print "Snuke"
	elif b_cnt>w_cnt:
		print "Fennec"
	else:
		print "Snuke"

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

B = [False]*N
visited = [True]*N

Fp,Sp = 0,0
Fi,Si = [0],[N-1]

while B != visited:
    
    nextXi = []
    for i in Fi:
        if not B[i]:
            B[i] = True
            Fp += 1
            nextXi.extend(A[i])
    Fi = nextXi
    
    nextXi = []
    for i in Si:
        if not B[i]:
            B[i] = True
            Sp += 1
            nextXi.extend(A[i])
    Si = nextXi

print("Fennec" if Fp>Sp else "Snuke")

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

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

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

shortest = []
def get_path(start, end, par):
    if end in e[start]:
        shortest.append(end)
        return True
    for item in e[start]:
        if item != par:
             if get_path(item, end, start):
                 shortest.append(item)
                 return True

def tree_count(start, par, a, b):
    count = 0
    for item in e[start]:
        if start == a and item == b:
            continue
        if start == b and item == a:
            continue
        if item != par:
            count += 1
            count += tree_count(item, start, a, b)
    return count

get_path(0, n-1, -1)
shortest.append(0)
shortest = shortest[::-1]
cut_l = (len(shortest)-1) // 2
p = tree_count(0, -1, shortest[cut_l], shortest[cut_l+1])
q = n - p - 2 
if p > q:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import heapq

N = int(input())
d = [0] * N
INF = float('inf')
        
G = [[] 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)
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heapq.heappush(h, [d[e], e])

dijkstra(0)
d2 = d.copy()
F = d2

dijkstra(N - 1)
S = d

Fennec = 0
for i in range(N):
    if F[i] <= S[i]:
        Fennec += 1
        
print('Fennec' if Fennec > N - Fennec else 'Snuke')

Solution (Python):
import sys
from collections import deque

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

    dist_one = [-1 for _ in range(N+1)]
    dist_one[1] = 0

    dist_n = [-1 for _ in range(N+1)]
    dist_n[N] = 0

    qo = deque()
    qo.append(1)
    while len(qo) > 0:
        i = qo.popleft()
        for j in A[i]:
            if dist_one[j] != -1:
                continue

            dist_one[j] = dist_one[i] + 1
            qo.append(j)

    qn = deque()
    qn.append(N)
    while len(qn) > 0:
        i = qn.popleft()
        for j in A[i]:
            if dist_n[j] != -1:
                continue

            dist_n[j] = dist_n[i] + 1
            qn.append(j)

    co, cn = 0, 0
    for i in range(1, N+1):
        if dist_one[i] <= dist_n[i]:
            co += 1
        else:
            cn += 1

    if co > cn:
        return 'Fennec'
    else:
        return 'Snuke'


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