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 sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
d1 = [float("inf")] * (N + 1)
d1[1] = 0
Q = dq([])
Q.append(1)
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if d1[q] > d1[p] + 1:
      d1[q] = d1[p] + 1
      Q.append(q)
dn = [float("inf")] * (N + 1)
dn[N] = 0
Q.append(N)
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if dn[q] > dn[p] + 1:
      dn[q] = dn[p] + 1
      Q.append(q)
#print(d1, dn)
f = 0
for i in range(1, N + 1):
  if d1[i] <= dn[i]:
    f += 1
if f > N // 2: print("Fennec")
else: print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N=int(input())
ab=[[] for _ in range(N)]
for _ in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)
"""
N=10**5
ab=[[]]*N
ab[0]=[2]
ab[N-1]=[N-1]
for i in range(1,N-1):
  ab[i]=[i,i+2]
"""
par=[0]*N
  
def dfs(pre,p):
  global path
  par[p-1]=pre
  if p==N:
    pass
  else:
    for i in ab[p-1]:
      if i!=pre:
        dfs(p,i)

dfs(-1,1)
path=[N]
p=N
while p!=1:
  p=par[p-1]
  path.append(p)
path.reverse()

spath=set(path)

def dfs2(pre,p):
  a=0
  for i in ab[p-1]:
    if i in spath:
      pass
    elif i==pre:
      pass
    else:
      a+=dfs2(p,i)
  return 1+a

ff=0
sf=0
L=len(path)
for i in range(L):
  if i<=(L-1)//2:
    ff+=dfs2(-1,path[i])
  else:
    sf+=dfs2(-1,path[i])
    
if ff>sf:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque

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)
    
q = deque()
q.append(0)
parents = [-1]*N
parents[0] = -2
while q:
    t = q.popleft()
    for i in E[t]:
        if parents[i] == -1:
            parents[i] = t
            q.append(i)
    if parents[N-1] >= 0:
        break

q_snuke = deque()
q_snuke.append(N-1)
idx = N-1
used = [0]*N
used[0] = 1
cnt = 0
while parents[idx] >= 0:
    q_snuke.append(parents[idx])
    idx = parents[idx]
    used[idx] = 1

n = len(q_snuke)
for _ in range(n//2+(n%2)):
    q_snuke.pop()
    

while q_snuke:
    t = q_snuke.popleft()
    for i in E[t]:
        if used[i] == 0:
            used[i] = 1
            q_snuke.append(i)

s = sum(used) - (n//2+(n%2))
if s >= N-s or N == 2:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                #ループが嫌な時
                return -1
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return len

def examD():
    N = I()
    v = [[] for i in range(N)]
    for i in range(N-1):
        a, b = LI()
        v[a-1].append(b-1)
        v[b-1].append(a-1)
    fennec = bfs(N,0,v)
    snuke = bfs(N,N-1,v)
    cur = 0
    for i in range(N):
        if fennec[i]>snuke[i]:
            cur +=1
    if cur>=(N+1)//2:
        ans = "Snuke"
    else:
        ans = "Fennec"
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
node_data = [[] for i in range(n+1)]
node_stuck = deque([])
Fennec = [0] * (n+1)
Snuke = [0] * (n+1)
for i in range(n-1):
    x, y = list(map(int, input().split()))
    node_data[x].append(y)
    node_data[y].append(x)
node_stuck.append([1,0])
finished = set()

while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Fennec[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count+1])
node_stuck.append([n,0])
finished = set()
while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Snuke[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count + 1]) 
f = 0
s = 0
##print("Fennec => {}".format(Fennec))
##print("Snuke  => {}".format(Snuke))
for i in range(2, n):
    if Fennec[i] <= Snuke[i]:
        f += 1
    else:
        s += 1

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

Submission status: Accepted

Solution code:
from collections import deque

def dfs(si, ei):
  q = deque()
  q.append([si,0])
  done = set([si])
  ds = [0 for _ in range(N)]
  while len(q) > 0:
    prvi, d = q.pop()
    for i in g[prvi]:
      if i in done: continue
      ds[i] = d+1
      q.append([i,d+1])
      done.add(i)
  return ds

N = int(input())
g = {i:[] for i 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)

dslist = dfs(0,N-1)
delist = dfs(N-1,0)

cntb, cntw = 0, 0
for ds, de in zip(dslist[1:N-1], delist[1:N-1]):
  if ds <= de: cntb += 1
  else: cntw += 1
print('Fennec' if cntb>cntw else 'Snuke')

Submission status: Accepted

Solution code:
import itertools
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
N = int(input())
E = {i:[] for i in range(N+1)}
for i in range(N-1):
    a,b= inputs()
    E[a].append(b)
    E[b].append(a)
stkf = [[1,-1,0]]
visitedf=[0]*(N+1)
visiteds=[0]*(N+1)
stks = [[N,-1,0]]
cntf=0
cnts=0
while stkf:
    v,p,cost=stkf.pop()
    if v==N:
        visitedf[N]=cost
        continue
    visitedf[v]=cost
    cntf+=1
    for i in E[v]:
        if i!=p:
            stkf.append([i,v,cost+1])
while stks:
    v,p,cost=stks.pop()
    if v==1:
        visiteds[1]=cost
        continue
    visiteds[v]=cost
    cnts+=1
    for i in E[v]:
        if i!=p:
            stks.append([i,v,cost+1])
for i in range(1,N+1):
  if visitedf[i] and visiteds[i]:
    if visitedf[i]<=visiteds[i]:
      cnts-=1
    else:
      cntf-=1
#print(cntf-1,cnts-1,visitedf[N]-1,visiteds[1]-1)
"""
if (visitedf[N]-1)%2!=0:
  cntf=cntf-1-(visitedf[N]-1)//2
  cnts=cnts-1-(visitedf[N]-1)//2-1
else:
  cntf=cntf-1-(visitedf[N]-1)//2
  cnts=cnts-1-(visitedf[N]-1)//2
"""
print("Fennec" if cntf>cnts else "Snuke")
#print(visitedf,cntf,cnts)

Submission status: Accepted

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
data=[[] for i in range(n+1)]
for u in ab:
    a,b=u
    data[a].append(b)
    data[b].append(a)
flag=[0]*(n+1)
s=[1]
g=[n]
flag[1]="B"
flag[n]="W"
while s or g:
    H=[]
    for u in s:
        for v in data[u]:
            if flag[v]==0:
                flag[v]="B"
                H.append(v)
    s=H
    H=[]
    for u in g:
        for v in data[u]:
            if flag[v]==0:
                flag[v]="W"
                H.append(v)
    g=H
Bcount=0
Wcount=0
for i in range(1,n+1):
    if flag[i]=="B":
        Bcount+=1
    elif flag[i]=="W":
        Wcount+=1
if Bcount>Wcount:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

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

V = [0] * (n+1)
P = [-1] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

Q = [1]
s = 0
V[1] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        if V[x] == 0:
            V[x] = 1
            P[x] = i
            Q.append(x)
    s += 1
    # print(Q)

# print(P)

aida = [n]
a = n
while a != 1:
    a = P[a]
    aida.append(a)



V = [0] * (n+1)
for i in aida:
    V[i] = 1

aida = aida[::-1]
# print(aida)

fe = 0
su = 0
for j in range(len(aida)):
    ans = 1
    Q = [aida[j]]
    s = 0
    while s < len(Q):
        i = Q[s]
        for x in M[i]:
            if V[x] == 0:
                V[x] = 1
                P[x] = i
                Q.append(x)
                ans += 1
        s += 1
    if j < (len(aida)+1)//2:
        fe += ans
    else:
        su += ans
    # print(aida[j],ans)

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

Submission status: Accepted

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

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

def dfs(s,d):
    global flag
    global la
    flag[s] = d + 1
    for g in la[s]:
        if flag[g] == -1:
            dfs(g,flag[s])

def main():
    global n
    global flag
    dfs(0,-1)
    distf = flag[:]
    flag = [-1 for _ in range(n)]
    dfs(n-1,-1)
    dists = flag[:]
    res = 0
    for i in range(n):
        if distf[i] <= dists[i]:
            res += 1
        else:
            res -= 1
    if res > 0:
        return "Fennec"
    else:
        return "Snuke"



print(main())

Submission status: Accepted

Solution code:
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    heappush(Q,(0,point))
    
    while Q:
        c,p=heappop(Q)
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                heappush(Q,(c+1,np))
    return cost

n=int(input())
d=[[]for i in range(n+1)]

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

x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

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

Submission status: Accepted

Solution code:
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=deque()
    Q.appendleft((0,point))
    
    while Q:
        c,p=Q.pop()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                Q.appendleft((c+1,np))
    return cost

n=int(input())
d=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

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

Submission status: Accepted

Solution code:
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    Q.append((0,point))
    
    while Q:
        c,p=Q.pop()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                Q.append((c+1,np))
    return cost

n=int(input())
d=[deque()for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

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

Submission status: Accepted

Solution code:
#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    heappush(Q,(0,point))
    
    while Q:
        c,p=heappop(Q)
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                heappush(Q,(c+1,np))
    return cost

n=int(input())
d=[deque()for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

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

Submission status: Accepted

Solution code:
#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=[]
    heappush(Q,(0,point))
    
    while Q:
        c,p=heappop(Q)
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                heappush(Q,(c+1,np))
    return cost

n=int(input())
d={}
for i 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]
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

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

Submission status: Accepted

Solution code:
#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=deque([(0,point)])
    
    while Q:
        c,p = Q.popleft()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                Q.append((c+1,np))
    return cost

n=int(input())
# d={}
d=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    
    # if a in d.keys():
    #     d[a].append(b)
    # else:
    #     d[a]=[b]
    # if b in d.keys():
    #     d[b].append(a)
    # else:
    #     d[b]=[a]
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

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

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)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

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

Submission status: Accepted

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

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

que = deque()
que.append(1)
root = [-1] * (N+1)
root[1] = 0
while que:
    v = que.popleft()
    for u in adj[v]:
        if root[u] < 0:
            root[u] = v
            que.append(u)

i = N
path = []
while True:
    path.append(i)
    if i == 1:
        break
    i = root[i]
path.reverse()

first = path[(len(path)-1)//2]
second = path[(len(path)-1)//2 + 1]
cnt = 0
que.append(first)
seen = [0] * (N+1)
seen[first] = 1
seen[second] = 1
while que:
    v = que.pop()
    cnt += 1
    for u in adj[v]:
        if seen[u] == 0:
            seen[u] = 1
            que.append(u)

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = {}
for i in range(N-1):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
hist = [-1 for _ in range(N+1)]
heapF = deque([(1,0)])
hist[1] = 0
heapS = deque([(N,0)])
hist[N] = 1
turn = 0
while heapF or heapS:
    if turn%2==0:
        while heapF:
            cur = heapF.popleft()
            if cur[1]==turn//2:
                for x in G[cur[0]]:
                    if hist[x]<0:
                        heapF.append((x,cur[1]+1))
                        hist[x] = 0
            else:
                heapF.append(cur)
                break
    else:
        while heapS:
            cur = heapS.popleft()
            if cur[1]==turn//2:
                for x in G[cur[0]]:
                    if hist[x]<0:
                        heapS.append((x,cur[1]+1))
                        hist[x] = 1
            else:
                heapS.append(cur)
                break
    turn += 1
n = hist.count(0)
m = hist.count(1)
if m>=n:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
import collections

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)

cur_f = [1]
cur_s = [n]
visit_f = {1}
visit_s = {n}
while cur_f or cur_s:
  temp_f = []
  for start in cur_f:
    for end in graph[start]:
      if end not in visit_f and end not in visit_s:
        temp_f.append(end)
        visit_f.add(end)
  cur_f = temp_f
  temp_s = []
  for start in cur_s:
    for end in graph[start]:
      if end not in visit_f and end not in visit_s:
        temp_s.append(end)
        visit_s.add(end)
  cur_s = temp_s

if len(visit_f) > len(visit_s):
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

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

Graph = [[] for i in range(n)]
for edge in Edge:
    Graph[edge[0]-1].append(edge[1]-1)
    Graph[edge[1]-1].append(edge[0]-1)

Distance_1 = [-1 for i in range(n)]
Distance_1[0] = 0
Distance_n = [-1 for i in range(n)]
Distance_n[n-1] = 0

stack = [0]
while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Distance_1[adj] == -1:
            Distance_1[adj] = Distance_1[node] + 1
            stack.append(adj)

stack = [n-1]
while stack:
    node = stack.pop()
    for adj in Graph[node]:
        if Distance_n[adj] == -1:
            Distance_n[adj] = Distance_n[node] + 1
            stack.append(adj)

count = 0
for i in range(n):
    if Distance_1[i]<=Distance_n[i]:
        count += 1

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

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            distance[connection[next[i]][j]]=ct
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

import sys
input = sys.stdin.readline
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)
 
f=bfs(0);s=bfs(n-1)
ctf=0;cts=0
for i in range(n):
  if f[i]<=s[i]:
    ctf+=1
  else:
    cts+=1
 
if ctf>cts:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

import sys
input = sys.stdin.readline
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)
 
f=bfs(0);s=bfs(n-1)
ctf=0;cts=0
for i in range(n):
  if f[i]<=s[i]:
    ctf+=1
  else:
    cts+=1
 
if ctf>cts:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 or visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

import sys
input = sys.stdin.readline
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)
 
f=bfs(0);s=bfs(n-1)
ctf=0;cts=0
for i in range(n):
  if f[i]<=s[i]:
    ctf+=1
  else:
    cts+=1
 
if ctf>cts:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
    
  return distance

import sys
input = sys.stdin.readline
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)

f=bfs(0);s=bfs(n-1)
ctf=0;cts=0
for i in range(n):
  if f[i]<=s[i]:
    ctf+=1
  else:
    cts+=1

if ctf>cts:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
    
  return distance

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)

f=bfs(0);s=bfs(n-1)
ctf=0;cts=0
for i in range(n):
  if f[i]<=s[i]:
    ctf+=1
  else:
    cts+=1

if ctf>cts:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

da = [0]*N
db = [0]*N

qa = deque([0])
visited = [False]*N
visited[0] = True
while qa :
    u = qa.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            da[v] = da[u] + 1
            qa.append(v)

qb = deque([N-1])
visited = [False]*N
visited[N-1] = True
while qb :
    u = qb.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            db[v] = db[u] + 1
            qb.append(v)

c = sum(da[i] <= db[i] for i in range(N))
ans = "Fennec" if c > N-c else "Snuke"
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

da = [0]*N
db = [0]*N

qa = deque([0])
visited = [False]*N
visited[0] = True
while qa :
    u = qa.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            da[v] = da[u] + 1
            qa.append(v)

qb = deque([N-1])
visited = [False]*N
visited[N-1] = True
while qb :
    u = qb.popleft()
    for v in L[u] :
        if not visited[v] :
            visited[v] = True
            db[v] = db[u] + 1
            qb.append(v)

c = sum([1 if da[i] <= db[i] else 0 for i in range(N)])
ans = "Fennec" if c > N-c else "Snuke"
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    next_points = deque([home_point])

    while len(next_points) > 0:
        p = next_points.popleft()
        for idx in neighbor[p]:
            if shortest_distance_list[idx] == -1:
                shortest_distance_list[idx] = shortest_distance_list[p]+1
                next_points.append(idx)

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
shortest_distance_from_Snuke = shortest_distance(N-1)

for idx in range(1,N-1):
    if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
        black_white[idx] = 0
    else:
        black_white[idx] = 1

print("Fennec" if black_white.count(0) > black_white.count(1) else "Snuke")

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
V = [0]*N
V[0] = 1
V[-1] = -1
q = [0,N-1]
while q:
    qq = []
    for i in q:
        Vi = V[i]
        for j in E[i]:
            if not V[j]:
                V[j] = Vi
                qq.append(j)
    q = qq
print("Fennec" if sum(V)>0 else "Snuke")

Submission status: Accepted

Solution code:
n=int(input());l=[[]for _ in[0]*n];c=[1]+[0]*(n-2)+[-1];q=[0,n-1]
for _ in[0]*q[1]:a,b=map(int,input().split());l[a-1]+=[b-1];l[b-1]+=[a-1]
while q:
  p=[]
  for i in q:
    for j in l[i]:
      if c[j]==0:c[j]=c[i];p+=[j]
  q=p
print("FSennunkeec"[sum(c)<1::2])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    graph[a - 1] += [b - 1]
    graph[b - 1] += [a - 1]




f_que = deque([0])
s_que = deque([n - 1])
visited = [0] * n
visited[0] = 1
visited[n - 1] = 1
f_cnt = s_cnt = 0
while f_que or s_que:
    f_tmp = deque()
    for cur in f_que:
        for nxt in graph[cur]:
            if visited[nxt]:
                continue
            f_tmp += [nxt]
            visited[nxt] = 1
            f_cnt += 1
    f_que = f_tmp
    s_tmp = deque()
    for cur in s_que:
        for nxt in graph[cur]:
            if visited[nxt]:
                continue
            s_tmp += [nxt]
            visited[nxt] = 1
            s_cnt += 1
    s_que = s_tmp


if s_cnt >= f_cnt:
    print('Snuke')
else:
    print('Fennec')

Submission status: Accepted

Solution code:
import collections
import heapq


class Dijkstra:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.neighbors = collections.defaultdict(list)

    def add_edge(self, x, y, d):
        self.neighbors[x].append((y, d))
        self.neighbors[y].append((x, d))

    def compute_all(self, s):
        distances = [float('inf') for _ in range(self.n_nodes)]
        visited = [False for _ in range(self.n_nodes)]
        prev_nodes = [None for _ in range(self.n_nodes)]
        distances[s] = 0
        q = []
        for t in range(self.n_nodes):
            heapq.heappush(q, (distances[t], t))
        while q:
            dist_x, x = heapq.heappop(q)
            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.neighbors[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes


n = int(input())
dijkstra = Dijkstra(n)
for _ in range(n - 1):
    a, b = map(int, input().split())
    dijkstra.add_edge(a - 1, b - 1, 1)
ds0, _ = dijkstra.compute_all(0)
ds1, _ = dijkstra.compute_all(n - 1)
count = 0
for d0, d1 in zip(ds0, ds1):
    if d0 <= d1:
        count += 1
if count > n // 2:
    print('Fennec')
else:
    print('Snuke')