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



Sample input:
7
3 6
1 2
3 1
7 4
5 7
1 4


Sample output:
Fennec

Submission status: Accepted

Solution code:
import heapq
 
"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""
 
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b = map(int,input().split())
    edge[a-1].append([1,b-1])
    edge[b-1].append([1,a-1])

dist_zero = dijkstra_heap(0,edge)
dist_n = dijkstra_heap(N-1,edge)
"""
print(dist_zero)
print(dist_n)
"""
b = 0
w = 0

for black,white in zip(dist_zero,dist_n):
    if black > white:
        w += 1
    else:
        b += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
    
def main():
    N = int(input())
    d = {}
    for _ in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    v = set()
    v.add(1)
    l = []
    def dfs(n):
        if n == N:
            l.append(n)
            return True
        for i in d[n]:
            if i not in v:
                v.add(i)
                if dfs(i):
                    l.append(n)
                    return True
        return False
    dfs(1)
    l.reverse()
    v = set()
    if len(l) % 2 == 0:
        half = len(l) // 2 - 1
    else:
        half = len(l) // 2
    v.add(l[half])
    s = l[half+1]
    v.add(s)
    def dfs2(n):
        r = 1
        for i in d[n]:
            if i not in v:
                v.add(i)
                r += dfs2(i)
        return r
    x = dfs2(s)
    if N - x > x:
        return 'Fennec'
    else:
        return 'Snuke'
print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    C = [0] * N
    B = set([0])
    W = set([N - 1])
    C[0] = 1
    C[-1] = -1
    while B or W:
        BN = set()
        for b in B:
            for bb in E[b]:
                if bb != b and C[bb] == 0:
                    C[bb] = 1
                    BN.add(bb)
        B = BN
        WN = set()
        for w in W:
            for ww in E[w]:
                if ww != w and C[ww] == 0:
                    C[ww] = -1
                    WN.add(ww)
        W = WN
    return 'Fennec' if C.count(1) > C.count(-1) else 'Snuke'

print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from collections import deque
N=int(input())

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

dist_f=[-1]*(N+1)
d=0
queue=[1]
while queue:  
  new_queue=set()
  for u in queue:
    dist_f[u]=d
    for v in graph[u]:
      if dist_f[v]==-1:
        new_queue.add(v)
        
  queue=list(new_queue)
  d+=1
#print(dist_f)

dist_s=[-1]*(N+1)
d=0
queue=[N]
while queue:  
  new_queue=set()
  for u in queue:
    dist_s[u]=d
    for v in graph[u]:
      if dist_s[v]==-1:
        new_queue.add(v)
        
  queue=list(new_queue)
  d+=1
#print(dist_s)

cnt_f,cnt_s=0,0
for i in range(1,N+1):
  if dist_f[i]<=dist_s[i]:
    cnt_f+=1
  else:
    cnt_s+=1

#print(cnt_f,cnt_s)
if cnt_f>cnt_s:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque

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

edges = [[] for _ in range(N + 1)]
for u, v in X:
    edges[u].append(v)
    edges[v].append(u)


def bfs(s, x):
    inf = 10 ** 9 + 7
    d = [inf] * (N + 1)
    d[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in edges[u]:
            if d[v] != inf:
                continue

            d[v] = d[u] + 1
            if v != x:
                q.append(v)

    return d


d1 = bfs(1, N)
d2 = bfs(N, 1)

cnt = 0
for i in range(1, N + 1):
    cnt += d1[i] <= d2[i]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import heapq
def dijkstra(s):
    # 始点sから各頂点への最短距離
    d = [float('inf')]*n
    d[s] = 0
    # 各頂点が訪問済みかどうか
    used = [False]*n
    used[s] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in edge[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

################################
n = int(input()) #n:頂点数　w:辺の数
w = n - 1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    z = 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

dis_from_f = dijkstra(0)
dis_from_s = dijkstra(n - 1)

cnt = 0
for i, j in zip(dis_from_f, dis_from_s):
    if i <= j:
        cnt += 1
if cnt > n - cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

dist = [0] * N
def dfs(u, d, p=-1):
    global dist
    dist[u] = d
    for v in edges[u]:
        if v == p:
            continue
        dfs(v, d + 1, u)
    return dist

dist1 = dfs(0, 0, -1)
dist = [0] * N
dist2 = dfs(N - 1, 0, -1)

cnt = 0
for d1, d2 in zip(dist1, dist2):
    if d1 <= d2:
        cnt += 1
if N - cnt < cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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


from collections import deque
seen = [False for _ in range(n)]
child = [[] for _ in range(n)]
par = [0 for _ in range(n)]
order = []
que = deque()
que.append(0)
seen[0] = True

while que:
    v = que.popleft()
    order.append(v)
    for to in edges[v]:
        if not seen[to]:
            seen[to] = True
            par[to] = v
            que.append(to)
            child[v].append(to)

d = [-1 for _ in range(n)]
c = [0 for _ in range(n)]
for i in order:
    d[i] = d[par[i]] + 1
for i in order[::-1]:
    if len(child[i]) == 0:
        continue
    for ch in child[i]:
        c[i] += c[ch] + 1



point = n - 1
move_s = (d[n-1] - 1) // 2
move_f = d[n-1] - 1 - move_s
for i in range((d[n-1] - 1) // 2):
    point = par[point]

cnt_s = c[point]
cnt_f = n - (c[point] + 1) - 1


print('Fennec' if cnt_f > cnt_s else 'Snuke')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n = int(input()) #n:頂点数　w:辺の数
w = n - 1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    z = 1
    edge[x].append([z,y])
    edge[y].append([z,x]) 

dis_from_f = dijkstra_heap(0)
dis_from_s = dijkstra_heap(n - 1)

cnt = 0
for i, j in zip(dis_from_f, dis_from_s):
    if i <= j:
        cnt += 1
if cnt > n - cnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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)

def dfs(v,d,dist):
    dist[v] = d
    for ve in edge[v]:
        if dist[ve] is None:
            dist = dfs(ve, d+1, dist)
    return dist
    
    
f_dist = dfs(0,0,[None]*n)
s_dist = dfs(n-1,0,[None]*n)

fget = sum(1 for f,s in zip(f_dist,s_dist) if f<=s)
print("Fennec" if fget*2>n else "Snuke")

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
for _i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

visit = [-1 for _ in range(n)]
f, s = 0, 0
f_q = deque([0])
s_q = deque([n-1])

while f_q or s_q:
    g = []
    while f_q:
        p = f_q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                f += 1
                g.append(i)
                visit[i] = 0
    f_q = deque(g)

    g = []
    while s_q:
        p = s_q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                s += 1
                g.append(i)
                visit[i] = 0
    s_q = deque(g)
if f > s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
N = int(input())
g = [[] for _ in range(N + 5)]
Fennec = [0]*(N+10)
Sunuke = [0]*(N+10)
sys.setrecursionlimit(10**8)

def dfs(r,f,d,dist):
	dist[r]=d
	for x in range(len(g[r])):
		if g[r][x]==f : continue
		else : dfs(g[r][x],r,d+1,dist)

# main

for i in range(N-1):
	a,b=map(int,input().split())
	a-=1
	b-=1
	g[a].append(b)
	g[b].append(a)
dfs(0,-1,0,Fennec)
dfs(N-1,-1,0,Sunuke)
ans = int(0)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
read = sys.stdin.read

N, *ab = map(int, read().split())
a, b = zip(*zip(*[iter(ab)] * 2))

graph = csr_matrix(([1] * (N - 1), (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False, indices=[1, N])
d1 = distance[0][1:]
dn = distance[1][1:]

Fennec = np.count_nonzero(d1 <= dn)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

for x,y in a:
    b[x-1].append(y-1)
    b[y-1].append(x-1)

# グラフでのbfs
import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1


        return dis
    return bfs()

fennec=tree(0)
snuke=tree(n-1)

# ans1:fennecの取り分
# ans2:sunukeの取り分
ans1=0
ans2=0
for i in range(n):
    if fennec[i]<=snuke[i]:
        ans1+=1
    else:
        ans2+=1

if ans1>ans2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

n = int(input())
edges = [[] for _ 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 get_dists(f):
    dists = [0 for _ in range(n)]
    q = deque()
    q.append((f, -1, 0))
    while len(q) > 0:
        num, f_num, dist = q.popleft()
        for node in edges[num]:
            if node == f_num:
                continue
            else:
                dists[node] = dist + 1
                q.append((node, num, dist+1))
    return dists

dist_1 = get_dists(0)
dist_n = get_dists(n-1)

ans = 0
for i in range(n):
    if dist_1[i] <= dist_n[i]:
        ans += 1

fennec = ans
snuke = n - fennec
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

from collections import deque



def submit():
    n = int(input())
    edge = {i: [] for i in range(1, n + 1)}
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge[a].append(b)
        edge[b].append(a)

    # 1とNの最短路を求める
    def dfs(q, path, hist):
        p = q.pop()
        if p == n:
            return path

        for e in edge[p]:
            if not hist[e]:
                q.append(e)
                path.append(e)
                hist[e] = True
                ret = dfs(q, path, hist)
                if ret:
                    return ret
                path.pop(-1)
        return None


    q = deque()
    q.append(1)
    hist = {i: False for i in range(n + 1)}
    hist[1] = True
    direct_path = dfs(q, [1], hist)
    d = len(direct_path) 
    if d % 2:
        fennec = direct_path[:d // 2 + 1]
        snuke = direct_path[d // 2 + 1:]
    else:
        fennec = direct_path[:d // 2]
        snuke = direct_path[d // 2:]

    edge[fennec[-1]].remove(snuke[0])
    
    # fennecが取れる数を数える
    color = 0
    picked = [False for _ in range(n)]
    q = deque()
    q.append(1)
    picked[0] = True
    while len(q):
        p = q.pop()
        color += 1
        for e in edge[p]:
            if not picked[e - 1]:
                q.append(e)
                picked[e - 1] = True
    
    if color > n - color:
        print("Fennec")
    else:
        print("Snuke")


submit()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

lst=[0]*(n+1)
f=deque([1])
s=deque([n])
fcnt,scnt=0,0
while 1:
    flag=0
    for i in range(len(f)):
        tmp=f.popleft()
        if lst[tmp]==0:
            lst[tmp]=1
            fcnt+=1
            flag=1
            for j in dic[tmp]:
                f.append(j)
    
    for i in range(len(s)):
        tmp=s.popleft()
        if lst[tmp]==0:
            lst[tmp]=1
            scnt+=1
            flag=1
            for j in dic[tmp]:
                s.append(j)
    
    if flag==0:
        break
    

if fcnt>scnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque
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)

dist_f = [None]*n
dist_s = [None]*n

que = deque([(0,0)])
while que:
    node, cost = que.popleft()
    if dist_f[node] != None:
        continue
    dist_f[node] = cost
    for to in g[node]:
        que.append((to, cost+1))

que = deque([(n-1, 0)])
while que:
    node, cost = que.popleft()
    if dist_s[node] != None:
        continue
    dist_s[node] = cost
    for to in g[node]:
        que.append((to, cost+1))
        
cnt = 0
for i in range(n):
    if dist_f[i] <= dist_s[i]:
        cnt += 1
print('Fennec' if cnt>n-cnt else 'Snuke')

Submission status: Accepted

Solution code:
import queue
import sys
sys.setrecursionlimit(10 ** 7)

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

G = [[] for _ in range(N + 1)]
for el in ab:
    a, b = el
    G[a].append(b)
    G[b].append(a)

seen = [False] * (N + 1)
todo = queue.Queue()
dist = [0] * (N + 1)
prev = [None] * (N + 1)

def bfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            todo.put(child)
            dist[child] = dist[parent] + 1
            prev[child] = parent
    if not todo.empty():
        bfs(todo.get())

bfs(1)
#print(dist)
#print(prev)
min_dist = dist[N]
#print(min_dist)

route = []
temp = N
for _ in range(min_dist + 1):
    route.append(temp)
    temp = prev[temp]
#print(route)


seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    cnt[0] += 1
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)


S = route[(min_dist + 1) // 2 - 1]
F = route[(min_dist + 1) // 2]

seen[S] = True
seen[F] = True
cnt = [0]
dfs(S)
arround_S = cnt[0]
cnt = [0]
dfs(F)
arround_F = cnt[0]
#print(arround_N, arround_1)

if arround_F > arround_S:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    N = int(input())
    Graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        Graph[a].add(b)
        Graph[b].add(a)

    Fennec = [-1] * N
    Snuke = [-1] * N

    def bfs(start, arr):
        arr[start] = 0
        dq = deque()
        dq.append(start)
        while dq:
            v = dq.popleft()
            d = arr[v]
            for u in Graph[v]:
                if ~arr[u]:
                    continue
                arr[u] = d + 1
                dq.append(u)

    bfs(start=0, arr=Fennec)
    bfs(start=N - 1, arr=Snuke)

    cnt_f = sum(1 for f, s in zip(Fennec, Snuke) if f <= s)
    cnt_s = N - cnt_f

    print('Fennec' if cnt_f > cnt_s else 'Snuke')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
edge = []
hand_a = [100005]*(n+1)
hand_b = [100005]*(n+1)
for i in range(n+1):
    edge.append([])
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

# print(edge)
def dfs(start, goal, hand):
    cnt = 0
    hand[start] = 0
    stack = [start]
    used = set()
    used.add(start)
    while stack:
        here = stack.pop()
        cnt += 1
        for i in edge[here]:
            if i == goal:
                pass
            elif i not in used:
                stack.append(i)
                used.add(i)
                hand[i] = hand[here] + 1
    return cnt, used


cnt_a, used_a = dfs(1, n, hand_a)
cnt_b, used_b = dfs(n, 1, hand_b)
# print(cnt_a, cnt_b)
# print(used_a, used_b)
# print(hand_a, hand_b)
a_ans = b_ans = 0
for i in range(1,n+1):
    if hand_a[i] <= hand_b[i]:
        a_ans += 1
    else:
        b_ans += 1
if a_ans > b_ans:
    print("Fennec")
else:
    print("Snuke")



# work_q = deque([1])
# used = set()
# used.add(1)
# ans[1] = cost[1]
# cnt = 0
# while work_q:
#     here = work_q.popleft()
#     cnt = ans[here]
#     for i in edge[here]:
#         if i not in used:
#             work_q.append(i)
#             used.add(i)
#             ans[i] = cnt + cost[i]
# print(*ans[1:])

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 067
# D - Fennec VS. Snuke
# https://atcoder.jp/contests/abc067/tasks/arc078_b
import sys
from collections import deque

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

# bfs
def bfs(s):
    q = deque()
    q.append(s)
    D = [0]*N
    visited = [False]*N
    while q:
        v = q.popleft()
        visited[v] = True
        d = D[v]

        for u in G[v]:
            if visited[u]:
                continue
            D[u] = d+1
            q.append(u)

    return D


Df = bfs(0)
Ds = bfs(N-1)

cnt_f = 0
cnt_s = 0
for df, ds in zip(Df, Ds):
    if df <= ds:
        cnt_f += 1
    else:
        cnt_s += 1

print('Fennec' if cnt_f > cnt_s else 'Snuke')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
n = int(input())
ki = [[]for _ in range(n)]
dist1 = [0]*n
distN = [0]*n
def dfs1(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        dist1[next] = dist1[now]+1
        dfs1(next,now)
def dfsN(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        distN[next] = distN[now]+1
        dfsN(next,now)
        
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
fs = 0
dfs1(0)
dfsN(n-1)
for i in range(n):
    if dist1[i] <= distN[i]:fs+=1
ss = n-fs
if fs > ss:print('Fennec')
else:print('Snuke')

Submission status: Accepted

Solution code:
import collections
N = int(input())
G = [set() for i in range(N)]

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


F = [-1]*N
F[0] = 0
q = collections.deque()
q.append(0)
while(q):
    x = q.popleft()
    for y in G[x]:
        if F[y] < 0:
            F[y] = F[x] + 1
            q.append(y)

S = [-1]*N
S[N-1] = 0
q.append(N-1)
while(q):
    x = q.popleft()
    for y in G[x]:
        if S[y] < 0:
            S[y] = S[x] + 1
            q.append(y)
# print(F)
# print(S)
ans = 0

q = collections.deque()
r = [True]*N
for i in range(N):
    if F[i] + S[i] == F[-1]:
        if F[i] <= S[i]:
            q.append(i)
            r[i] = False
        else:
            r[i] = False
ans = len(q)

while(q):
    x = q.popleft()
    for y in G[x]:
        if r[y]:
            ans += 1
            q.append(y)
            r[y] = False

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

Submission status: Accepted

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

from collections import deque
dist_f=[-1]*n
dist_f[0]=0
q=deque()
q.append(0)
while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_f[nx]==-1:
            dist_f[nx]=dist_f[cur]+1
            q.append(nx)

dist_s=[-1]*n
dist_s[n-1]=0
q=deque()
q.append(n-1)
while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_s[nx]==-1:
            dist_s[nx]=dist_s[cur]+1
            q.append(nx)
fenec,sunuke=0,0
for i in range(n):
    if dist_f[i]<=dist_s[i]:
        fenec+=1
    else:
        sunuke+=1
print("Fennec") if fenec>sunuke else print("Snuke")

Submission status: Accepted

Solution code:
def examA():
    def calc_L(x1,y1,x2,y2):
        return ((x2-x1)**2 + (y2-y1)**2)**0.5
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    for x in itertools.permutations(X):
        cur = 0
        for i in range(1,N):
            cur += calc_L(x[i-1][0],x[i-1][1],x[i][0],x[i][1])
        #print(x,cur)
        ans += cur
    for i in range(1,N+1):
        ans /= i
    print(ans)
    return

def examB():
    def judge(n):
        sn = 0
        for i in n:
            sn += int(i)
        if int(n)%sn==0:
            return "Yes"
        return "No"
    N = SI()
    ans = judge(N)
    print(ans)
    return

def examC():
    N, K = LI()
    P = LI()
    ans = 0
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    for i in range(N-K+1):
        cur = S[i+K] - S[i]
        if cur>ans:
            ans = cur
    print(ans)
    return

def examD():
    def bfs(n,V,s,W):
        visited = [False]*n
        que = deque()
        que.append(s)
        while(que):
            now = que.pop()
            visited[now] = True
            for ne in V[now]:
                if visited[ne]:
                    continue
                W[ne] += W[now]
                que.append(ne)
        return W
    N, Q = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    W = [0] * N
    for _ in range(Q):
        p, x = LI()
        W[p-1] += x
    ans = bfs(N,V,0,W)
    print(" ".join(map(str,ans)))
    return

def examE():
    def bfs(n,edges,s):
        L = [inf]*n
        que = deque()
        que.append(s)
        L[s] = 0
        while(que):
            now = que.popleft()
            for ne in edges[now]:
                if L[ne]>L[now]+1:
                    L[ne] = L[now]+1
                    que.append(ne)
        return L
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    F = bfs(N,V,0)
    S = bfs(N,V,N-1)
    f = 0; s = 0
    for i in range(N):
        if F[i]>S[i]:
            s += 1
        else:
            f += 1
    if f>s:
        print("Fennec")
    else:
        print("Snuke")
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def calc(s):
    st = [s]
    minDist = [10**18] * N
    minDist[s] = 0
    while st:
        now = st.pop()
        for to in edges[now]:
            if minDist[to] > minDist[now] + 1:
                minDist[to] = minDist[now] + 1
                st.append(to)
    return minDist

A = calc(0)
B = calc(N - 1)

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

Submission status: Accepted

Solution code:
def dijkstra(G, s):
    # sを始点としてすべての点への最短距離を求める
    inf = 10**18
    n = len(G)
    D = [inf for i in range(n)]
    D[s] = 0
    Q = [s]
    while Q:
        x = Q.pop()
        for y in G[x]:
            if D[y] > D[x] + 1:
                D[y] = D[x] + 1
                Q.append(y)
    return D


n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
D0 = dijkstra(G, 0)
D1 = dijkstra(G, n-1)
c0, c1 = 0, 0
for i in range(n):
    if D0[i] <= D1[i]:
        c0 += 1
    else:
        c1 += 1
if c0 > c1:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
N = int(input())
from collections import defaultdict
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)


dist2 = [-1]*N
que = deque([N-1])
dist2[N-1] = 0
while que:
    v = que.popleft()
    d = dist2[v]
    for w in G[v]:
        if dist2[w] > -1:
            continue
        dist2[w] = d + 1
        que.append(w)

ans = [0, 0]
for a,b in zip(dist, dist2):
    if a <= b:
        ans[0] += 1
    else:
        ans[1] += 1



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

Submission status: Accepted

Solution code:
from collections import deque

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)

def dist_from_X(X:int):
    """ BFSで距離を求める """
    dist = [-1] * N
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        for w in edge[v]:
            if dist[w] < 0:
                dist[w] = dist[v] + 1
                que.append(w)
    return dist

Fennec = dist_from_X(0)
Snuke = dist_from_X(N - 1)

# 距離同じ -> Fennec
cntF, cntS = 0,0
for f,s in zip(Fennec, Snuke):
    if f <= s:
        cntF += 1
    else:
        cntS += 1

# cntが同じ -> Snuke
if cntF > cntS:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
def dfs(v):
  dist = [-1]*n
  dist[v] = 0
  stack = [v]
  while stack:
    nv = stack.pop()
    for i in T[nv]:
      if dist[i] == -1:
        dist[i] = dist[nv] + 1
        stack.append(i)
  return dist
B = dfs(0)
W = dfs(n-1)
cnt_b, cnt_w = 0, 0
for i in range(n):
  if B[i] <= W[i]:
    cnt_b += 1
  else:
    cnt_w += 1
if cnt_b > cnt_w:
  print("Fennec")
else:
  print("Snuke")