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 heapq
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] += [[b,1]]
  graph[b] += [[a,1]]

def dijkstra(s):
  
  dist = [float('inf')]*N
  dist[s] = 0
  num = [0]*N
  num[s] = 1
  q = [[0, s]]
  pre = [0]*N
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
        pre[v] = u
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num, pre

d1, _, pre1 = dijkstra(0)
d2, _, pre2 = dijkstra(N-1)

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

if a1 <= a2:
  print('Snuke')
else:
  print('Fennec')

Solution (Python):
from collections import deque

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

not_visited = [-1]*N
not_visited[0] = 0
stack = deque()
stack.append(0)

while stack != deque([]):
    now = stack.popleft()
    for i in line[now]:
        if not_visited[i] == -1:
            not_visited[i] = now
            stack.append(i)

route = []
now = N-1
while not_visited[now] != 0:
    route.append(now)
    now = not_visited[now]
route.append(now)
route.reverse()

l = len(route)

not_visited = [-1]*N
for i in route[l//2:]:
    not_visited[i] = -2
not_visited[0] = 0
stack = deque()
stack.append(0)

F = 0
while stack != deque([]):
    now = stack.popleft()
    for i in line[now]:
        if not_visited[i] == -1:
            not_visited[i] = not_visited[now] + 1
            stack.append(i)
            F += 1

S = N-F-2

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

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    n = ni()
    e = [[] for _ in range(n)]

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

    dist_f = [-1 for _ in range(n)]
    dist_s = [-1 for _ in range(n)]
    dist_f[0] = 0
    dist_s[n - 1] = 0

    def bfs(que, dist):
        while que:
            q = que.popleft()
            for ei in e[q]:
                if dist[ei] == -1:
                    dist[ei] = dist[q] + 1
                    que.append(ei)
        return dist

    dist_f = bfs(collections.deque([0]), dist_f)
    dist_s = bfs(collections.deque([n - 1]), dist_s)

    f = 0
    s = 0
    for df, ds in zip(dist_f, dist_s):
        if df <= ds:
            f += 1
        else:
            s += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import collections
n = int(raw_input())
adj = collections.defaultdict(list)
for _ in range(n-1):
	u,v = map(int, raw_input().split())
	adj[u].append(v)
	adj[v].append(u)
def bfs(source, adj):
	q = collections.deque([(source,0)])
	distance = {}
	vis = set([source])
	while(q):
		u,d = q.popleft()
		distance[u] = d
		for v in adj[u]:
			if v not in vis:
				vis.add(v)
				q.append((v,d+1))
	return distance
a,b = bfs(1, adj), bfs(n, adj)
print 'Fennec' if 2* sum([+1 if a[u] <= b[u] else 0 for u in range(1, n+1)]) > n else 'Snuke'

Solution (Python):
from collections import deque

N=int(input())
G=[[] for _ in range(N+1)]

for i in range(N-1):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)
  
def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque()
    seen[s]=1
    todo.append(s)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d_f = bfs(1)
d_s = bfs(N)

count_f,count_s=0,0
for i in range(1,N+1):
  if d_f[i] <= d_s[i]:count_f +=1
  else: count_s += 1
    
if count_f>count_s:print('Fennec')
else:print('Snuke')

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	n=II()
	G=[[] for _ in range(n+1)]

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


	B=[-1]*(n+1)
	W=[-1]*(n+1)
	B[1]=0
	W[n]=0

	Q=deque([1])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if B[i]==-1:
				B[i]=B[now]+1
				Q.append(i)
	

	Q=deque([n])
	while Q:
		now=Q.popleft()
		for i in G[now]:
			if W[i]==-1:
				W[i]=W[now]+1
				Q.append(i)
	

	s=0
	f=0
	for i,j in zip(B[1:],W[1:]):
		if i<=j:
			f+=1
		else:
			s+=1
	

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






if __name__ == "__main__":
	main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    search = [-1] * N
    search[v0] = 0
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if search[nv] == -1:
                q.append(nv)
                search[nv] = search[v] + 1

    return search


def bfs2(N, v0, edge, dis):

    q = deque()
    q.append(v0)

    ret = []

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if dis[v] > dis[nv] and dis[nv] != 0:
                q.append(nv)
                ret.append(nv)

    return ret[::-1]


def bfs3(N, v0, edge, color, x):

    search = [False] * N
    search[v0] = True
    q = deque()
    q.append(v0)

    ret = 0

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if not search[nv]:
                if color[nv] == -1:
                    ret += 1
                    q.append(nv)
                elif color[nv] == x:
                    q.append(nv)
                search[nv] = True

    return ret


def main():

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

    for i in range(N - 1):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    dis = bfs(N, 0, edge)
    color_v = bfs2(N, N - 1, edge, dis)

    color = [-1] * N
    color[0] = 1
    color[-1] = 0

    color_v = deque(color_v)
    teban = 1

    while color_v:

        if teban == 1:
            v = color_v.popleft()
            color[v] = 1
            teban = 0

        elif teban == 0:
            v = color_v.pop()
            color[v] = 0
            teban = 1

    fen = bfs3(N, 0, edge, color, 1)
    sun = bfs3(N, N - 1, edge, color, 0)

    

    if teban == 1:
        if fen > sun:
            ans = 'Fennec'
        else:
            ans = 'Snuke'
    elif teban == 0:
        if sun > fen:
            ans = 'Snuke'
        else:
            ans = 'Fennec'

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


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

    """
    改良コードも試す。
    どっちが先にマスに色を塗るかは、要は両者のスタート地点からの距離を比べれば良い。
    前にもこの手の議論見た気がする。。。
    """

    
    depth_from_Fennec = [-1] * N
    depth_from_Snuke = [-1] * N
    depth_from_Fennec[0] = 0
    depth_from_Snuke[N - 1] = 0

    q = deque([0])
    while q:
        u = q.popleft()
        for v in repn[u]:
            if depth_from_Fennec[v] != -1: continue
            depth_from_Fennec[v] = depth_from_Fennec[u] + 1
            q.append(v)
    q.append(N - 1)
    while q:
        u = q.popleft()
        for v in repn[u]:
            if depth_from_Snuke[v] != -1: continue
            depth_from_Snuke[v] = depth_from_Snuke[u] + 1
            q.append(v)

    Fennec = Snuke = 0
    for f, s in zip(depth_from_Fennec, depth_from_Snuke):
        if f <= s:
            Fennec += 1
        else:
            Snuke += 1
    if Fennec > Snuke:
        print("Fennec")
    else:
        print("Snuke")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        xの属する木の根を返す
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        x, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

    """
    まさかの問題を読み間違えていた。。。
    （プレイヤーがマスの上を１マスずつ動くと思っていた）

    「最適に行動した時」＝「どちらかに必勝法が存在する」と言い換える。
    あとはその戦略を見出せば勝ち。見抜けなければ相手の全行動パターンに勝つ手の存在を示す。
    同じ色が隣接していればどのマスでも塗れるなら、最初に一気に２人が距離を詰めた方がいいに決まってる。
    """

    
    depth_from_0 = [-1] * N
    parent = [-1] * N
    depth_from_0[0] = 0

    def dfs(u):
        for v in repn[u]:
            if depth_from_0[v] != -1: continue
            depth_from_0[v] = depth_from_0[u] + 1
            parent[v] = u
            dfs(v)

    dfs(0)

    
    path = [N - 1]
    while path[-1] != 0: path.append(parent[path[-1]])
    l = len(path)

    
    tree = UnionFind(N)
    a0, b0 = path[l // 2 - 1], path[l // 2]
    if a0 > b0: a0, b0 = b0, a0
    for a, b in edge:
        if a != a0 or b != b0: tree.union(a, b)
    Fennec = tree.size(0)
    Snuke = tree.size(N - 1)
    if Fennec > Snuke:
        print("Fennec")
    else:
        print("Snuke")



if __name__ == "__main__":
    main()

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

def bfs(s):
    q = deque([s])
    dist = [-1]*N
    dist[s] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
        
    return dist

N = int(input())
G = [[] for _ in range(N)]

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

d1 = bfs(0)
d2 = bfs(N-1)
c = 0

for i in range(N):
    if d1[i]<=d2[i]:
        c += 1

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

Solution (Python):
from heapq import heappop, heappush
from collections import deque
n = int(input())
mp2 = []
route = [[] for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x:int(x)-1,input().split())
    mp2.append((a,b,1))
    mp2.append((b,a,1))
    route[a].append(b)
    route[b].append(a)
inf=float('inf')
d=[inf for i in range(n)]
d[0]=0
prev=[None]*n
p=dict()
for i,j,k in mp2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[0],0))
while q:
    du, u = heappop(q)
    if d[u]<du: continue
    for v,weight in p.get(u,[]):
        alt=du+weight
        if d[v]>alt:
            d[v]=alt
            prev[v]=u
            heappush(q, (alt,v))

p=[n-1]
while prev[p[-1]]!=None: p.append(prev[p[-1]])

p = p[::-1]
t = p[-(-len(p)//2)-1]

d = deque()
d.append(n-1)
visit = [False for i in range(n)]
siro = 1
visit[n-1] = True
visit[t] = True
while d:
    now = d.popleft()
    for i in route[now]:
        if not visit[i] and i != t:
            visit[i] = True
            d.append(i)
            siro += 1
kuro = n - siro
if kuro <= siro:
    print("Snuke")
elif kuro > siro:
    print("Fennec")

Solution (Python):
import queue
n=int(input())
e=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=queue.Queue()
q.put(1)
vif=[-1]*n
vif[0]=0
while not q.empty():
  now=q.get()
  for to in e[now]:
    if vif[to-1]==-1:
      q.put(to)
      vif[to-1]=vif[now-1]+1
q.put(n)
vis=[-1]*(n+1)
vis[n-1]=0
while not q.empty():
  now=q.get()
  for to in e[now]:
    if vis[to-1]==-1:
      q.put(to)
      vis[to-1]=vis[now-1]+1
ans=0
for i in range(n):
  if vif[i]<=vis[i]:ans+=1
print(['Snuke','Fennec'][ans>n//2])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  

def make_tree_0index(N):
    edge_dic = {}
    for _ in range(N-1):
        x, y = na()
        x -= 1
        y -= 1
        if x in edge_dic:
            edge_dic[x].append(y)
        else:
            edge_dic[x] = [y]
        if y in edge_dic:
            edge_dic[y].append(x)
        else:
            edge_dic[y] = [x]
    return edge_dic


N = ni()

edge_dic = make_tree_0index(N)

parent_array = [-2] * N
depth_array = [-1] * N

node = deque([0])
parent_array[0] = -1
depth_array[0] = 0

while(len(node)):
    n = node.popleft()
    for nn in edge_dic[n]:
        if nn == parent_array[n]:
            continue
        parent_array[nn] = n
        depth_array[nn] = depth_array[n] + 1
        node.append(nn)



now_depth = depth_array[-1]
max_node = N - 1
for i in range((now_depth-1)//2):
    max_node = parent_array[max_node]

cnt = 1
node.append(max_node)
while(len(node)):
    n = node.popleft()
    for nn in edge_dic[n]:
        if nn == parent_array[n]:
            continue
        node.append(nn)
        cnt += 1



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

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()

Graph = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

Fennec = [-1]*(N+1)  
Snuke = [-1]*(N+1)  

from collections import deque

q1 = deque([1])
q2 = deque([N])
Fennec[1] = 0
Snuke[N] = 0
while q1:
    n = q1.pop()
    for d in Graph[n]:
        if Fennec[d] == -1:
            Fennec[d] = Fennec[n] + 1
            q1.appendleft(d)
while q2:
    n = q2.pop()
    for d in Graph[n]:
        if Snuke[d] == -1:
            Snuke[d] = Snuke[n] + 1
            q2.appendleft(d)
            
a = sum(Fennec[i] <= Snuke[i] for i in range(1,N+1))
print('Fennec' if a >= N//2+1 else 'Snuke')

Solution (Python):
from collections import deque, defaultdict

def main():
  n=int(input())
  edges=[tuple(map(int,input().split())) for _ in range(n-1)]
  d=defaultdict(list)
  for e in edges:
    d[e[0]].append(e[1])
    d[e[1]].append(e[0])
  def dist(m):
    c=-1
    dl=[-1]*(n+1)
    cv=deque([m])
    nv=deque([1])
    while nv:
      c+=1
      cv.extend(nv)
      nv.clear()
      for e in cv:
        dl[e]=c
        for x in d[e]:
          if dl[x]<0:
            nv.append(x)
      cv.clear()
    return dl[1:]
  fnc=dist(1)
  snk=dist(n)
  j=sum([(fnc[i]<=snk[i])-(fnc[i]>snk[i]) for i in range(n)])
  if j>0:
    print('Fennec')
  else:
    print('Snuke')

if __name__=='__main__':
    main()

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

n=int(input())
edges=[tuple(map(int,input().split())) for _ in range(n-1)]
d=defaultdict(list)
for e in edges:
  d[e[0]].append(e[1])
  d[e[1]].append(e[0])
fnc=[-1]*(n+1)
snk=[-1]*(n+1)
fnc[1]=0
snk[n]=0
cv=deque([1])
nv=deque([1])
c=-1
while nv:
  c+=1
  cv.extend(nv)
  nv.clear()
  for e in cv:
    fnc[e]=c
    for x in d[e]:
      if fnc[x]<0:
        nv.append(x)
  cv.clear()
cv.append(n)
nv=deque([1])
c=-1
while nv:
  c+=1
  cv.extend(nv)
  nv.clear()
  for e in cv:
    snk[e]=c
    for x in d[e]:
      if snk[x]<0:
        nv.append(x)
  cv.clear()

j=sum([(fnc[i]<=snk[i])-(fnc[i]>snk[i]) for i in range(1,n+1)])
if j>0:
  print('Fennec')
else:
  print('Snuke')

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    dist1 = [-1] * N
    dist1[0] = 0
    queue = deque([0])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist1[nv] == -1:
                dist1[nv] = dist1[v] + 1
                if nv != N - 1:
                    queue.append(nv)

    dist2 = [-1] * N
    dist2[N - 1] = 0
    queue = deque([N - 1])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist2[nv] == -1:
                dist2[nv] = dist2[v] + 1
                if nv != 0:
                    queue.append(nv)

    F = S = 0
    for i, (d1, d2) in enumerate(zip(dist1, dist2)):
        if i in (0, N - 1):
            continue
        if d1 == -1:
            S += 1
        elif d2 == -1:
            F += 1
        elif d1 <= d2:
            F += 1
        else:
            S += 1

    if F > S:
        print('Fennec')
    else:
        print('Snuke')

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    dist = [f_inf] * n
    dist[0] = 0
    q = deque([0])
    while q:
        u = q.popleft()
        if u != n - 1:
            for nv in edge[u]:
                if dist[nv] == f_inf:
                    dist[nv] = dist[u] + 1
                    q.append(nv)

    half_dist = (dist[-1] - 1) // 2
    dist2 = [f_inf] * n
    dist2[-1] = 0
    q = deque([n - 1])
    while q:
        u = q.popleft()
        for nv in edge[u]:
            if dist[nv] == f_inf:
                continue
            else:
                if dist2[nv] == f_inf:
                    if dist2[u] + 1 <= half_dist:
                        dist2[nv] = dist2[u] + 1
                        q.append(nv)

    visited = [False] * n
    visited[0] = True
    q = deque([0])
    while q:
        u = q.popleft()
        if u != n - 1:
            for nv in edge[u]:
                if dist2[nv] == f_inf and not visited[nv]:
                    visited[nv] = True
                    q.append(nv)

    fennec = sum(visited)
    snuke = n - fennec
    print("Fennec" if fennec > snuke else "Snuke")


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque

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

color = [0]*N
color[0] = 1
color[N-1] = -1
q = deque([])
q.append(0)
q.append(N-1)

while q:
  node = q.popleft()
  c = color[node]
  for to in G[node]:
    if color[to] == 0:
      color[to] = c
      q.append(to)

b = color.count(1)
w = color.count(-1)

if b > w:
  print('Fennec')
else:
  print('Snuke')

Solution (Python):
from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
cnt = [1, 1]
q = deque([(0, 0), (n-1, 1)])
seen = [False]*n
seen[0] = seen[n-1] = True
while q:
    node, turn = q.popleft()
    for c_node in graph[node]:
        if seen[c_node]:
            continue
        seen[c_node] = True
        cnt[turn] += 1
        q.append((c_node, turn))
print('FSennunkeec'[cnt[1]>=cnt[0]::2])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
pre = [None]*n
def dfs(node, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        pre[c_node] = node
        dfs(c_node, node)
dfs(0)
path = [n-1]
now = n-1
while now>0:
    now = pre[now]
    path.append(now)
snuke = path[len(path)//2-1]
fennec = path[len(path)//2]
def dfs2(node, p_node):
    cnt = 1
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        cnt += dfs2(c_node, node)
    return cnt
print('FSennunkeec'[dfs2(fennec, snuke)<=dfs2(snuke, fennec)::2])

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
from collections import deque 
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
INF = 1 << 32
d = [INF] * n
d[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for e in es[v]:
        if d[e] == INF:
            d[e] = d[v] + 1
            q.append(e)
d2 = [INF] * n
q.append(n - 1)
d2[n - 1] = 0
while q:
    v = q.popleft()
    for e in es[v]:
        if d2[e] == INF and d2[v] + 1 < d[e]:
            d2[e] = d2[v] + 1
            q.append(e)

print("Fennec" if 2 * sum(1 for i in d2 if i < INF) < n else "Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
from collections import deque 
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
INF = 1 << 32
d = [INF] * n
d[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for e in es[v]:
        if d[e] == INF:
            d[e] = d[v] + 1
            q.append(e)
d2 = [INF] * n
q.append(n - 1)
d2[n - 1] = 0
while q:
    v = q.popleft()
    for e in es[v]:
        if d2[e] == INF and d2[v] + 1 < d[e]:
            d2[e] = d2[v] + 1
            q.append(e)

print("Fennec" if 2 * sum(1 for i in d2 if i < INF) < n else "Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
def dfs0(v, d, p):
    if v == n - 1:
        return d
    for e in es[v]:
        if e != p:
            k = dfs0(e, d + 1, v)
            if k:
                if isinstance(k, int) and k // 2 == d:
                    return v, e
                return k
    return 0

def dfs1(v, p):
    if v == E:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs1(e, v)
    return cnt

V, E = dfs0(0, 0, -1)
if  2*dfs1(0, -1) > n:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
def dfs0(v, d, p):
    if v == n - 1:
        return d
    for e in es[v]:
        if e != p:
            k = dfs0(e, d + 1, v)
            if k:
                if isinstance(k, int) and k // 2 == d:
                    return v, e
                return k
    return 0

def dfs1(v, p):
    if v == E:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs1(e, v)
    return cnt

def dfs2(v, p):
    if v == 0:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs2(e, v)
    return cnt
V, E = dfs0(0, 0, -1)
if  2*dfs1(0, -1) > n:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
def dfs0(v, d, p):
    if v == n - 1:
        return d
    for e in es[v]:
        if e != p:
            k = dfs0(e, d + 1, v)
            if k:
                if isinstance(k, int) and k // 2 == d:
                    return v, e
                return k
    return 0

def dfs1(v, p):
    if v == E:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs1(e, v)
    return cnt


V, E = dfs0(0, 0, -1)
if  2*dfs1(0, -1) > n:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
def dfs0(v, d, p):
    if v == n - 1:
        return d
    for e in es[v]:
        if e != p:
            k = dfs0(e, d + 1, v)
            if k:
                if isinstance(k, int) and k // 2 == d:
                    return v, e
                return k
    return 0

def dfs1(v, p):
    if v == E:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs1(e, v)
    return cnt

def dfs2(v, p):
    if v == 0:
        return 0
    cnt = 1
    for e in es[v]:
        if e != p:
            cnt += dfs2(e, v)
    return cnt
V, E = dfs0(0, 0, -1)
if  2*dfs1(0, -1) > n:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

import sys
from dataclasses import dataclass

def solve(N: int, a: "List[int]", b: "List[int]"):
    from collections import defaultdict, deque
    edges = defaultdict(list)
    for aa, bb in zip(a, b):
        edges[aa].append(bb)
        edges[bb].append(aa)
    def f():
        visited = [None] * (N+1)
        que = deque([("f", 1), ("s", N)])
        while que:
            name, node = que.popleft()
            if visited[node]:
                continue
            visited[node] = name
            for n in edges[node]:
                if visited[n]:
                    continue
                que.append((name, n))
        return sum("f" == v for v in visited)
    return "Fennec" if f() > N // 2 else "Snuke"
            



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))
    print(solve(N, a, b))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
query = [[] for _ in range(N)]
ab = []
for _ in range(N-1):
    a, b = mapint()
    query[a-1].append(b-1)
    query[b-1].append(a-1)
    ab.append((a-1, b-1))

def dfs_lis(start):
    checked = [0]*N
    dist = [0]*N
    def dfs(now):
        checked[now] = 1
        for nx in query[now]:
            if not checked[nx]:
                dist[nx] = dist[now]+1
                dfs(nx)
    dfs(start)
    return dist

fe = dfs_lis(0)
snu = dfs_lis(N-1)
cnt = 0
for f, s in zip(fe, snu):
    if f<=s:
        cnt += 1

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