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
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

#木なので一度に隣り合うマスを全て塗っても答えは同じ
N = ir()
edges = [[] for _ in range(N+1)] #1-indexed
for _ in range(N-1):
    a, b = lr()
    edges[a].append(b)
    edges[b].append(a)

fen = 0
snu = 0
used = set([1, N])
fen_list = [1]
snu_list = [N]
while fen_list or snu_list:
    f = []
    for x in fen_list:
        for next in edges[x]:
            if next in used:
                continue
            fen += 1
            f.append(next)
            used.add(next)
    fen_list = f
    s = []
    for y in snu_list:
        for next in edges[y]:
            if next in used:
                continue
            snu += 1
            s.append(next)
            used.add(next)
    snu_list = s

print('Fennec' if fen > snu else 'Snuke')
# 46

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 -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


def d(s):
    ret = [10 ** 18] * n
    ret[s] = 0
    q = deque()
    q.append(s)
    while len(q):
        now = q.popleft()
        for to in g[now]:
            if ret[to] < 10 ** 18:
                continue
            ret[to] = ret[now] + 1
            q.append(to)
    return ret


# print(d(n-1))

fennec = d(0)
snuke = d(n - 1)
cnt = 0
for i in range(n):
    if fennec[i] <= snuke[i]:
        cnt += 1
    else:
        cnt -= 1
if cnt > 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
N=int(input())
import collections
import heapq
ab=[tuple(map(int,input().split())) for i in range(N-1)]
G=[set() for i in range(N)]
for a,b in ab:
  a-=1
  b-=1
  G[a].add(b)
  G[b].add(a)
q=collections.deque()

dis=[[-1]*N for i in range(2)]
dis[0][0]=0
q.append(0)
while(q):
  x=q.popleft()
  for y in G[x]:
    if dis[0][y]==-1:
      q.append(y)
      dis[0][y]=dis[0][x]+1
dis[1][N-1]=0
q.append(N-1)
while(q):
  x=q.popleft()
  for y in G[x]:
    if dis[1][y]==-1:
      q.append(y)
      dis[1][y]=dis[1][x]+1

hqF=[(0,0)]
hqS=[(0,N-1)]
colord=[False]*N

while(1):
  if len(hqF)==0:
    print("Snuke")
    exit(0)
  _,x = heapq.heappop(hqF)
  while(colord[x]):
    if hqF:
      _,x = heapq.heappop(hqF)
    else:
      print("Snuke")
      exit(0)
  colord[x]=True
  for y in G[x]:
    if colord[y]==False:
      heapq.heappush(hqF,(dis[1][y],y))

  if len(hqS)==0:
    print("Fennec")
    exit(0)
  _,x = heapq.heappop(hqS)
  while(colord[x]):
    if hqF:
      _,x = heapq.heappop(hqS)
    else:
      print("Fennec")
      exit(0)
  colord[x]=True
  for y in G[x]:
    if colord[y]==False:
      heapq.heappush(hqS,(dis[0][y],y))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
ab = [LIST() for _ in range(N-1)]

def dijkstra(E, start):
   N_d = len(E)
   dist = [INF] * N_d
   dist[start] = 0
   q = [(0, start)]
   while q:
       dist_v, v = heappop(q)
       if dist[v] != dist_v:
           continue
       for u, dist_vu in E[v]:
           dist_u = dist_v + dist_vu
           if dist_u < dist[u]:
               dist[u] = dist_u
               heappush(q, (dist_u, u))
   return dist

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

for a, b in ab:
	E[a-1].append((b-1, 1))
	E[b-1].append((a-1, 1))

d_f = dijkstra(E, 0)
d_s = dijkstra(E, N-1)

f = 0
s = 0
for i in range(N):
	if d_f[i] <= d_s[i]:
		f += 1
	else:
		s += 1

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

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

    def dfs(s) -> list:
        init = n

        d = [init] * n
        d[s] = 0

        q = deque()
        q.append(s)
        while q:
            v = q.popleft()
            for u in g[v]:
                if d[u] != init:
                    continue
                d[u] = d[v] + 1
                q.append(u)

        return d

    n = int(input())

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

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

    fennec = sum(dist_1[v] <= dist_n[v] for v in range(n))
    snuke = n - fennec

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    def dfs(v, d):
        for u in g[v]:
            if d[u] != init:
                continue
            d[u] = d[v] + 1
            dfs(u, d)

    n = int(input())

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

    init = n

    dist_1 = [init] * n
    dist_1[0] = 0
    dfs(0, dist_1)

    dist_n = [init] * n
    dist_n[n - 1] = 0
    dfs(n - 1, dist_n)

    fennec = sum(dist_1[v] <= dist_n[v] for v in range(n))
    snuke = n - fennec

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


ans=0

n=I()
g,c=GI(n,n-1)


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

def dfs(x,s):
    r=[]
    for i in x:
        for nb in g[i]:
            if v[nb]==-1:
                r.append(nb)
                v[nb]=s
    return r

F=[0]
S=[n-1]
while F or S:
    F=dfs(F,1)
#    show('F',v,F,S)
    S=dfs(S,0)
#    show('S',v,F,S)

if sum(v)>n//2:
    ans='Fennec'
else:
    ans='Snuke'
    
print(ans)

Submission status: Accepted

Solution code:
#フェネックバーサス　スヌーく
n=int(input())
tree_list={i:[] for i  in range(1,n+1)}
for i  in range(n-1):
    a,b=map(int,input().split())
    tree_list[a].append(b)
    tree_list[b].append(a)
painted=[False for i in range(n+1)]
painted[1]="black"
painted[n]="white"
from collections import deque
d_white=deque()
e_white=deque()

d_black=deque()
e_black=deque()

d_black.append(1)
d_white.append(n)

while(d_black or d_white):
    for some in d_black:
        for point in tree_list[some]:
            if painted[point]==False:
                painted[point]="black"
                e_black.append(point)
    d_black=e_black
    e_black=deque()
    
    for some in d_white:
        for point in tree_list[some]:
            if painted[point]==False:
                painted[point]="white"
                e_white.append(point)
    d_white=e_white
    e_white=deque()
sunke=0
fennec=0
for i in range(1,n+1):
  if painted[i]=="white":
    sunke+=1
  elif painted[i]=="black":
    fennec+=1
if fennec>sunke:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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)
from collections import deque
que=deque()
que.append(0)
unvisited=[1]*n
unvisited[0]=0
lf=[0]*n
while que:
    v=que.pop()
    for u in g[v]:
        if unvisited[u]:
            lf[u]=lf[v]+1
            que.appendleft(u)
            unvisited[u]=0
que=deque()
que.append(n-1)
unvisited=[1]*n
unvisited[n-1]=0
ls=[0]*n
while que:
    v=que.pop()
    for u in g[v]:
        if unvisited[u]:
            ls[u]=ls[v]+1
            que.appendleft(u)
            unvisited[u]=0
f=0
for i in range(n):
    if lf[i]<=ls[i]:
        f+=1
if f>n-f:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

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

dists1 = [float('inf') for _ in range(N)]
used = [False for _ in range(N)]
dists1[0] = 0
used[0] = True

buf = [0]
while buf:
    src = buf.pop()
    for dst, w in edges[src]:
        if not used[dst]:
            dists1[dst] = dists1[src] + w
            used[dst] = True
            buf.append(dst)

dists2 = [float('inf') for _ in range(N)]
used = [False for _ in range(N)]
dists2[N - 1] = 0
used[N - 1] = True

buf = [N - 1]
while buf:
    src = buf.pop()
    for dst, w in edges[src]:
        if not used[dst]:
            dists2[dst] = dists2[src] + w
            used[dst] = True
            buf.append(dst)

num1, num2 = 0, 0
for d1, d2 in zip(dists1, dists2):
    if d1 <= d2:
        num1 += 1
    elif d1 > d2:
        num2 += 1

if num1 > num2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph, stack, visited, times):
    cnt = 0
    while stack:
        a,cost = stack.popleft()
        if cost > times:
            stack.appendleft([a,cost])
            break
        for b in graph[a].keys():
            if not visited[b]:
                stack.append([b,cost+1])
                visited[b] += 1 
                cnt += 1
    return cnt

def bi_bfs(graph, start, goal):
    s_stack, g_stack = deque(), deque()
    s_stack.append([start,0])
    g_stack.append([goal, 0])
    visited = [0 for i in range(N+1)]
    visited[start] = visited[goal] = 1 
    s_cnt = g_cnt = 1
    times = 0

    while s_stack or g_stack:
        s_cnt += bfs(graph, s_stack, visited, times)
        g_cnt += bfs(graph, g_stack, visited, times)
        times += 1
    return s_cnt > g_cnt

N = int(input())
graph = {}
for i in range(N-1):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
print('Fennec' if bi_bfs(graph,1,N) else 'Snuke')

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph, start, goal):
    s_stack = deque()
    g_stack = deque()
    visited = [0 for i in range(N+1)]
    s_stack.append([start,0])
    g_stack.append([goal, 0])
    visited[start] = 1 
    visited[goal] = 1 
    s_cnt = 1
    g_cnt = 1
    round = 0
    while s_stack or g_stack:
        while s_stack:
            a,cost = s_stack.popleft()
            if cost > round:
                s_stack.appendleft([a,cost])
                break
            for b in graph[a].keys():
                if not visited[b]:
                    s_stack.append([b,cost+1])
                    visited[b] += 1 
                    s_cnt += 1
        while g_stack:
            a, cost = g_stack.popleft()
            if cost > round:
                g_stack.appendleft([a,cost])
                break
            for b in graph[a].keys():
                if not visited[b]:
                    g_stack.append([b,cost+1])
                    visited[b] += 1 
                    g_cnt += 1
        round += 1
    # print(s_cnt, g_cnt)
    # print(visited)
    return s_cnt > g_cnt

N = int(input())
graph = {i:{} for i in range(1,N+1)}
for i in range(N-1):
    a,b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1
print('Fennec' if bfs(graph,1,N) else 'Snuke')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みなし) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c = stack.pop()
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                stack.append((v, u, c+1))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

# それぞれから最短距離
res1 = dfs(N, nodes, 0)
res2 = dfs(N, nodes, N-1)

cnt = 0
for i in range(N):
    # 相手より距離が近い場所(同値含む)は自分のマスにできる
    if res1[i] <= res2[i]:
        cnt += 1
# 自分のマスが半分超なら勝ち(半分ちょうどだと負ける)
if cnt > N // 2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

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

def main():
  n = int(input())
  F = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)
  seenB = [False]*n
  seenW = [False]*n
  distB = [0]*n
  distW = [0]*n
  def dfs(v, seen, dist):
    seen[v] = True
    for nv in F[v]:
      if seen[nv]:
        continue
      dist[nv] = dist[v] + 1
      dfs(nv, seen, dist)
  dfs(0, seenB, distB)
  dfs(n-1, seenW, distW)
  b, w = 0, 0
  for i in range(n):
    if distB[i] <= distW[i]:
      b += 1
    else:
      w += 1
  if b > w:
    print("Fennec")
  else:
    print("Snuke")
      
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N -1)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)

def dfs(n):
  INF = 10 ** 10
  dist = [INF] * (N + 1)

  stack = [n]
  dist[n] = 0
  while stack:
    s = stack.pop()
    for g in graph[s]:
      if dist[s] + 1 < dist[g]:
        stack.append(g)
        dist[g] = dist[s] + 1
  return dist

dist_f = dfs(1)
dist_a = dfs(N)
D = dist_f[N]
#print("dist_f:", dist_f)
#print("dist_a:", dist_a)

f_cnt = 0
a_cnt = 0

color = [0] * (N + 1)
color[1] = 1
color[N] = -1

for i in range(1, N + 1):
  if dist_f[i] <= D // 2:
    if color[i] == 0:
      f_cnt += 1
      color[i] = 1
  if dist_a [i] <= (D - 1) // 2:
    if color[i] == 0:
      a_cnt += 1
      color[i] = -1
#print("color:", color)
#print("f_cnt, a_cnt:", f_cnt, a_cnt)

def paint(n):
  cnt = 0
  for i in range(1, N + 1):
    if color[i] == n:
      stack = [i]
      while stack:
        s = stack.pop()
        for g in graph[s]:
          if color[g] == 0:
            stack.append(g)
            color[g] = n
            cnt += 1
  return cnt

f_cnt += paint(1)
a_cnt += paint(-1)

if f_cnt >= a_cnt + 1:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
import sys

n, *ab = map(int, sys.stdin.read().split())
graph = [[]for _ in range(n+1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    stack = [v]
    dist = [None] * (n + 1)
    dist[v] = 0
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist

def main():
    dist_1 = dfs(1)
    dist_n = dfs(n)
    black_cnt = 0
    for i in range(1, n+1):
        if dist_1[i] <= dist_n[i]:
            black_cnt += 1

    if black_cnt <= n // 2:
        return 'Snuke'
    else:
        return 'Fennec'

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

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for _ 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)
s = [0]
d1 = [-1] * n
d1[0] = 0
while s:
    d = s.pop()
    for node in g[d]:
        if d1[node] == -1:
            s.append(node)
            d1[node] = d1[d] + 1
s = [n - 1]
d2 = [-1] * n
d2[n - 1] = 0
while s:
    d = s.pop()
    for node in g[d]:
        if d2[node] == -1:
            s.append(node)
            d2[node] = d2[d] + 1
f, s = 0, 0
for i in range(n):
    if d1[i] <= d2[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 sys
input = sys.stdin.readline

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

DF = [None]*N
DF[0] = 0
queue = [0]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if DF[e] is not None: continue
            DF[e] = DF[q]+1
            queue_new.append(e)
    queue = queue_new

DS = [None]*N
DS[N-1] = 0
queue = [N-1]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if DS[e] is not None: continue
            DS[e] = DS[q]+1
            queue_new.append(e)
    queue = queue_new
    
NF, NS = 0, 0
for df, ds in zip(DF,DS):
    if df<=ds: NF+=1
    else: NS+=1

print('Fennec' if NF>NS else 'Snuke')

Submission status: Accepted

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

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

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

Fennec = np.count_nonzero(d1 <= dn)

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

Submission status: Accepted

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

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

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

Fennec = -1
for i, j in zip(d1, dn):
    if i <= j:
        Fennec += 1

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

Submission status: Accepted

Solution code:
def d_fennec_vs_snuke():
    from collections import deque
    N = int(input())
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    graph = [[] for _ in range(N)]
    for a, b in Edges:
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    def bfs(start, tree_size=N, tree=graph):
        """木のある頂点 start からの距離を求める (start は 0-origin)"""
        dist = [0] * tree_size
        is_visited = [False] * tree_size
        is_visited[start] = True

        queue = deque([start])
        while queue:
            current = queue.pop()
            for child in tree[current]:
                if is_visited[child]:
                    continue
                is_visited[child] = True
                dist[child] = dist[current] + 1
                queue.appendleft(child)
        return dist

    fennec_dist, snuke_dist = bfs(0), bfs(N - 1)
    fennec_point, snuke_point = 0, 0  # 各々が色を塗れたマスの数

    for fennec, snuke in zip(fennec_dist, snuke_dist):
        if fennec <= snuke:
            fennec_point += 1
        else:
            snuke_point += 1
    return 'Fennec' if fennec_point > snuke_point else 'Snuke'

print(d_fennec_vs_snuke())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


def dfs_f(now, kyori):
    kyori_f[now] = kyori
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        # 行ったことがない、白く塗られていない
        if not memo_f[next] and next != n - 1:
            memo_f[next] = True
            dfs_f(next, kyori + 1)


def dfs_s(now, kyori):
    kyori_s[now] = kyori
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        # 行ったことがない、黒く塗られていない
        if not memo_s[next] and next != 0:
            memo_s[next] = True
            dfs_s(next, kyori + 1)


n = int(input())
g = [[] * n for i in range(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)

# フェネック
memo_f = [False for i in range(n)]  # 訪れたことがあるか
kyori_f = [float("inf") for i in range(n)]  # 始点からの距離
memo_f[0] = True
dfs_f(0, 0)

# すぬけ
memo_s = [False for i in range(n)]  # 訪れたことがあるか
kyori_s = [float("inf") for i in range(n)]  # 始点からの距離
memo_s[n - 1] = True
dfs_s(n - 1, 0)

black = 0
white = 0
for i in range(n):
    if kyori_f[i] <= kyori_s[i]:
        black += 1
    else:
        white += 1

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

Submission status: Accepted

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

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

def BFS(n, E, i0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

A = BFS(N, X, 0)
B = BFS(N, X, N-1)
print("Snuke" if sum([A[i] <= B[i] for i in range(N)]) * 2 <= N else "Fennec")

Submission status: Accepted

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

n = int(input())
graph = {i : [] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

stack = [0]
already = set()
parent = [i for i in range(n)]
flg = False
while len(stack) > 0:
    cur = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next not in already:
            stack.append(_next)
            parent[_next] = cur
            if _next == n - 1:
                flg = True
                break
    if flg:
        break

path = []
cur = n - 1
while cur != 0:
    path.append(cur)
    cur = parent[cur]
path.append(0)
path.reverse()
flg_2 = len(path) % 2 != 0
left = path[len(path) // 2 - 1 + flg_2]
right = path[len(path) // 2 + flg_2]

def dfs(x, last):
    res = 1
    for _next in graph[x]:
        if _next != last:
           res += dfs(_next, x)
    return res

left_res = dfs(left, right)
#print(left_res)
print("Fennec" if left_res > (n - left_res) else "Snuke")

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline

    N = int(input())

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

    check = [0] * (N + 1)
    que1 = deque() #fennecのキュー
    que2 = deque() #sunukeのキュー

    que1.append(1)
    que2.append(N)

    check[1] = 1
    check[N] = 1

    fennec = 0
    snuke = 0

    flag = True

    while flag:
        flag = False

        tmp_lst = []
        while len(que1) != 0:
            flag = True
            tmp = que1.popleft()
            for next_ in graph[tmp]:
                if check[next_] == 0:
                    tmp_lst.append(next_)
                    fennec += 1
                    check[next_] = 1
        for i in tmp_lst:
            que1.append(i)
        
        tmp_lst = []
        while len(que2) != 0:
            flag = True
            tmp = que2.popleft()
            for next_ in graph[tmp]:
                if check[next_] == 0:
                    tmp_lst.append(next_)
                    snuke += 1
                    check[next_] = 1
        for i in tmp_lst:
            que2.append(i)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

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

check = [0] * (N + 1)
que1 = deque() #fennecのキュー
que2 = deque() #sunukeのキュー

que1.append(1)
que2.append(N)

check[1] = 1
check[N] = 1

fennec = 0
snuke = 0

flag = True

while flag:
    flag = False

    tmp_lst = []
    while len(que1) != 0:
        flag = True
        tmp = que1.popleft()
        for next_ in graph[tmp]:
            if check[next_] == 0:
                tmp_lst.append(next_)
                fennec += 1
                check[next_] = 1
    for i in tmp_lst:
        que1.append(i)
    
    tmp_lst = []
    while len(que2) != 0:
        flag = True
        tmp = que2.popleft()
        for next_ in graph[tmp]:
            if check[next_] == 0:
                tmp_lst.append(next_)
                snuke += 1
                check[next_] = 1
    for i in tmp_lst:
        que2.append(i)

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

Submission status: Accepted

Solution code:
N=int(input())
E=[[] 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].append(b)
  E[b].append(a)

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

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

Submission status: Accepted

Solution code:
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)
res=[0]*n
res[0]=1
res[n-1]=-1
q=[0,n-1]
while q:
    qq=[]
    for i in q:
        v=res[i]
        for j in g[i]:
            if not res[j]:
                res[j]=v
                qq.append(j)
    q=qq
if sum(res)>0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)

    # 0からn-1へのpathを求める
    path=[]
    def dfs(v,p=-1)->bool:
        if(v==n-1):
            path.append(v)
            return True
        for nv in E[v]:
            if(nv==p): continue
            if(dfs(nv,v)):
                path.append(v)
                return True
        return False
    dfs(0)
    path.reverse()
    k=len(path)
    a,b=path[(k+1)//2-1],path[(k+1)//2]

    # 辺a,bを削除する
    E[a].remove(b)
    E[b].remove(a)

    # このグラフに対して、0を含む連結成分の個数を求める
    from collections import deque
    Q=deque([0])
    visited=[0]*n
    while(Q):
        v=Q.popleft()
        visited[v]=1
        for nv in E[v]:
            if(visited[nv]): continue
            Q.append(nv)

    c=sum(visited)
    print("Fennec" if(c>n-c) else "Snuke")
resolve()