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())
E=[[] for i in range(N)]

for i in range(N-1):
    x,y=map(int,input().split())
    x-=1
    y-=1
    E[x].append(y)
    E[y].append(x)


from collections import deque
BACK=[-1]*N

Q=deque([0])

while Q:
    x=Q.pop()

    for to in E[x]:
        if BACK[to]==-1:
            BACK[to]=x
            Q.append(to)

ROAD=[N-1]

while ROAD[-1]!=0:
    ROAD.append(BACK[ROAD[-1]])

LEN=len(ROAD)

COLOR=[-1]*N
QW=deque()
QB=deque()

for i in range(LEN//2):
    COLOR[ROAD[i]]=1
    QB.append(ROAD[i])

for i in range(LEN//2,LEN):
    COLOR[ROAD[i]]=0
    QW.append(ROAD[i])

SW=0
if LEN%2==1:
    SW+=1
SB=0

while QW:
    x=QW.pop()

    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=0
            SW+=1
            QW.append(to)

while QB:
    x=QB.pop()

    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=1
            SB+=1
            QB.append(to)

if SW>SB:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000000)
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)
que = deque([0])
parent = [-1]*N
parent[0] = 0
while que:
    cur = que.pop()
    for nxt in edges[cur]:
        if parent[nxt] < 0:
            parent[nxt] = cur
            que.append(nxt)
cur = N-1
route = [N-1]
while cur:
    cur = parent[cur]
    route.append(cur)
i = len(route)//2
a, b = route[i-1:i+1]
edges[a].remove(b)
edges[b].remove(a)
que = deque([0])
flag = [True]*N
score = 0
flag[0] = False
while que:
    v0 = que.pop()
    score+=1
    for v in edges[v0]:
        if flag[v]:
            que.append(v)
            flag[v] = False
if score>N//2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
def F(m):
	q=deque([m])
	d=[-1]*n
	while q:
		cur=q.popleft()
		for nxt in G[cur]:
			if d[nxt]<0:
				q.append(nxt)
				d[nxt]=d[cur]+1
	return d
def solve():
	global n,G
	n,*L=map(int,open(0).read().split())
	G=[[]for _ in range(n)]
	for a,b in zip(*[iter(L)]*2):
		G[a-1]+=[b-1]
		G[b-1]+=[a-1]
	print("FSennunkeec"[sum(i>j or-1 for i,j in zip(F(0),F(n-1)))>=0::2])
if __name__=="__main__":solve()

Submission status: Accepted

Solution code:
from collections import*
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
def F(m):
	q=deque([m])
	d=[-1]*n
	while q:
		cur=q.popleft()
		for nxt in G[cur]:
			if d[nxt]<0:
				q.append(nxt)
				d[nxt]=d[cur]+1
	return d
print("FSennunkeec"[sum(i>j or-1 for i,j in zip(F(0),F(n-1)))>=0::2])

Submission status: Accepted

Solution code:
from collections import deque
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n;db[0]=0
dw=[-1]*n;dw[-1]=0
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=deque([0])
while q:
	cur=q.popleft()
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append(nxt)
			db[nxt]=db[cur]+1
q=deque([n-1])
while q:
	cur=q.popleft()
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append(nxt)
			dw[nxt]=dw[cur]+1
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:print("Snuke")
else:print("Fennec")

Submission status: Accepted

Solution code:
from collections import deque
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n
dw=[-1]*n
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=deque([(0,0)])
while q:
	cur,d=q.popleft()
	db[cur]=d
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append((nxt,d+1))
q=deque([(n-1,0)])
while q:
	cur,d=q.popleft()
	dw[cur]=d
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append((nxt,d+1))
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:
	print("Snuke")
else:
	print("Fennec")

Submission status: Accepted

Solution code:
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n;db[0]=0
dw=[-1]*n;dw[-1]=0
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=[0]
while q:
	cur=q.pop(0)
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append(nxt)
			db[nxt]=db[cur]+1
q=[n-1]
while q:
	cur=q.pop(0)
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append(nxt)
			dw[nxt]=dw[cur]+1
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:print("Snuke")
else:print("Fennec")

Submission status: Accepted

Solution code:
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n
dw=[-1]*n
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=[(0,0)]
while q:
	cur,d=q.pop(0)
	db[cur]=d
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append((nxt,d+1))
q=[(n-1,0)]
while q:
	cur,d=q.pop(0)
	dw[cur]=d
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append((nxt,d+1))
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:
	print("Snuke")
else:
	print("Fennec")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

alis = [""] * N
alis[0] = 0

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

while len(Q) > 0:

    now = Q.pop()

    if now not in dic:
        continue

    for b in dic[now]:

        if alis[b] == "":
            alis[b] = alis[now] + 1

            Q.append(b)

blis = [""] * N
blis[N-1] = 0

Q = deque([])
Q.append(N-1)

while len(Q) > 0:

    now = Q.pop()

    if now not in dic:
        continue

    for b in dic[now]:

        if blis[b] == "":
            blis[b] = blis[now] + 1

            Q.append(b)

F = 0
S = 0

for i in range(N):
    if alis[i] <= blis[i]:
        F += 1
    else:
        S += 1

if F <= S:
    print ("Snuke")
else:
    print ("Fennec")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)

def set_distance(t, l, now, prev, pos):
    d = l[now][pos]

    for child in t[now]:
        if child == prev:
            continue
        l[child][pos] = d+1
        set_distance(t, l, child, now, pos)


n = int(input())
t = defaultdict(list)
for _ in range(n-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    t[a].append(b)
    t[b].append(a)

# distance [fennec, snuke]
l = [[n, n] for _ in range(n)]
l[0][0] = 0
l[n-1][1] = 0

set_distance(t, l, 0, -1, 0)
set_distance(t, l, n-1, -1, 1)

f, s = 0, 0
for df, ds in l:
    if df <= ds:
        f += 1
    else:
        s += 1

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

Submission status: Accepted

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(N+10)

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

"""
相手の取れるマス目を減らすようにとるとよい
相手よりそのマスに近ければそのマスを取得できる
フェネックくん、すぬけ君について初期地点からそれぞれへの距離が必要
"""
def solve(now, depth, depth_list, es, visited):
    visited[now] = True
    depth_list[now] = depth
    for next in es[now]:
        if visited[next] == False:            
            solve(next, depth+1, depth_list, es, visited)

depth_list_F = [0] * N
visited_F = [False] * N
solve(0, 0, depth_list_F, es, visited_F)

depth_list_S = [0] * N
visited_S = [False] * N
solve(N-1, 0, depth_list_S, es, visited_S)

cnt_F = cnt_S = 0
for f,s in zip(depth_list_F, depth_list_S):
    if f <= s:
        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(100000)

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)
prevs=[0]*N
def dfs(prev,curr):
    prevs[curr]=prev
    if curr == N-1:
        return
    for c in edges[curr]:
        if c!=prev:
            dfs(curr,c)
dfs(-1,0)
paths=[N-1]
tmp=N-1
while tmp!=0:
    paths.append(prevs[tmp])
    tmp=prevs[tmp]
paths=paths[::-1]

points=[0,0]
def count(prev,curr,player):
    points[player]+=1
    for c in edges[curr]:
        if c!=prev:
            count(curr,c,player)

nf = (len(paths)+1)//2
f,s = paths[nf-1],paths[nf]
count(s,f,0)
count(f,s,1)
pf,ps=points
print("Fennec" if pf>ps else "Snuke")

Submission status: Accepted

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

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

V = [-1 for _ in range(N)]
def dfs(u,count):
  V[u] = count
  for v in E[u]:
    if V[v] == -1:
      dfs(v,count+1)
dfs(0,0)
Path = []
v = N-1
while (v != 0):
  Path.append(v)
  for u in E[v]:
    if V[u] == V[v] -1:
      v = u
Path.append(0)
#print(Path)

def dfs2(u):
  visited[u] = True
  res = 1
  for v in E[u]:
    if not visited[v]:
      res += dfs2(v)
  return res
visited = [False for _ in range(N)]
for i in Path:
  visited[i] = True
fennec = 0
for i in range((len(Path)+1)//2):
  fennec += dfs2(Path[-i-1])
snuke = 0
for i in range(len(Path)//2):
  snuke += dfs2(Path[i])
#print(fennec,snuke)
print('Fennec' if fennec > snuke else 'Snuke')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

G = {k: [] for k in range(N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].append(b)
    G[b].append(a)


def dfs(v, p, c, distance):  # 現在の頂点v, vの親p, 現在の距離c
    distance[v] = c
    for nv in G[v]:
        if visited[nv] is False:
            if nv == p:
                continue
            dfs(nv, v, c+1, distance)
    return


distance_f = [-1]*(N+1)
visited = [False] * (N+1)
dfs(1, -1, 0, distance_f)

distance_s = [-1]*(N+1)
visited = [False] * (N+1)
dfs(N, -1, 0, distance_s)

# print(distance_f)
# print(distance_s)

c = 0
for i in range(2, N):
    if distance_f[i] <= distance_s[i]:
        c += 1
    elif distance_f[i] > distance_s[i]:
        c -= 1

if c > 0:
    print('Fennec')
elif c <= 0:
    print('Snuke')

Submission status: Accepted

Solution code:
N = int(input())
E = [set() for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  E[a].add(b)
  E[b].add(a)
DF = [-1]*N
q = [0]
DF[0] = 0
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if DF[n] < 0:
      DF[n] = DF[c]+1
      q.append(n)
#print(DF)
DS = [-1]*N
q = [N-1]
DS[N-1] = 0
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if DS[n] < 0:
      DS[n] = DS[c]+1
      q.append(n)
NF = 0
NS = 0
for i in range(N):
  if DF[i] <= DS[i]:
    NF += 1
  else:
    NS += 1
#print(NF, NS)
if NF > NS:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
import collections
def main():

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

    cur1 = [1]
    cur2 = [N]
    visited1 = {1}
    visited2 = {N}

    while cur1 or cur2:
        temp1, temp2 = [], []
        for a in cur1:
            for b in graph[a]:
                if b not in visited1 and b not in visited2:
                    temp1.append(b)
                    visited1.add(b)
        cur1 = temp1

        for a in cur2:
            for b in graph[a]:
                if b not in visited1 and b not in visited2:
                    temp2.append(b)
                    visited2.add(b)
        cur2 = temp2

    if len(visited1) > len(visited2):
        return "Fennec"
    return "Snuke"


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
visited = [0]*n
visited[0] = 1
visited[n-1] = 1
visited_all = [1]*n
nextF = edge[0]
nextS = edge[n-1]
black = 1
white = 1
while visited != visited_all:
    l = []
    for f in nextF:
        if visited[f] == 0:
            visited[f] = 1
            black += 1
            for x in edge[f]:
                l.append(x)
            nextF = l
    l = []
    for s in nextS:
        if visited[s] == 0:
            visited[s] = 1
            white += 1
            for y in edge[s]:
                l.append(y)
            nextS = l
if black > white:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import*
N,*AB=map(int,open(0).read().split())
E=[[]for _ in range(N+1)]
for a,b in zip(*[iter(AB)]*2):
	E[a]+=[b]
	E[b]+=[a]
def g(s):
	Q=deque([s]);d=[0]*(N+1)
	while Q:
		v=Q.popleft()
		for u in E[v]:
			if d[u]==0:
				Q+=[u]
				d[u]=d[v]+1
	return d[1:]
print("SFneunknee c"[0<sum(1 if f<=s else-1 for f,s in zip(g(1),g(N)))::2])

Submission status: Accepted

Solution code:
from collections import deque
N,*AB=map(int,open(0).read().split())
E=[[]for _ in range(N+1)]
for a,b in zip(*[iter(AB)]*2):
	E[a].append(b)
	E[b].append(a)
def g(s):
	Q=deque([s])
	d=[0]*(N+1)
	while Q:
		v=Q.popleft()
		for u in E[v]:
			if d[u]==0:
				Q.append(u)
				d[u]=d[v]+1
	return d[1:]
print("Fennec"if 0<sum(1 if f<=s else-1 for f,s in zip(g(1),g(N))) else"Snuke")

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

def get_dist(src):
    Q = deque([src])
    dist = [0] * (N + 1)
    while Q:
        v =  Q.popleft()
        for u in E[v]:
            if dist[u] == 0:
                Q.append(u)
                dist[u] = dist[v] + 1
    return dist[1:]

F = get_dist(1)
S = get_dist(N)

fennec = sum(1 if f <= s else -1 for f, s in zip(F, S))

if fennec > 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)


def get_dist(src):
    Q = deque([src])
    dist = [0] * (N + 1)
    while Q:
        v =  Q.popleft()
        for u in E[v]:
            if dist[u] == 0:
                Q.append(u)
                dist[u] = dist[v] + 1
    return dist[1:]

F = get_dist(1)
S = get_dist(N)

fennec, snuke = 0, 0
for f, s in zip(F, S):
    if f <= s:
        fennec += 1
    else:
        snuke += 1

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

Submission status: Accepted

Solution code:
from collections import deque


N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)


def get_dist(src):
    Q = deque([(src, 0)])
    dist = [-1] * (N + 1)
    while Q:
        v, d = Q.popleft()
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                Q.append((u, d + 1))
    return dist[1:]

F = get_dist(1)
S = get_dist(N)
fennec, snuke = 0, 0
for f, s in zip(F, S):
    if f <= s:
        fennec += 1
    else:
        snuke += 1

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

Submission status: Accepted

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

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

d1 = [-1] * n
d2 = [-1] * n
def dfs(v, d):
    for v_next in edge[v]:
        if d[v_next] == -1:
            d[v_next] = d[v] + 1
            dfs(v_next, d)

d1[0] = 0
dfs(0, d1)
d2[-1] = 0
dfs(n-1, d2)

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

if n_f > n // 2:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Submission status: Accepted

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

import math

N=int(input())

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

depth=[[0]*N for i in range(2)]

def dfs(d, i, p, k=0):
	for t in G[i]:
		if t!=p:
			depth[k][t]=d
			dfs(d+1, t, i,k)


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

cnt=0
for i,j in zip(depth[0], depth[1]):
	if i<=j:
		cnt+=1

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

Submission status: Accepted

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

distance1=[-1 for i in range(n)]
distance1[0]=0
next=connection[0]
next2=[]
check=[-1 for i in range(n)]
check[0]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

distanceN=[-1 for i in range(n)]
distanceN[n-1]=0
next=connection[n-1]
next2=[]
check=[-1 for i in range(n)]
check[n-1]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distanceN[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

ctF=0;ctS=0
for i in range(n):
  if distance1[i]<=distanceN[i]:
    ctF+=1
  else:
    ctS+=1
if ctF>ctS:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
# ARC078D - Fennec VS. Snuke (ABC067D)
from collections import deque


def bfs(s: int, d: "List[int]") -> None:
    q = deque([s])
    while q:
        v = q.popleft()
        for u in G[v]:
            if not d[u]:
                q.append(u)
                d[u] = d[v] + 1


def main():
    global G, DB, DW
    N, *E = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 2, 2):
        v, u = E[i : i + 2]
        G[v] += [u]
        G[u] += [v]
    # DB, DW: distance from G[i] (black) and G[N] (white)
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    bfs(1, DB), bfs(N, DW)
    b, w = 0, 0
    for i, j in zip(DB[1:], DW[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC067D - Fennec VS. Snuke (ARC078D)
from collections import deque


def bfs(s: int, d: "List[int]") -> None:
    q = deque([s])
    while q:
        v = q.popleft()
        for u in G[v]:
            if not d[u]:
                q.append(u)
                d[u] = d[v] + 1


def main():
    global G, DB, DW
    N, *E = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 2, 2):
        v, u = E[i : i + 2]
        G[v] += [u]
        G[u] += [v]
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    bfs(1, DB), bfs(N, DW)
    b, w = 0, 0
    for i, j in zip(DB[1:], DW[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC067D - Fennec VS. Snuke (ARC078D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, x: int, d: "List[int]") -> None:
    d[v] = x
    for u in G[v]:
        if not d[u]:
            dfs(u, x + 1, d)


def main():
    global G, DB, DW
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    dfs(1, 1, DB), dfs(N, 1, DW)
    b, w = 0, 0
    for i, j in zip(DB[1:], DW[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC067D - Fennec VS. Snuke (ARC078D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

from collections import deque


def bfs(s, d) -> None:
    q = deque([s])
    while q:
        v = q.popleft()
        for u in G[v]:
            if not d[u]:
                q.append(u)
                d[u] = d[v] + 1


def main():
    global G, DB, DW
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    bfs(1, DB), bfs(N, DW)
    b, w = 0, 0
    for i, j in zip(DB[1:], DW[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(600000)

N = int(input())

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

def dfs(p, checked, now):
    #print(p, checked, now)
    if p == N-1:
        return now, True
    ok = False
    for q in graph[p]:
        if not checked[q]:
            now.append(q)
            checked[q] = True
            nbw, ok1 = dfs(q, checked, now)
            if ok1:
                bw = nbw
                ok = True
    if not ok:
        now.pop()
        return now, False
    return bw, True

checked = [False for _ in range(N)]
checked[0] = True
bw, ok = dfs(0, checked, [0])
#print(bw)

between = [0 for _ in range(N)]
k = len(bw)
if k % 2 == 0:
    s0 = bw[k//2-1]
    sN = bw[k//2]
else:
    s0 = bw[k//2]
    sN = bw[k//2+1]
between[s0] = True
between[sN] = True

def dfs2(p, checked, c):
    c += 1
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            c = dfs2(q, checked, c)
    return c

c0 = dfs2(s0, between, 0)
cN = dfs2(sN, between, 0)
#print(c0, cN)



if cN < c0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
ki=[[] for i in range(n+1)]
for i in range(n-1):
    ki[ab[i][0]].append(ab[i][1])
    ki[ab[i][1]].append(ab[i][0])
# print(ki)
kyori=[[float("INF"), float("INF")] for i in range(n+1)]
def tansaku(m, dis, hito):
    q=[[m,dis]]
    while q:
        po=q.pop()
        for i in ki[po[0]]:
            if kyori[i][hito]>po[1]:
                kyori[i][hito]=po[1]
                q.append([i,po[1]+1])

tansaku(1,1,0)
tansaku(n,1,1)
fe,su=0,0

for i in range(1,n+1):
    if kyori[i][0]<=kyori[i][1]:
        fe+=1
    else:
        su+=1

if fe>su:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

nbr=[[] for _ in range(n)]
for i in range(n-1):
    nbr[l[i][0]-1].append(l[i][1]-1)
    nbr[l[i][1]-1].append(l[i][0]-1)
def sm(i,p):
    s=0
    for x in nbr[i]:
        if x!=p:s+=sm(x,i)
    return s+1
flg=False
f=0
c=[]
def dfs(i,p):
    global flg
    global c
    if i==n-1:flg=True
    if not flg:
        for x in nbr[i]:
            if x!=p:dfs(x,i)
            if flg:break
    if flg:
        c.append(i)
dfs(0,-1)
idx=(len(c)+1)//2
print('Fennec' if sm(c[::-1][idx],c[::-1][idx-1])*2<n else 'Snuke')

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    l[x].append(y)
    l[y].append(x)
from collections import deque
q=deque([0])
lf=[10**100 for i in range(n)]
lf[0]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if lf[p]+1<lf[i]:
            lf[i]=lf[p]+1
            q.append(i)
q=deque([n-1])
ls=[10**100 for i in range(n)]
ls[n-1]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if ls[p]+1<ls[i]:
            ls[i]=ls[p]+1
            q.append(i)
s,f=0,0
for i in range(n):
    if lf[i]<=ls[i]:
        f+=1
    else:
        s+=1
if f<=s:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    l[x].append(y)
    l[y].append(x)
from collections import deque
q=deque([0])
lf=[10**100 for i in range(n)]
lf[0]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if lf[p]+1<lf[i]:
            lf[i]=lf[p]+1
            q.append(i)
q=deque([n-1])
ls=[10**100 for i in range(n)]
ls[n-1]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if ls[p]+1<ls[i]:
            ls[i]=ls[p]+1
            q.append(i)
s,f=0,0
for i in range(n):
    if lf[i]<=ls[i]:
        f+=1
    else:
        s+=1
if f<=s:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if not (a % 3 and b % 3 and (a + b) % 3):
        print("Possible")
    else:
        print("Impossible")
    return

#B
def B():
    _, n = LI()
    l = LI()
    l.sort(reverse = True)
    print(sum(l[:n]))
    return

#C
def C():
    n = II()
    a = LI()
    for i in range(n-1):
        a[i + 1] += a[i]
    maxa = a[-1]
    ans = inf
    for i in range(n-1):
        ans = min(ans, abs(2 * a[i] - maxa))
    print(ans)
    return

#D
def D():
    n = II()
    edg = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    rank = [0] * n
    q = deque()
    q.append(0)
    rank[0] = 1
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i]:
                continue
            rank[i] = rank[p] + 1
            q.appendleft(i)
    k = 2
    q = deque()
    q.append(n - 1)
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i] < rank[p]:
                if rank[i] <= k:
                    a = p
                    break
                q.appendleft(i)
                k += 1
    ans1 = 1
    ans2 = 1
    check = [True] * n
    q = deque()
    q.append(a)
    check[a] = False
    while q:
        p = q.pop()
        for i in edg[p]:
            if rank[i] > rank[p]:
                q.append(i)
                ans1 += 1
                check[i] = False
    q = deque()
    q.append(0)
    check[0] = False
    while q:
        p = q.pop()
        for i in edg[p]:
            if check[i]:
                q.append(i)
                ans2 += 1
                check[i] = False
    print(["Fennec", "Snuke"][ans1 >= ans2])
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
to = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    to[a - 1].append(b - 1)
    to[b - 1].append(a - 1)
dist = None
pars = [0] * N
q = deque()
q.append((0, 0, 0))
while len(q):
    a, d, p = q.pop()
    pars[a] = p
    if a == N - 1:
        dist = d
        break
    for b in to[a]:
        if b != p:
            q.append((b, d + 1, a))

boundw = N - 1
for _ in range((dist - 1) // 2):
    boundw = pars[boundw]

q = deque()
q.append((0, 1, 0))
ans = 0
while len(q):
    a, sgn, p = q.pop()
    if a == boundw:
        sgn = -1
    ans += sgn
    for b in to[a]:
        if b != p:
            q.append((b, sgn, a))
print("Fennec" if ans > 0 else "Snuke")

Submission status: Accepted

Solution code:

from collections import deque

# BFSで、B/Wそれぞれのスタート地点から拡張点への距離を取得
def bfs(s, distance):
    visited = [False] * N
    q = [(s, 1)]
    visited[s] = True

    while q:
        u, dist = q.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                distance[v] = dist
                q.append((v, dist+1))

#    print(distance)


N = int(input())
graph = [deque() for i in range(N)]
distance = [[0] * N for i in range(2)]

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

#print(graph)

bfs(0, distance[0])
bfs(N-1, distance[1])

# 各頂点について、より近いほうが塗れたことに
b = w = 0
for i in range(1, N-1):
    if distance[0][i] <= distance[1][i]:
        b += 1
    else:
        w += 1
if b <= w:
    print('Snuke')
else:
    print('Fennec')