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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

s = 0

d1 = [INF]*N
d1[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d1[v] != INF: continue
    d1[v] = d1[u] + 1
    q.append(v)
    
s = N-1
d2 = [INF]*N
d2[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d2[v] != INF: continue
    d2[v] = d2[u] + 1
    q.append(v)
    
ans = 0
for i in range(N):
  if d1[i]<=d2[i]:
    ans += 1

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

s = 0

d1 = [INF]*N
d1[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d1[v] != INF: continue
    d1[v] = d1[u] + 1
    q.append(v)
    
s = N-1
d2 = [INF]*N
d2[s] = 0
q = deque([s])
while q:
  u = q.popleft()
  for v in graph[u]:
    if d2[v] != INF: continue
    d2[v] = d2[u] + 1
    q.append(v)
    
ans = 0
for i in range(N):
  if d1[i]<=d2[i]:
    ans += 1

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

Solution (Python):
def dijkstra(s, stop, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))
            if u == stop:
                break

    return prev, cost


def main():
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk, cost = dijkstra(n, 1, g)
    l = cost[1] - 1
    k = l // 2 if l % 2 == 0 else l // 2 + 1
    vis = [False] * (n + 1)

    def f(now):
        if vis[now]:
            return 0
        vis[now] = True
        c = 1
        for _, nxt in g[now]:
            c += f(nxt)

        return c

    nw = dk[1]

    cnt = []
    i = 0
    vis[1] = True
    vis[n] = True
    while i < k:
        i += 1
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    fn += sum(cnt)
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Solution (Python):
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev, cost


def main():
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk, cost = dijkstra(n, g)
    l = cost[1] - 1
    k = l // 2 if l % 2 == 0 else l // 2 + 1
    vis = [False] * (n + 1)

    def f(now):
        if vis[now]:
            return 0
        vis[now] = True
        c = 1
        for _, nxt in g[now]:
            c += f(nxt)

        return c

    nw = dk[1]

    cnt = []
    i = 0
    vis[1] = True
    vis[n] = True
    while i < k:
        i += 1
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    fn += sum(cnt)
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Solution (Python):
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev


def main():
    from itertools import accumulate
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk = dijkstra(n, g)

    vis = [False] * (n + 1)

    def f(now, c):
        if vis[now]:
            return 0
        vis[now] = True
        cnt = 1
        for _, nxt in g[now]:
            cnt += f(nxt, c)

        return cnt

    nw = dk[1]

    cnt = []
    vis[1] = True
    vis[n] = True
    while nw != n:
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw, 0)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    *a, = accumulate(cnt)
    l = len(a)
    k = l // 2 - 1 if l % 2 == 0 else l // 2
    fn += a[k] if l > 0 else 0
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()

Solution (Python):








from collections import deque

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

neighbor = [[] for i in range(n)]
for e in edges:
    neighbor[e[0] - 1].append(e[1] - 1)
    neighbor[e[1] - 1].append(e[0] - 1)
    

info = [(-1, -1)] * n
info[0] = (0, -1) 

q = deque([])
q.append(0)


while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0:
            q.append(nei)
            info[nei] = (distance + 1, v)
    if len(q) == 0:
        break





now = n-1
distance = info[n-1][0]
half = distance // 2

if distance == half + 1:
    
    snuke_side_marginal = now
else:
    while True:
        now = info[now][1]
        distance -= 1
        if distance == half + 1:
            snuke_side_marginal = now
            break



info = [(-1, -1)] * n
info[0] = (0, -1) 

q = deque([])
q.append(0)

n_visited = 1


while True:
    v = q.popleft()
    distance = info[v][0]
    for nei in neighbor[v]:
        if info[nei][0] < 0 and nei != snuke_side_marginal:
            q.append(nei)
            info[nei] = (distance + 1, v)
            n_visited += 1

    if len(q) == 0:
        break

if n_visited > n - n_visited:
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
def resolve():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]
    adjlist = {}
    for a, b in AB:
        adjlist.setdefault(a-1, [])
        adjlist.setdefault(b-1, [])
        adjlist[a-1].append(b-1)
        adjlist[b-1].append(a-1)
    import collections
    q = collections.deque([0])
    sources = [None for _ in range(N)]
    sources[0] = -1
    while q:
        v = q.popleft()
        for nxt in adjlist[v]:
            if sources[nxt] is None:
                sources[nxt] = v
                q.append(nxt)
    
    
    
    shortest = [N-1]
    cur = N-1
    while True:
        shortest.append(sources[cur])
        if sources[cur] == 0:
            break
        cur = sources[cur]
    shortest.reverse()
    
    shortest = collections.deque(shortest[1:-1])

    b_nexts = set(adjlist[0])
    b_nexts.discard(N-1)
    w_nexts = set(adjlist[N-1])
    w_nexts.discard(0)

    colored = [False for _ in range(N)]
    colored[0] = True
    colored[N-1] = True
    b_turn = True
    while True:
        
        
        
        
        if b_turn:
            if len(b_nexts) == 0:
                print("Snuke")
                return
            if len(shortest) > 0:
                nxt = shortest.popleft()
                b_nexts.remove(nxt)
            else:
                nxt = b_nexts.pop()
            if nxt in w_nexts:
                w_nexts.remove(nxt)
        else:
            if len(w_nexts) == 0:
                print("Fennec")
                return
            if len(shortest) > 0:
                nxt = shortest.pop()
                w_nexts.remove(nxt)
            else:
                nxt = w_nexts.pop()
            if nxt in b_nexts:
                b_nexts.remove(nxt)
        
        colored[nxt] = True
        for v in adjlist[nxt]:
            if colored[v] is False:
                if b_turn:
                    b_nexts.add(v)
                else:
                    w_nexts.add(v)
        
        b_turn = not b_turn
    


if '__main__' == __name__:
    resolve()

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

from collections import deque
d_from_b=[-1]*n
d_from_w=[-1]*n
d_from_b[0]=0
todo=deque([0])
while todo:
  t=todo.popleft()
  l=ki[t]
  for li in l:
    if d_from_b[li]==-1:
      d_from_b[li]=d_from_b[t]+1
      todo.append(li)

d_from_w[n-1]=0
todo=deque([n-1])
while todo:
  t=todo.popleft()
  l=ki[t]
  for li in l:
    if d_from_w[li]==-1:
      d_from_w[li]=d_from_w[t]+1
      todo.append(li)
b_cnt=0
for i in range(n):
  if d_from_b[i]<=d_from_w[i]:
    b_cnt+=1
if n-b_cnt<b_cnt:
  print('Fennec')
else:
  print('Snuke')

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

from collections import deque

seen=[-2]*n
seen[0]=-1
todo=deque([0])
while todo:
  t=todo.popleft()
  l=ki[t]
  for li in l:
    if seen[li]==-2:
      seen[li]=t
      todo.append(li)
      if li==n-1:
        break
root=[n-1]
now=n-1
while now!=0:
  root.append(seen[now])
  now=seen[now]
bend=root[(len(root)-2)//2+1]
wend=root[(len(root)-2)//2]

seen=[0]*n
seen[bend]=1
seen[wend]=1
todo=[bend]
cnt=0
while todo:
  t=todo.pop()
  l=ki[t]
  cnt+=1
  for li in l:
    if seen[li]==0:
      todo.append(li)
      seen[li]=1
if n-cnt<cnt:
  print('Fennec')
else:
  print('Snuke')

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

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)

dist1 = [-1]*n
dist1[0] = 0
dist2 = [-1]*n
dist2[n-1] = 0
def dfs(now,dist):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        dfs(nxt,dist)
dfs(0,dist1)
dfs(n-1,dist2)

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

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

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)

dist = [(0,-1) for _ in range(n)]
def dfs(now,prev=-1):
    for nxt in G[now]:
        if nxt == prev: continue
        dist[nxt] = (dist[now][0]+1,now)
        dfs(nxt,now)
dfs(0)

color = ["?"]*n
cnt = 0
now = n-1
w = (dist[n-1][0]+1)//2
while now != -1:
    if cnt < w: color[now] = -1
    else: color[now] = 1
    cnt += 1
    now = dist[now][1]

def coloring(now,prev=-1):
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt] != "?" and color[now] != color[nxt]: continue
        color[nxt] = color[now]
        coloring(nxt,now)
coloring(0)
coloring(n-1)

print("Fennec" if sum(color) > 0 else "Snuke")

Solution (Python):
from collections import deque
n = int(input())

Map = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    Map[a-1].append(b-1)
    Map[b-1].append(a-1)
INF = float('inf')
def distance(st):
    d = [INF for i in range(n)]
    d[st] = 0
    q = deque()
    q.append(st)
    while q:
        index = q.pop()
        for nexts in Map[index]:
            if d[nexts] == INF:
                d[nexts] = d[index]+1
                q.append(nexts)
    return d
d1 = distance(0)
d2 = distance(n-1)

fen = 0
snu = 0
for i in range(n):
    if d1[i]<= d2[i]:
        fen += 1
    else:
        snu += 1

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

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    E = []
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        G[b].append(a)
        E.append((a, b))
    par = [-1] * N
    par[N - 1] = N - 1
    stk = [N - 1]
    while stk:
        v = stk.pop()
        for to in G[v]:
            if par[to] >= 0:
                continue
            par[to] = v
            stk.append(to)
    path = []
    v = 0
    while v != N - 1:
        path.append(v)
        v = par[v]
    path.append(N - 1)
    m = (len(path) - 1) // 2
    x, y = path[m], path[m + 1]
    uf = UnionFindTree(N)
    for a, b in E:
        if a == x and b == y or a == y and b == x:
            continue
        uf.union(a, b)
    print('Fennec' if uf.size(0) > uf.size(N - 1) else 'Snuke')

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

n = int(input())

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

d1 = [-1] * n
d2 = [-1] * n
d1[0] = 0
d2[-1] = 0

q1 = deque([0])
q2 = deque([n-1])

while q1:
    l = q1.pop()
    for i in roots[l]:
        if d1[i] == -1:
            d1[i] = d1[l] + 1
            q1.append(i)

while q2:
    l = q2.pop()
    for i in roots[l]:
        if d2[i] == -1:
            d2[i] = d2[l] + 1
            q2.append(i)

f = 0
s = 0

for i in range(n):
    if d1[i] <= d2[i]:
        f += 1
    else:
        s += 1

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

Solution (Python):
from collections import deque
def bfs(G, n,visited):
    q = deque([(1,'fe'),(n,'su')])
    visited[1] = 'fe'
    visited[n] = 'su'
    while q:
        curr_node = q.popleft()
        for next_node in G[curr_node[0]]:
            if visited[next_node] != 'yet': continue
            visited[next_node] = curr_node[1]
            q.append((next_node,curr_node[1]))


n = int(input())
G = [ [] for _ in range(n+1)]
visited = ['yet'] * (n+1)
for i in range(n-1):
    a, b = map(int, input().split()) 
    G[a].append(b)
    G[b].append(a)
bfs(G, n, visited)

if visited.count('fe') > visited.count('su'):
    print('Fennec')
else:
    print('Snuke')

Solution (Python):
from collections import deque
N = int(input())

G = {k: [] for k 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 bfs(i):
    visited = [-1 for _ in range(N)]
    visited[i] = 0
    que = deque([(i, 0)])

    while que:
        ci, d = que.popleft()

        for ni in G[ci]:
            if visited[ni] == -1:
                visited[ni] = d+1
                que.append((ni, d+1))

    return visited


F = bfs(0)
S = bfs(N-1)


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

Solution (Python):
n=int(input())

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

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

ans=[0]*n
ans[0]="B"
ans[n-1]="W"

from collections import deque

stack = deque([0,n-1])

while len(stack)>1:
    tmp=stack.popleft()

    for item in tree[tmp]:
        if ans[item]==0:
            if ans[tmp]=="W":
                ans[item]="W"
            else:
                ans[item]="B"
            stack.append(item)

if ans.count("B")>ans.count("W"):
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))












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

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

queue = [0,n-1]
done=0
col = [-1]*n
col[0]=0
col[n-1]=1

while(len(queue)>done):
    now = queue[done]
    done+=1
    for i in nb[now]:
        if(col[i]==-1):
            queue.append(i)
            col[i] = col[now]

print("Fennec" if n-sum(col) > sum(col) else "Snuke")

Solution (Python):
from collections import deque
N = int(input())
g = [[] for i in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
a = [-1]*N
b = [-1]*N
def bfs(n):
  q=deque()
  q.append(n)
  a[n] = 0
  while len(q):
    x=q.popleft()
    for i in g[x]:
      if a[i]==-1: 
        a[i]=a[x]+1
        q.append(i)
bfs(0)
def bfs2(n):
  q=deque()
  q.append(n)
  b[n] = 0
  while len(q):
    x=q.popleft()
    for i in g[x]:
      if b[i]==-1: 
        b[i]=b[x]+1
        q.append(i)
bfs2(N-1)
cnt = 0
for i in range(N):
  if a[i] <= b[i]:
    cnt += 1
  else:
    cnt -= 1
if cnt > 0:
  print('Fennec')
else:
  print('Snuke')

Solution (Python):
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
f = 0
s = 0
from collections import deque
ps = [-1] * n
used = [False] * n
used[0] = True 
q = deque([0])
while len(q) > 0:
    a = q.popleft()
    if a == n-1:
        break
    for u in edges[a]:
        if not used[u]:
            ps[u] = a
            q.append(u)
            used[u] = True

nx = n - 1
xs = [n-1]
while nx != 0:
    nx = ps[nx]
    xs.append(nx)

xs.reverse()
l = len(xs) - 2
f = (l+1)//2
s = l-f

if len(xs) == 2:
    z_lim = -1
    n_lim = 0
else:
    z_lim = (len(xs)+1)//2
    n_lim = z_lim - 1


used = [-1] * n
used[0] = 0 
q = deque([0])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[z_lim]:
            q.append(u)
            used[u] = 0
            cnt += 1

f += cnt


used = [-1] * n
used[n-1] = 0 
q = deque([n-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    for u in edges[a]:
        if used[u] == -1 and u != xs[n_lim]:
            q.append(u)
            used[u] = 0
            cnt += 1

s += cnt


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

Solution (Python):
from collections import deque

N = int(input())

G = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
pars = [-1] * N
pars[0] = 0
stack = deque([0])
visited = [False] * N
visited[0] = True

while stack:
  now = stack.pop()
  for nxt in G[now]:
    if visited[nxt]:
      continue
    visited[nxt] = True
    pars[nxt] = now
    stack.append(nxt)

now = N-1
roads = []
while now != 0:
  now = pars[now]
  roads.append(now)

roads.reverse()
roads.append(N-1)
stack = deque([])
for i in range((len(roads)+1)//2):
  stack.append(roads[i])

stop = roads[(len(roads)+1)//2]
visited = [False] * N
for i in roads:
  visited[i] = True

black = (len(roads)+1)//2

while stack:
  now = stack.pop()
  for nxt in G[now]:
    if visited[nxt] or (nxt==stop):
      continue
    visited[nxt] = True
    stack.append(nxt)
    black += 1

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

Solution (Python):
n=int(input())
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
fe=[0]*n
sn=[0]*n
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    fe[i]=fe[g]+1
d=deque()
d.append(n-1)
visited=[False]*n
visited[n-1]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    sn[i]=sn[g]+1
x=0
for i in range(n):
  if fe[i]>sn[i]:
    x+=1
  else:
    x-=1
print('Fennec' if x<0 else 'Snuke')