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 queue import Queue


def distances(tree: list, size: int, root: int)->list:
    dists = [0] * size

    q = Queue()
    q.put((root, -1, 0))

    while not q.empty():
        v, prev, d2v = q.get()
        dists[v] = d2v

        for u, dv2u in tree[v]:
            if u == prev:
                continue
            q.put((u, v, d2v + dv2u))

    return dists


def fennec_vs_snuke(N: int, edges: list)->str:
    tree = [[] for _ in range(N)]
    for a, b in edges:
        tree[a-1].append((b-1, 1))
        tree[b-1].append((a-1, 1))

    d_from1 = distances(tree, N, 0)
    d_fromN = distances(tree, N, N-1)

    fennec, snuke = 0, 0
    for i in range(N):
        if d_fromN[i] < d_from1[i]:
            snuke += 1
        else:
            fennec += 1
    return 'Fennec' if fennec > snuke else 'Snuke'


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(int(s) for s in input().split()) for _ in range(N-1)]
    ans = fennec_vs_snuke(N, edges)
    print(ans)

Solution (Python):
import itertools
import math
from collections import deque
N = int(input())
adj = [[] for _ in range(N+1)]

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

def bfs(S):
    dist = [N]*(N+1)
    dist[S] = 0
    q = deque([S])
    while q:
        u=q.pop()
        for v in adj[u]:
            if dist[v] == N:
                dist[v] = dist[u]+1
                q.appendleft(v)
    return dist
df = bfs(1)
ds = bfs(N)

if sum(df[i] > ds[i] for i in range(1,N+1)) >= N/2:
    print("Snuke")
else:
    print("Fennec")

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

def dfs(v):
    d= [0] * n
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        visited[v] = 1
        visited.append(v)
        for i in edges[v]:
            if not visited[i]:
                d[i] = d[v] + 1
                q.append(i)
    return d

dist_from0 = dfs(0)
dist_fromn = dfs(n-1)

f = 0
s = 0
for i in range(n):
    if dist_fromn[i] >= dist_from0[i]:
        f += 1
    else:
        s += 1
if f>s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
import sys
input=sys.stdin.readline
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
brack[N]=0
check=deque([1])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if brack[i]>10**9:
            brack[i]=brack[now]+1
            check.append(i)
white=[float('inf')]*(N+1)
white[N]=0
white[1]=0
check=deque([N])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if white[i]>10**9:
            white[i]=white[now]+1
            check.append(i)
brack[N]=float('inf')
white[1]=float('inf')
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

Solution (Python):


from collections import deque

INF = 10 ** 5 + 10

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

s = [INF for _ in range(N)]


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


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

q = deque()
q.append((0, 0))

while q:
    v, d = q.popleft()
    f[v] = d
    for nv in e[v]:
        if f[nv] <= d + 1: continue
        q.append((nv, d + 1))

q = deque()
q.append((N - 1, 0))

while q:
    v, d = q.popleft()
    s[v] = d
    for nv in e[v]:
        if s[nv] <= d + 1: continue
        q.append((nv, d + 1))

Fennec_count = 0
for v in range(N):
    if f[v] <= s[v]:
        
        
        Fennec_count += 1
        

print('Fennec' if Fennec_count > N - Fennec_count else 'Snuke')

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

N = int(input())
ad = [[] for _ in range(N)]
dis = [[-1]*N,[-1]*N]

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

def bfs(s):
    index = 0 if s == 0 else 1
    dq = deque()
    dq.append((s,0,-1))
    while dq:
        v,d,pre = dq.popleft()
        dis[index][v] = d
        for nv in ad[v]:
            if nv == pre:continue
            dq.append((nv,d+1,v))

bfs(0); bfs(N-1)
f = 0; s = 0
for d0,d1 in zip(dis[0],dis[1]):
    if d0 <= d1: f += 1
    else: s += 1
ans = "Fennec" if f > s else "Snuke"
print(ans)

Solution (Python):
import sys,copy
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
inf = float('inf')

N = int(input())
ad = [{} for _ in range(N)]
dis = [inf]*N
near = [-1]*N
player = ["Fennec","Snuke"]

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

back_up = [copy.deepcopy(line) for line in ad]

def dfs(v,start,depth=0):
    if dis[v] > depth:
        dis[v] = depth
        near[v] = start
    if not ad[v]:
        return
    while ad[v]:
        key,nv = ad[v].popitem()
        ad[nv].pop(key)
        dfs(nv,start,depth+1)

dfs(0,0)
ad = back_up
dfs(N-1,N-1)
f = near.count(0)
s = N-f
ans = player[0] if f > s else player[1]
print(ans)

Solution (Python):
from collections import deque


def main():
    N = int(input())
    adj = [set() for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].add(b)
        adj[b].add(a)
    state = [None] * (N+1)
    q = deque([(1, "B"), (N, "W")])
    while len(q):
        node, color = q.popleft()
        if state[node] is not None:
            continue
        state[node] = color
        for nxt in adj[node]:
            if state[nxt] is None:
                adj[nxt].remove(node)
                q.append((nxt, color))
    result = {"B": 0, "W": 0}
    for s in state:
        if s in result:
            result[s] += 1
    if result["B"] > result["W"]:
        print("Fennec")
    else:
        print("Snuke")


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""


n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = deque()
q.append(0)
d_f[0] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""


n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = deque()
q.append(0)
d_f[0] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import queue
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""


n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = deque()
q.append(0)
d_f[0] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import queue
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""


n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = queue.Queue()
q.put(0)
d_f[0] = 0
while not q.empty():
    x = q.get()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.put(y)
d_s = [-1 for i in range(n)]
q.put(n-1)
d_s[n-1] = 0
while not q.empty():
    x = q.get()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.put(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""


n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = []
q.append(0)
d_f[0] = 0
while q:
    x = q.pop(-1)
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop(-1)
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""


n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = deque()
q.append(0)
d_f[0] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")

Solution (Python):
n = int(input())
a = [[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)

def dfs(v):
    d = [-1 for i in range(n)]
    q = []
    d[v] = 0
    q.append(v)
    while len(q):
        v = q.pop()
        for i in a[v]:
            if d[i] == -1:
                d[i] = d[v]+1
                q.append(i)
    return d
c1 = dfs(0)
c2 = dfs(n-1)
c = 0
for i in range(n):
    if c1[i]>c2[i]:
        c += 1
if c>= n/2:
    print("Snuke")
else:
    print("Fennec")

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

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

i=0
b=1
w=1
f[1]=1
f[N]=1
bq=d[1]
wq=d[N]

while len(bq)>0 or len(wq)>0:
    tmp=[]
    if i==0:
        for q in bq:
            if f[q]==0:
                f[q]=1
                b+=1
                tmp+=d[q]
    else:
        for q in wq:
            if f[q]==0:
                f[q]=1
                w+=1
                tmp+=d[q]
    if i==0:
        i=1
        bq=tmp
    else:
        i=0
        wq=tmp

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

Solution (Python):
from collections import deque
n = int(input())
num_hen = n-1
info = [list(map(int,input().split())) for i in range(num_hen)]

for i in range(num_hen):
  info[i][0] -=1
  info[i][1] -=1

tree=[[] for i in range(n)]
for i in range(num_hen):
  tree[info[i][0]].append(info[i][1])
  tree[info[i][1]].append(info[i][0])
  

painted=[0]*n
painted[0]=1
painted[n-1]=-1



que = deque()
for i in range(len(tree[0])):
  que.append([tree[0][i],0])
visited=[False]*n 
visited[0]=True
keiro ={}
while que:
  v = que.pop()
  keiro[v[1]]=v[0]
  if v[0] == n-1:
    final = v[1]
    break
  elif not visited[v[0]]:
    for i in range(len(tree[v[0]])):
      que.append([tree[v[0]][i],v[1]+1])
    visited[v[0]]=True


for i in range(final):
  if i%2==0:
    painted[keiro[i//2]]=1
  else:
    painted[keiro[final-1-i//2]]=-1


def dfs(i,color):
  que2 = deque()
  for element in tree[i]:
    que2.append(element)
  while que2:
    w = que2.pop()
    if painted[w]==0:
      painted[w]=color
      for element in tree[w]:
        que2.append(element)
  return

for i in range(n):
  if painted[i]==1:
    dfs(i,1)
  elif painted[i]==-1:
    dfs(i,-1)

print("Fennec" if painted.count(1) > painted.count(-1) else "Snuke")

Solution (Python):
from collections import deque
n = int(input())
li = []
for _ in range(n - 1):
    li.append(list(map(int, input().split())))


edges = [set() for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].update({j})
    edges[j].update({i})


Q = deque()
Q.append([0, 0])
visited = {0}
pre = {}
while len(Q) > 0:
    u, d = Q.pop()
    if u == n - 1:
        i = (d - 1) // 2
        a = u
        for _ in range(i + 1):
            b = a
            a = pre[b]
        edges[a].remove(b)
        edges[b].remove(a)
        break
    for v in edges[u]:
        if v not in visited:
            pre[v] = u
            visited.update({v})
            Q.append([v, d + 1])


Q = deque()
Q.append(0)
visited = {0}
while len(Q) > 0:
    u = Q.pop()
    for v in edges[u]:
        if v not in visited:
            visited.update({v})
            Q.append(v)

ans = 'Snuke' if len(visited) <= n // 2 else 'Fennec'

print(ans)

Solution (Python):
from collections import deque

INF = 10 ** 20

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

def dijkstra(start):
    dist = [INF] * n
    dist[start] = 0
    que = deque()
    que.append((0, start))
    while que:
        score, node = que.popleft()
        for to in edges[node]:
            if dist[to] > score + 1:
                dist[to] = score + 1
                que.append((score + 1, to))
    return dist

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

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n=I()
nl=[[] for i in range(n)]
distfen=[-1 for i in range(n)]
distsnu=[-1 for i in range(n)]

for i in range(n-1):
    a,b=IL()
    nl[a-1].append(b-1)
    nl[b-1].append(a-1)
    
q=[[0,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distfen[v]=d+1
            q.append([v,d+1])

q=[[n-1,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distsnu[v]=d+1
            q.append([v,d+1])
        
fen=0
snu=0

for i in range(1,n-1):
    if distfen[i]<=distsnu[i]:
        fen+=1
    else:
        snu+=1

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


d1 = [None] * (N+1)
dn = [None] * (N+1)


def dfs(v, d, d_list):
    d_list[v] = d
    for nv in G[v]:
        if d_list[nv] is None:
            dfs(nv, d+1, d_list)

dfs(1, 0, d1)
dfs(N, 0, dn)

cnt = 0
for i in range(1, N+1):
    if d1[i] <= dn[i]:
        cnt += 1
    else:
        cnt -= 1

print('Fennec' if cnt > 0 else 'Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


d1 = [None] * (N+1)
dn = [None] * (N+1)


def dfs(v, d, d_list):
    d_list[v] = d
    for nv in G[v]:
        if d_list[nv] is None:
            dfs(nv, d+1, d_list)

dfs(1, 0, d1)
dfs(N, 0, dn)

cnt = 0
for i in range(1, N+1):
    if d1[i] <= dn[i]:
        cnt += 1
    else:
        cnt -= 1

print('Fennec' if cnt > 0 else 'Snuke')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


d1 = [None] * (N+1)
dn = [None] * (N+1)


def dfs(v, d, d_list):
    d_list[v] = d
    for nv in G[v]:
        if d_list[nv] is None:
            dfs(nv, d+1, d_list)

dfs(1, 0, d1)
dfs(N, 0, dn)

cnt = 0
for i in range(1, N+1):
    if d1[i] <= dn[i]:
        cnt += 1
    else:
        cnt -= 1

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

Solution (Python):
import queue

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

stack = [0]
visited = [False for _ in range(n)]
white = 0
black = 0
wQueue = queue.Queue()
wQueue.put(0)
bQueue = queue.Queue()
bQueue.put(n-1)

while 1:
    wSize = wQueue.qsize()
    if wSize != 0:
        for i in range(wSize):
            now = wQueue.get()
            if not visited[now]:
                white += 1
                visited[now] = True
                for j in range(len(ab[now])):
                        wQueue.put(ab[now][j])
    bSize = bQueue.qsize()
    if bSize != 0:
        for i in range(bSize):
            now = bQueue.get()
            if not visited[now]:
                black += 1
                visited[now] = True
                for j in range(len(ab[now])):
                        bQueue.put(ab[now][j])
    if wSize == 0 and bSize == 0:
        if white > black:
            print("Fennec")
        else:
            print("Snuke")
        
        exit()

Solution (Python):
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


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

path = Dijkstra(graph, 0, N - 1).execute()
cost = len(path) - 1

black = 1
if cost % 2 == 0:
    tmp = (cost - 1) // 2
    black += tmp + 1
else:
    tmp = (cost - 1) // 2
    black += tmp
not_path = set(path[black:])
visited = [False for _ in range(N)]
q = [0]
visited[0] = False
while len(q) != 0:
    dist = q.pop()
    for d in graph[dist].keys():
        if visited[d] or d in not_path:
            continue
        q.append(d)
        visited[d] = True
for p in tuple(path):
    visited[p] = False
for v in visited:
    if v:
        black += 1
white = N - black

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

Solution (Python):
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


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

path = Dijkstra(graph, 0, N - 1).execute()
cost = len(path) - 1

black = 1
if cost % 2 == 0:
    tmp = (cost - 1) // 2
    black += tmp + 1
else:
    tmp = (cost - 1) // 2
    black += tmp
not_path = set(path[black:])
visited = [False for _ in range(N)]
q = [0]
visited[0] = False
while len(q) != 0:
    dist = q.pop()
    for d in graph[dist].keys():
        if visited[d] or d in not_path:
            continue
        q.append(d)
        visited[d] = True
for p in path:
    visited[p] = False
for v in visited:
    if v:
        black += 1
white = N - black

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

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

fennec = [float('inf')] * (N+1)
snuke = [float('inf')] * (N+1)

def dfs(memo: list, cur: int, prev: int, dist: int) -> None:
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(memo, nxt, cur, dist+cost)

dfs(fennec, 1, -1, 0)
dfs(snuke, N, -1, 0)

fn = sn = 0
for i in range(2, N):
    
    if fennec[i] <= snuke[i]:
        fn += 1
    else:
        sn += 1

if fn > sn:
    print('Fennec')
else:
    print('Snuke')

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

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 dfs(n):
    dist = [-1] * N
    dist[n] = 0
    stack = [n]

    while stack:
        u = stack.pop()
        for v, c in T[u]:
            if dist[v] < 0:
                dist[v] = dist[u] + 1
                stack.append(v)
    return dist


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

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

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

Solution (Python):

from collections import defaultdict
from pprint import pprint as pp
N = int(input())
abn = [list(map(int, input().split())) for _ in range(N-1)]

graph = defaultdict(lambda: defaultdict(int))

for a,b in abn:
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1



def dist(x):
    que = [(x,0)]
    distance = [-1 for _ in range(N)]
    distance[x] = 0

    while len(que) > 0:
        i,tmpdist = que.pop(0)        

        for next in [k for k,v in  graph[i].items() if v == 1]:
            if distance[next] == -1:
                distance[next] = tmpdist + 1
                que.append((next, tmpdist + 1))

    return distance

distF = dist(0)

distS = dist(N-1)


Fcnt = 0
Scnt = 0
for f,s in zip(distF,distS):
    if f > s:
        Scnt += 1
    else:
        Fcnt += 1

if Fcnt > Scnt:
    print("Fennec")
else:
    print("Snuke")