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:
n = int(input())

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

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

Submission status: Accepted

Solution code:
# unionfindで共通部分の数調べたらいけるかと思ったけど
# 共通部分の構造が重要だった...

# 知りたいのは0とn-1間のパス上における優劣
# →BFSで各頂点までの距離を調べると白黒どちらになるか分かる

# (おまけ)各頂点に付けた順位はその数字の手数以下で
# どちらかの色がつくことが確定している

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    black = [-1] * n
    white = [-1] * n
    f = deque([0])
    black[0] = 0
    s = deque([n-1])
    white[-1] = 0

    def bfs(q, color):
        while q:
            v = q.popleft()
            for nv in adj[v]:
                if color[nv] < 0:
                    color[nv] = color[v] + 1
                    q.append(nv)

    bfs(f, black)
    bfs(s, white)
    cnt = 0
    for i in range(n):
        if black[i] <= white[i]:
            cnt += 1
    if cnt > n-cnt:
        print('Fennec')
    else:
        print('Snuke')



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys


def bfs(s, trail):
    q = deque()
    q.append((s, 0))
    trail[s] = 0
    while q:
        p, step = q.popleft()
        for np in edge[p]:
            nstep = step + 1
            if trail[np] > nstep:
                q.append((np, nstep))
                trail[np] = nstep


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


INF = 10 ** 9
path0 = [INF] * N
pathN = [INF] * N

bfs(0, path0)
bfs(N - 1, pathN)

fennec = 0
snuke = 0
for i in range(N):
    if path0[i] <= pathN[i]:
        fennec += 1
    else:
        snuke += 1

ans = 'Fennec' if fennec > snuke else 'Snuke'
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

distF = [-1]*N
distS = [-1]*N
def bfs(s,dist):
    q = deque([])
    q.append([s,0])
    while len(q) != 0:
        v = q.popleft()
        dist[v[0]] = v[1]
        for nv in edge[v[0]]:
            if dist[nv] != -1:
                continue

            dist[nv] = dist[v[0]] + 1
            q.append([nv,dist[nv]])

bfs(0,distF)
bfs(N-1,distS)
# print(distF)
# print(distS)
Fennec = 0
Snuke = 0
for i in range(N):
    if distF[i] <= distS[i]:
        Fennec += 1
    else:
        Snuke += 1
# print(Fennec)
# print(Snuke)
if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
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)
d1=[-1]*n
d2=[-1]*n
q1=[0]
d1[0]=0
while q1:
  x=q1.pop()
  for t in g[x]:
    if d1[t]==-1:
      d1[t]=d1[x]+1
      q1.append(t)
q2=[n-1]
d2[n-1]=0
while q2:
  x=q2.pop()
  for t in g[x]:
    if d2[t]==-1:
      d2[t]=d2[x]+1
      q2.append(t)
cnt=0
for i in range(n):
  if d1[i]<=d2[i]:
    cnt+=1
if cnt>n//2:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1

N = int(input())
P = np.array([tuple(map(int1, input().split())) for _ in range(N - 1)]).T

matr = csr_matrix((np.ones(N - 1, dtype=int), P), shape=(N, N))
way_F = dijkstra(matr, indices=0, directed=False).astype(int)
way_F[way_F < 0] = N + 1
way_S = dijkstra(matr, indices=N - 1, directed=False).astype(int)
way_S[way_F < 0] = N + 1

fc = np.count_nonzero(way_F <= way_S)
print('Fennec' if fc > N - fc else 'Snuke')

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
V=[0]*n
V[0]=1
P=[0]*n
P[0]=-1
C=[1]*n
D=deque([0])
DD=deque([0])
GG=[[] for i in range(n)]
while len(D)>0:
  v=D[0]
  D.popleft()
  for i in range(len(G[v])):
    if V[G[v][i]]==0:
      V[G[v][i]]=1
      D.append(G[v][i])
      DD.append(G[v][i])
      P[G[v][i]]=v
DD=list(DD)[::-1]
for i in range(n):
  if DD[i]!=0:
    C[P[DD[i]]]+=C[DD[i]]
a=0
i=n-1
while i!=0:
  i=P[i]
  a=a+1
i=n-1
for _ in range((a-1)//2):
  i=P[i]
s=C[i]
f=n-C[i]
if f>s:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
N=int(input())
hen={i:set([]) for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    hen[a].add(b)
    hen[b].add(a)

parent={i:-1 for i in range(1,N+1)}
parent[1]=0
q=set([])
sub=set([])
q.add(1)
while q:
    while q:
        x=q.pop()
        for p in hen[x]:
            if parent[p]==-1:
                parent[p]=x
                sub.add(p)

        if not q:
            q=sub
            sub=set([])
            break

subtreesize={i:1 for i in range(1,N+1)}
q=set([])
for i in range(1,N+1):
    if i!=1 and len(hen[i])==1:
        q.add(i)
sub=set([])
flag={i:0 for i in range(1,N+1)}
while q:
    while q:
        x=q.pop()
        p=parent[x]
        if p!=1:
            subtreesize[p]+=subtreesize[x]
            flag[p]+=1
            if flag[p]==len(hen[p])-1:
                sub.add(p)
        else:
            subtreesize[1]+=subtreesize[x]

        if not q:
            q=sub
            sub=set([])
            break

s=N
load=[N]
while s!=1:
    s=parent[s]
    load.append(s)


depth=len(load)
white=subtreesize[load[depth//2-1]]
black=N-white
if white>=black:
    print('Snuke')
else:
    print('Fennec')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc067/tasks/arc078_b
# 1とNの最短経路について注目したときに、それぞれの最適戦略を考えてみる
# 相手を負かせたい→相手側に攻めて道を塞ぐのが有利(相手のマスが少なくなるから)
# 自分が負けそう→退避して行きたい(でも相手のマスのほうが多かったらもう逆転は不可能)
# 勝者は→先にたどり着けるノードの中で多い方が勝者(同数の場合はFennecが敗者)

import sys
read = sys.stdin.readline
from collections import defaultdict, deque


def read_ints():
    return list(map(int, read().split()))


class Tree:
    def __init__(self, N):
        '''重み付き無向木構造をクラスにしてみる(余り意味はなさそう)'''
        from collections import defaultdict, deque
        self.N = N
        self.tree = defaultdict(lambda: [])
        self.dists = None
        self.parents = None
        self.root = None

    def _link(self, a, b, d):
        '''
        d is a distance between a and b
        '''
        self.tree[a].append((b, d))
        self.tree[b].append((a, d))

    def _init_dists(self, root=0):
        self.dists = [-1] * self.N
        self.parents = [-1] * self.N
        que = deque([(root, -1, 0)])  # 現在のノード、前のノード、距離
        self.dists[root] = 0
        while que:
            u, p, d = que.popleft()
            self.parents[u] = p
            for nu, dadd in self.tree[u]:
                if nu == p:  # 親はもう探索しない
                    continue
                nd = d + dadd
                self.dists[nu] = nd
                que.append((nu, u, nd))

    def ret_dist(self, a, b):
        '''
        a,b間の距離を高速に取得する
        '''
        raise NotImplementedError()
        if self.parents == None:
            self._init_dists()
        # aとbの共通祖先を見つける必要がある
        # 共通祖先ってどうやって持ってくるんだろう...

    def ret_dists(self, u):
        '''
        uを始点とした各点への距離を返す (うまくやれば二度目は高速化できそう？)
        '''
        ret = [-1] * self.N
        que = deque([(u, -1, 0)])  # 現在のノード、前のノード、距離
        ret[u] = 0
        while que:
            u, p, d = que.popleft()
            for nu, dadd in self.tree[u]:
                if nu == p:  # 親はもう探索しない
                    continue
                nd = d + dadd
                ret[nu] = nd
                que.append((nu, u, nd))
        return ret


N = int(input())
graph = Tree(N)
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph._link(a, b, 1)

# def ret_dists(u):
#     ret = [-1] * N
#     que = deque([(u, -1, 0)])  # 現在のノード、前のノード、距離
#     ret[u] = 0
#     while que:
#         u, p, d = que.popleft()
#         nd = 1 + d
#         for nu in graph[u]:
#             if nu == p:  # 親はもう探索しない
#                 continue
#             ret[nu] = nd
#             que.append((nu, u, nd))

#     return ret


fennec_dist = graph.ret_dists(0)
snuke_dist = graph.ret_dists(N - 1)

n_snuke = 0  # snukeに近いノードの数
n_fennec = 0  # 0を含んでfennecに近い #fennecが塗れるので
for f, s in zip(fennec_dist, snuke_dist):
    if f > s:  # すぬけにちかい
        n_snuke += 1
    else:
        n_fennec += 1

# print(n_fennec, n_snuke)
if n_fennec > n_snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc067/tasks/arc078_b
# 1とNの最短経路について注目したときに、それぞれの最適戦略を考えてみる
# 相手を負かせたい→相手側に攻めて道を塞ぐのが有利(相手のマスが少なくなるから)
# 自分が負けそう→退避して行きたい(でも相手のマスのほうが多かったらもう逆転は不可能)
# 勝者は→先にたどり着けるノードの中で多い方が勝者(同数の場合はFennecが敗者)

import sys
read = sys.stdin.readline
from collections import defaultdict, deque


def read_ints():
    return list(map(int, read().split()))


N = int(input())
graph = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


def ret_dists(u):
    ret = [-1] * N
    que = deque([(u, -1, 0)])  # 現在のノード、前のノード、距離
    ret[u] = 0
    while que:
        u, p, d = que.popleft()
        nd = 1 + d
        for nu in graph[u]:
            if nu == p:  # 親はもう探索しない
                continue
            ret[nu] = nd
            que.append((nu, u, nd))

    return ret


fennec_dist = ret_dists(0)
snuke_dist = ret_dists(N - 1)

n_snuke = 0  # snukeに近いノードの数
n_fennec = 0  # 0を含んでfennecに近い #fennecが濡れるので
for f, s in zip(fennec_dist, snuke_dist):
    if f > s:  # すぬけにちかい
        n_snuke += 1
    else:
        n_fennec += 1

# print(n_fennec, n_snuke)
if n_fennec > n_snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

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

def tree(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        par[x]=p
        descend[p]+=tree(x)
    return descend[p]

n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
if l%2==0: print("Fennec" if p<q else "Snuke")
else: print("Fennec" if p<=q else "Snuke")

Submission status: Accepted

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

def tree(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        par[x]=p
        descend[p]+=tree(x)
    return descend[p]

n=int(input())
neighbor=[set()  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
if l%2==0: print("Fennec" if p<q else "Snuke")
else: print("Fennec" if p<=q else "Snuke")

Submission status: Accepted

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

def cur(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        else:
            par[x]=p
            descend[p]+=cur(x)
    neighbor[p].remove(par[p])
    return descend[p]

n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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


x=[descend[n]-1]
t=n
while t!=1:
    t,pret=par[t],t
    x.append(descend[t]-descend[pret]-1)

l=len(x)
p,q=sum(x[:l//2]),sum(x[l//2:])
if l%2==0: print("Fennec" if p<q else "Snuke")
else: print("Fennec" if p<=q else "Snuke")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
def even(n): return 1 if n%2==0 else 0

n = int(readline())
g = [[] for i in range(n)] #g[i]:点iに隣接している点のリスト
for i in range(n-1):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)

dist_fe = [10**10]*n
dist_su = [10**10]*n

dist_fe[0] = 0
dist_su[n-1] = 0

def bfs(d,v,dist):
    for i in g[v]:
        if d[i] == 10**10:
            d[i] = dist+1
            bfs(d,i,dist+1)

bfs(dist_fe,0,0)
bfs(dist_su,n-1,0)

b = 0
w = 0

for i in range(n):
    if dist_fe[i] <= dist_su[i]: #先手優先
        b += 1
    else:
        w += 1

ans = "Fennec" if b > w else "Snuke"
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)
 
from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=1
prev=[-1]*n
 
while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=1
        Q.append(nxt)
        prev[nxt]=now
 
rt=[n-1]
now=n-1
while prev[now]!=-1:
    now=prev[now]
    rt.append(now)
rt.reverse()
cut= -(-len(rt)//2)
f_node=rt[cut-1]
s_node=rt[cut]
 
Q = deque()
Q.append([0,0]) # 0 is f, 1 if s
visited=[-1]*n
visited[0]=0
 
while Q:
    now,fs = Q.popleft()
    for nxt in link[now]:
        nxt_fs=fs
        if now==f_node and nxt==s_node:
            nxt_fs=1
        if visited[nxt]!=-1:
            continue
        visited[nxt]=nxt_fs
        Q.append([nxt,nxt_fs])
s_score = sum(visited)
f_score = n-s_score
if s_score >= f_score:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

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

dist_zero = [-1]*n
dist_zero[0] = 0
queue = deque()
queue.append(0)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_zero[to] == -1:
            dist_zero[to] = dist_zero[now] + 1
            queue.append(to)

dist_n = [-1]*n
dist_n[-1] = 0
queue = deque()
queue.append(-1)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist_n[to] == -1:
            dist_n[to] = dist_n[now] + 1
            queue.append(to)

f = sum([(dist_zero[i]<=dist_n[i]) for i in range(n)])

print("Fennec" if 2*f > n else "Snuke")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

stack = deque([0])
visit_in = [-1]*N
visit_in[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if visit_in[y] >= 0:
            continue
        visit_in[y] = x
        stack.append(y)

path = [N-1]

while path[-1] != 0:
    path.append(visit_in[path[-1]])

#print(path)

group = [-1]*N

for x in path:
    group[x] = x

stack = deque(path[:])

while stack:
    x = stack.pop()
    for y in data[x]:
        if group[y] != -1:
            continue
        group[y] = group[x]
        stack.append(y)

#print(group)

num = [0]*N
for i in range(N):
    num[group[i]] += 1

#print(num)

p = len(path)-1
q = 0
fennec = num[0]
snuke = num[N-1]
#print(fennec,snuke)
while q < p - 1:
    p -= 1
    fennec += num[path[p]]
    if q < p -1:
        q += 1
        snuke += num[path[q]]
    #print(fennec,snuke)
    

if fennec <= snuke:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
#from scipy.misc import comb

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)

d_F = [0] + [-1]*(N-1)
d_S = [-1]*(N-1) + [0]

q_F = deque([0])
q_S = deque([N-1])

while len(q_F) > 0:
    u = q_F.popleft()
    for v in G[u]:
        if d_F[v] == -1:
            d_F[v] = d_F[u] + 1
            q_F.append(v)

while len(q_S) > 0:
    u = q_S.popleft()
    for v in G[u]:
        if d_S[v] == -1:
            d_S[v] = d_S[u] + 1
            q_S.append(v)

black = 0
white = 0
for i in range(N):
    if d_F[i] <= d_S[i]: black += 1
    else: white += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    fen_dist, sun_dist = [0] * N, [0] * N
    
    def dfs1(node, parent, dist):
        fen_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs1(child, node, dist + 1)
    
    def dfs2(node, parent, dist):
        sun_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs2(child, node, dist + 1)
    
    dfs1(0, -1, 0)
    dfs2(N - 1, -1, 0)
    
    cnt_fen, cnt_sun = 0, 0
    for i in range(N):
        if fen_dist[i] <= sun_dist[i]:
            cnt_fen += 1
        else:
            cnt_sun += 1
    
    if cnt_fen <= cnt_sun:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=1
prev=[-1]*n

while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=1
        Q.append(nxt)
        prev[nxt]=now

rt=[n-1]
now=n-1
while prev[now]!=-1:
    now=prev[now]
    rt.append(now)
rt.reverse()
cut= -(-len(rt)//2)
f_node=rt[cut-1]
s_node=rt[cut]

Q = deque()
Q.append([0,0]) # 0 is f, 1 if s
visited=[-1]*n
visited[0]=0

while Q:
    now,fs = Q.popleft()
    for nxt in link[now]:
        nxt_fs=fs
        if now==f_node and nxt==s_node:
            nxt_fs=1
        if visited[nxt]!=-1:
            continue
        visited[nxt]=nxt_fs
        Q.append([nxt,nxt_fs])
s_score = sum(visited)
f_score = n-s_score
if s_score >= f_score:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)

def main():
    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)
    
    depth = [-1] * n
    depth[0] = 0
    snuke = [0] * n
    snuke[-1] = 1
    children = [1] * n

    def dfs(i):
        if len(G[i]) == 0:
            return
        else:
            for e in G[i]:
                if depth[e] == -1:
                    depth[e] = depth[i] + 1
                    dfs(e)
                    snuke[i] |= snuke[e]
                    children[i] += children[e] 
  
    dfs(0)
    white = depth[-1]//2 + 1
    for i in range(n):
        if depth[i] == white and snuke[i]:
            sp = children[i]
            fp = n - sp
            break
    
    if  fp > sp:
        print('Fennec')
    else:
        print('Snuke')  
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(200000)
lf,ls=[None]*N,[None]*N
lf[0]=0
ls[-1]=0
def hu(n,c,l):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            hu(i,c+1,l)
hu(0,1,lf)
hu(-1,1,ls)
af=0
for i in range(N):
    if lf[i]<=ls[i]:
        af+=1
if af*2>N:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque

def bfs(i, c):
    q = deque()
    q.append(i)
    while q:
        p = q.popleft()
        for j in g[p]:
            if c[j] == 0 and i != j:
                q.append(j)
                c[j] = c[p] + 1
    return c

n = int(input())
g = [-1] * n
c1 = [0] * n
c2 = [0] * n
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if g[a] == -1:
        g[a] = [b]
    else:
        g[a].append(b)
    if g[b] == -1:
        g[b] = [a]
    else:
        g[b].append(a)

c1 = bfs(0, c1)
c2 = bfs(n - 1, c2)

F, S = 0, 0
for i in range(n):
    if c1[i] <= c2[i]:
        F += 1
    else:
        S += 1
print("Fennec" if F > S else "Snuke")

Submission status: Accepted

Solution code:

import heapq

N = int(input())

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

INF = float("inf")


# ダイクストラでフェネック君の開始地点からの距離を探索
dist_f = [INF] * N
dist_f[0] = 0
q = [(0,0)]
while q:
    cost, curr = heapq.heappop(q)
    if dist_f[curr] < cost:
        continue
    for nxt in es[curr]:
        if dist_f[nxt] < dist_f[curr] + 1:
            continue
        dist_f[nxt] = dist_f[curr] + 1
        heapq.heappush(q, (dist_f[nxt], nxt))

# ダイクストラですぬけ君の開始地点からの距離を探索
dist_s = [INF] * N
dist_s[N-1] = 0
q = [(0,N-1)]
while q:
    cost, curr = heapq.heappop(q)
    if dist_s[curr] < cost:
        continue
    for nxt in es[curr]:
        if dist_s[nxt] < dist_s[curr] + 1:
            continue
        dist_s[nxt] = dist_s[curr] + 1
        heapq.heappush(q, (dist_s[nxt], nxt))

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5)

n = int(input())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]
connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

d1 = [0] * n
dn = [0] * n

def dfs(v, ng, dis, d):
    d[v] = dis
    ng.add(v)
    for n in connect[v]:
        if n not in ng:
            dfs(n, ng, dis+1, d)

dfs(0, set(), 0, d1)
dfs(n-1, set(), 0, dn)

black = 0
white = 0
for i in range(n):
    if d1[i] <= dn[i]:
        black += 1
    else:
        white += 1
if black > white:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


def bfs(G: "List[List[int]]", a: int):
    q = deque()  # type: Deque[int]
    q.append(a)
    dist = [-1] * len(G)
    dist[a] = 0
    while q:
        s = q.popleft()
        for t in G[s]:
            if dist[t] >= 0:
                continue
            q.append(t)
            dist[t] = dist[s] + 1
    return dist


def solve(N: int, a: "List[int]", b: "List[int]"):
    G = [[] for i in range(N)]
    for ai, bi in zip(a, b):
        ai -= 1
        bi -= 1
        G[ai].append(bi)
        G[bi].append(ai)
    db = bfs(G, 0)
    dw = bfs(G, N - 1)
    bn = sum((dbi <= dwi) for dbi, dwi in zip(db, dw))
    wn = N - bn
    if bn > wn:
        print("Fennec")
    else:
        print("Snuke")


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    stack.append(adj)

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

Tf = Tree(N, E)
Tf.setroot(0)

Ts = Tree(N, E)
Ts.setroot(N - 1)

fennec = 0
snuke = 0

for i in range(N):
    if Tf.depth[i] <= Ts.depth[i]:
        fennec += 1
    else:
        snuke += 1

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

Submission status: Accepted

Solution code:
from collections import deque
N, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a,b in zip(*[iter(L)]*2):
  dic[a] += [b]
  dic[b] += [a]
fdist = [-1]*(N+1)
sdist = [-1]*(N+1)
fdist[1] = 0
sdist[N] = 0
q = deque([1])
while q:
  v = q.popleft()
  for u in dic[v]:
    if fdist[u] == -1:
      fdist[u] = fdist[v] + 1
      q.append(u)
q = deque([N])
while q:
  v = q.popleft()
  for u in dic[v]:
    if sdist[u]==-1:
      sdist[u] = sdist[v] + 1
      q.append(u)
ans = sum(a<=b for a,b in zip(fdist,sdist))-1
if 2*ans>N:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for _ in range(N)]
que_f = [0]
que_s = [N-1]
dis_f = [-1]*N
dis_s = [-1]*N
for i in range(N-1):
  a, b = map(int,input().split())
  a -= 1
  b -= 1
  G[a].append(b)
  G[b].append(a)

visited_f = [False]*N
dis_f[0] = 0
while que_f:
  pos = que_f.pop(0)
  for next_pos in G[pos]:
    if visited_f[next_pos] == True:
      continue
    que_f.append(next_pos)
    visited_f[pos] = True
    dis_f[next_pos] = dis_f[pos] + 1

visited_s = [False]*N
dis_s[N-1] = 0
while que_s:
  pos = que_s.pop(0)
  for next_pos in G[pos]:
    if visited_s[next_pos] == True:
      continue
    que_s.append(next_pos)
    visited_s[pos] = True
    dis_s[next_pos] = dis_s[pos] + 1
    
f = 0
s = 0
for i in range(N):
  if dis_f[i] <= dis_s[i]:
    f += 1
  else:
    s += 1

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**6)

def killme(num,lis):
    visited[num]=1
    if num==N-1:
        lis.append(num)
        for index,item in enumerate(lis):
            highway[item]=index
    else:
        for next_n in way[num]:
            if visited[next_n]==0:
                lis.append(num)
                killme(next_n,lis)
                lis.pop(-1)
    return 

def dfs(num,root):
    visited[num]=1
    cluster[root].append(num)
    for next_n in way[num]:
        if visited[next_n]==0 and highway[next_n]==-1:
            #print(next_n,root)
            dfs(next_n,root)
    return 

N=int(input())

way=[[] for i in range(N)]
visited=[0]*N
highway=[-1]*N

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

killme(0,[])

#print(way)
#print(visited)
#print(highway)

visited=[0]*N
cluster=[[] for i in range(highway[-1]+1)]

for index,item in enumerate(highway):
    if item!=-1:
        dfs(index,item)

F=0
S=0
for i in range(highway[-1]+1):
    if i<=highway[-1]//2:
        F+=len(cluster[i])
    else:
        S+=len(cluster[i])

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

Submission status: Accepted

Solution code:
# coding: utf-8
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)

INF=10**9

d=[INF for i in range(N)]
edges=[0 for i in range(N)]
d[0]=0
queue=[]
queue.append(0)

while queue:
    u=queue.pop(0)
    for i in range(len(G[u])):
        if d[G[u][i]]==INF:
            queue.append(G[u][i])
            d[G[u][i]]=d[u]+1

k=d[N-1]
m=N-1
queue.append(N-1)

while k>d[N-1]//2+1:
    u=queue.pop(0)
    for i in range(len(G[u])):
        if d[G[u][i]]==d[u]-1:
            queue.append(G[u][i])
            k=d[u]
            m=u

queue=[]
queue.append(m)
unused=[True for i in range(N)]
unused[m]=False

sunuke=1

while queue:
    u=queue.pop(0)
    sunuke+=len(G[u])-1
    for i in range(len(G[u])):
        if d[G[u][i]]>d[u] and unused[G[u][i]]:
            queue.append(G[u][i])
            unused[G[u][i]]=False

if sunuke>=-(-N//2):
    print("Snuke")
else:
    print("Fennec")