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


n = int(input())
edges = [[] for i 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)

todo = deque([(0, 1), (n-1, 2)])

colors = [0] * n
colors[0] = 1
colors[-1] = 2

while todo:
    node, color = todo.popleft()
    for to in edges[node]:
        if colors[to]:
            continue
        else:
            colors[to] = color
            todo.append((to, color))

fennec_count = colors.count(1)
if fennec_count > n // 2:
    print('Fennec ')

else:
    print('Snuke ')

Submission status: Accepted

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


n = int(input())
edges = [[] for _ in range(n)]

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

seen = [-1] * n
todo = [(0, 0)]

while todo:
    node, prev = todo.pop()
    if seen[node] != -1:
        continue

    seen[node] = prev
    for to in edges[node]:
        if seen[to] != -1:
            continue
        todo.append((to, node))


colors = [0] * n

node = n-1
goal_to_start = [n-1]
while node:
    node = seen[node]
    goal_to_start.append(node)

length = len(goal_to_start)
limit = (length) // 2

colors = [0] * n
for node in goal_to_start[:limit]:
    colors[node] = 2

for node in goal_to_start[limit:]:
    colors[node] = 1

fennec_todo = [node for node in range(n) if colors[node] == 1]
snuke_todo = [node for node in range(n) if colors[node] == 2]


def paint(todo, my_color):
    while todo:
        node = todo.pop()
        for to in edges[node]:
            if colors[to]:
                continue

            colors[to] = my_color
            todo.append(to)


paint(fennec_todo, 1)
paint(snuke_todo, 2)

feccec_count = len([color for color in colors if color == 1])
snuke_count = len([color for color in colors if color == 2])

if feccec_count > snuke_count:
    print('Fennec ')

else:
    print('Snuke ')

Submission status: Accepted

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


n = int(input())
edges = [[] for _ in range(n)]

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

seen = [-1] * n


def dfs(node, prev):
    if seen[node] != -1:
        return
    seen[node] = prev

    for to in edges[node]:
        dfs(to, node)


dfs(0, 0)

colors = [0] * n

node = n-1
goal_to_start = [n-1]
while node:
    node = seen[node]
    goal_to_start.append(node)

length = len(goal_to_start)
limit = (length) // 2

colors = [0] * n
for node in goal_to_start[:limit]:
    colors[node] = 2

for node in goal_to_start[limit:]:
    colors[node] = 1

fennec_todo = [node for node in range(n) if colors[node] == 1]
snuke_todo = [node for node in range(n) if colors[node] == 2]


def paint(todo, my_color):
    while todo:
        node = todo.pop()
        for to in edges[node]:
            if colors[to]:
                continue

            colors[to] = my_color
            todo.append(to)


paint(fennec_todo, 1)
paint(snuke_todo, 2)

feccec_count = len([color for color in colors if color == 1])
snuke_count = len([color for color in colors if color == 2])

if feccec_count > snuke_count:
    print('Fennec ')

else:
    print('Snuke ')

Submission status: Accepted

Solution code:
import sys
from collections import deque

N = int(sys.stdin.readline().strip())

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

visited = set()
q = {"fennec": deque([0]), "snuke": deque([N-1])}


count = {"fennec": 0, "snuke": 0}
while q["fennec"] or q["snuke"]:
    for user in ("fennec", "snuke"):
        if not q[user]:
            continue
        nq = deque()
        while q[user]:
            point = q[user].popleft()
            for point_next in edges[point]:
                if point_next in visited:
                    continue
                visited.add(point_next)
                count[user] += 1
                nq.append(point_next)
        q[user] = nq

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

Submission status: Accepted

Solution code:
from collections import deque

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

def calc_dist(node):
  dist = [-1] * N
  dist[node] = 0
  d = deque([[node, -1]])
  while d:
    node, p = d.pop()
    children = tree[node]
    for child in children:
      if child == p:
        continue
      dist[child] = dist[node] + 1
      d.append([child, node])
  return dist

d1 = calc_dist(0)
dN = calc_dist(N-1)

fennec = snuke = 0
for node in range(1, N-1):
  if d1[node] <= dN[node]:
    fennec += 1
  else:
    snuke += 1

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

Submission status: Accepted

Solution code:
# 全ての頂点について、フェネックからの距離とすぬけくんからの距離を求める
# フェネックからの距離 <= すぬけくんから距離　の頂点は黒　そうでなければ白

import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  
dist_from_fen = [-1 for i in range(N)]
dist_from_snk = [-1 for i in range(N)]

stack = []
# 頂点、距離、親
stack.append([0,0,-1])
while stack:
  v,dist,parent = stack.pop()
  dist_from_fen[v] = dist
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child,dist + 1,v])

stack = []
stack.append([N - 1,0,-1])
while stack:
  v,dist,parent = stack.pop()
  dist_from_snk[v] = dist
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child,dist + 1,v])

black = 0
white = 0
for i in range(N):
  if dist_from_fen[i] <= dist_from_snk[i]:
    black += 1
  else:
    white += 1
print(("Snuke","Fennec")[black > white])

Submission status: Accepted

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

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


dist=[float("inf")]*N
dist[0]=0
prev=[None]*N

def dfs1(v,parent,d):
    prev[v]=parent
    dist[v]=d
    for v2 in graph[v]:
        if v2==parent:
            continue
        dfs1(v2,v,d+1)

dfs1(0,-1,0)

x=N-1
for _ in range((dist[-1]-1)//2):
    x=prev[x]
cant_go=prev[x]

sunuke_score=0
def dfs2(v,parent):
    global sunuke_score
    sunuke_score+=1
    for v2 in graph[v]:
        if v2==parent:
            continue
        if v2==cant_go:
            continue
        dfs2(v2,v)

dfs2(x,-1)

fennec_score=N-sunuke_score
if sunuke_score>=fennec_score:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)
INF = 10**18
dist = [INF]*n
dist[0] = 0
prev = [None]*n


def dfs(v, parent, d):
    prev[v] = parent
    dist[v] = d
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, d+1)


dfs(0, -1, 0)

x = n-1
for _ in range((dist[-1]-1)//2):
    x = prev[x]
cant_go = prev[x]


def dfs2(v, parent):
    global snuke_v_cnt
    snuke_v_cnt += 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        if v2 == cant_go:
            continue
        dfs2(v2, v)


snuke_v_cnt = 0
dfs2(x, -1)

fennec_v_cnt = n-snuke_v_cnt
print('Fennec' if snuke_v_cnt < fennec_v_cnt else 'Snuke')

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
ab = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

sd = [-1]*(N+1)
q = deque()
q.append((1, 0))
while len(q) > 0:
    u, c = q.popleft()
    sd[u] = c
    for v in ab[u]:
        if sd[v] == -1:
            q.append((v, c+1))

ed = [-1]*(N+1)
q = deque()
q.append((N, 0))
while len(q) > 0:
    u, c = q.popleft()
    ed[u] = c
    for v in ab[u]:
        if ed[v] == -1:
            q.append((v, c+1))

sc = 0
for i in range(1, N+1):
    if sd[i] <= ed[i]:
        sc += 1
ec = N-sc
if sc > ec:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
AB = [list(map(int,input().split())) for _ in range (N-1)]
edge = [[] for _ in range(N)]
for u,v in AB:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

dists = [0]*N
distn = [0]*N
def dfs_s(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        dists[nv] = dists[v] + 1
        dfs_s(nv, v)
    return 
def dfs_n(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        distn[nv] = distn[v] + 1
        dfs_n(nv, v)
    return 
dfs_s(0,-1)
dfs_n(N-1,-1)

B = 0
W = 0
for i in range(N):
    if dists[i]<=distn[i]:
        B += 1
    else:
        W += 1

if B>W:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
# 2020-05-28 22:45:55

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

edge = [[] for _ in range(N)]
for u,v in ab:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

fromNode = [0] * N
def dfs(v, p):
    for nv in edge[v]:
        if nv==p:continue 
        fromNode[nv] = v
        dfs(nv, v)
    return 

def pathFind(s, g, fromNode):
    path = []
    while s!=g:
        g = fromNode[g]
        if g==s:break
        path.append(g)
    path.reverse()
    return path
dfs(0,-1)
path = pathFind(0,N-1,fromNode)

colors = [-1]*N
colors[0] = 0
colors[N-1] = 1
for i in range(len(path)):
    if i<=(len(path)-1)//2:
        colors[path[i]] = 0
    else:
        colors[path[i]] = 1

def dfs_color(v, p, c):
    for nv in edge[v]:
        if nv==p:continue 
        if colors[nv]==-1:
            colors[nv] = c
            dfs_color(nv, v, c)
    return 

dfs_color(0,-1,0)
dfs_color(N-1, -1, 1)
for p in path:
    c = colors[p]
    dfs_color(p, -1, c)

B = 0
W = 0
for c in colors:
    if c==0:B+=1
    elif c==1:W+=1

if B>W:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
N=int(input())
D=[[] for i in range(N)]
F,S=[-1]*N,[-1]*N
F[0]=0
S[N-1]=0
for i in range(N-1):
  a,b=map(int, input().split())
  a-=1
  b-=1
  D[a].append(b)
  D[b].append(a)
 
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
dis=0

def bfs(n):
  t=0
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if F[i]==-1 and i!=x: 
        F[i]=F[x]+1
        q.append(i)

def bfs2(n):
  t=0
  q=deque()
  q.append(n)
  while len(q):
    x=q.popleft()
    for i in D[x]:
      if S[i]==-1 and i!=x:
        S[i]=S[x]+1
        q.append(i)
bfs(0)
bfs2(N-1)
f,s=0,0
for i in range(N):
  if F[i]<=S[i]:
    f+=1
  else:
    s+=1
#print(F,S,f,s)
if f<=s:
  print('Snuke')
else:
  print('Fennec')

Submission status: Accepted

Solution code:
from queue import deque

n = int(input())
li = [[] for _ in range(n+1)]

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

def width_prime(start,li,n):
    inf = 10**10
    visited = [False]*(n+1)
    length = [inf]*(n+1)
    length[start] = 0
    visited[start] = True
    work_queue = deque([])
    work_queue.append(start)
    while work_queue:
        now = work_queue.popleft()
        visited[now] = True
        for i in li[now]:
            if visited[i]:
                continue
            work_queue.append(i)
            visited[i] = True
            if length[i] > length[now]+1:
                length[i] = length[now]+1
    return length

le_fe = width_prime(1,li,n)
le_su = width_prime(n,li,n)

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def restore_path(seq, start, goal):
        buf = []
        current = goal
        while current != start:
            buf.append(current)
            current = seq[current]
        buf.append(start)
        buf.reverse()
        return buf


    def calc_dist_path_in_bfs(adj, start, goal):
        q = deque()
        q.append([[start, None], 0])
        prev_memo = [None] * n
        while q:
            (u, prev), dist = q.popleft()
            if u == goal:
                prev_memo[u] = prev
                return dist, restore_path(prev_memo, start, goal)
            if not visited[u]:
                visited[u] = True
                prev_memo[u] = prev
                for v in adj[u]:
                    if not visited[v]:
                        q.append([[v, u], dist+1])
    
    def calc_node_in_dfs(adj, start):
        cnt = 1
        stack = [start]
        visited[start] = True
        while stack:
            # print(stack)
            u = stack[-1]
            for v in adj[u]:
                if not visited[v]:
                    stack.append(v)
                    visited[v] = True
                    cnt += 1                  
                    break
            else:
                stack.pop()
        return cnt


    n = ii()
    adj = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = mi_0()
        adj[a].append(b)
        adj[b].append(a)
    
    visited = [False] * n
    dist, path = calc_dist_path_in_bfs(adj, start=0, goal=n-1)
    # print(dist)
    # print(path)
    
    visited = [False] * n
    if dist % 2 == 1:
        i = path[(dist-1)//2]
        j = path[(dist-1)//2 + 1]
        adj[i].remove(j)
        adj[j].remove(i)
        # i 彩色数 > j 彩色数 で Fennec 勝ち
        i_color = calc_node_in_dfs(adj, i)
        j_color = calc_node_in_dfs(adj, j)
        print('Fennec') if i_color > j_color else print('Snuke')
    else:
        i = path[dist//2]
        j = path[dist//2+1]
        adj[i].remove(j)
        adj[j].remove(i)
        # i 彩色数 >= j 彩色数 で Fennec 勝ち
        i_color = calc_node_in_dfs(adj, i)
        j_color = calc_node_in_dfs(adj, j)
        print('Fennec') if i_color >= j_color else print('Snuke')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from queue import Queue

INF = 10 ** 5
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)
d1 = [INF] * N
d2 = [INF] * N
d1[0] = 0
d2[N-1] = 0

q1 = Queue()
q1.put((0,0))

while not q1.empty():
    x, c = q1.get()
    for u in edges[x]:
        if d1[u] == INF:
            d1[u] = c + 1
            q1.put((u,c+1))

q2 = Queue()
q2.put((N-1,0))

while not q2.empty():
    x, c = q2.get()
    for u in edges[x]:
        if d2[u] == INF:
            d2[u] = c + 1
            q2.put((u,c+1))

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

if black <= white:
    print('Snuke')
else:
    print('Fennec')

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
INF = 10**6


def dijkstra(N, adj_nodes, start_node, non_use_node):
    assert start_node != non_use_node
    d = [INF for _ in range(N)]
    d[start_node] = 0
    frontier = [(0, start_node)]
    while len(frontier) > 0:
        dist, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if next_node == non_use_node:
                continue
            if d[next_node] > dist + 1:
                d[next_node] = dist + 1
                heapq.heappush(frontier, (d[next_node], next_node))
    return d


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    fen_node, snu_node = 0, N - 1
    d_fen = dijkstra(N, adj_nodes, fen_node, snu_node)
    d_snu = dijkstra(N, adj_nodes, snu_node, fen_node)
    fen_score = 0
    for f, s in zip(d_fen, d_snu):
        fen_score += 1 if f <= s else 0
    snu_score = N - fen_score
    # answer
    if fen_score <= snu_score:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
N = int(input())
G = [[] for _ in range(N)]

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

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist

FE = dfs(G, N, 0)
SN = dfs(G, N, N-1)

get_count = sum(FE[i] <= SN[i] for i in range(N))
print('Fennec' if get_count > N-get_count else 'Snuke')

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
dic = defaultdict(set)
n = int(input())
for i in range(n-1):
    a, b = map(int, input().split())
    dic[a].add(b)
    dic[b].add(a)
q = deque([(1, 'F'), (n, 'S')])
seen = set([1, n])
f = 1
s = 1
while q:
    p, player = q.popleft()
    for child in dic[p]:
        if child not in seen:
            seen.add(child)
            q.append((child, player))
            if player == 'F':
                f += 1
            else:
                s += 1
print('Fennec' if f > s else 'Snuke')

Submission status: Accepted

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


def input(): return sys.stdin.readline().strip()


def resolve():

    # https://atcoder.jp/contests/abc070/tasks/abc070_d
    # https://atcoder.jp/contests/abc070/submissions/11681543
    from heapq import heapify, heappop, heappush

    inf = 10 ** 17

    def dijkstra_heap(start, edge):
        # 始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        # a:重み(//), b:次の頂点(%)
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)

        while len(edgelist):
            # まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d

    # N:頂点数 W:辺数
    N = int(input())
    W = N-1

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

    fen = dijkstra_heap(0, edge)
    sun = dijkstra_heap(N-1, edge)
    f = 0
    s = 0

    for i in range(1, N-1):
        if fen[i] <= sun[i]:
            f += 1
        elif fen[i] > sun[i]:
            s += 1
    print('Fennec' if f > s else 'Snuke')


resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(N+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1, d2 = dfs(1), dfs(N)
a = sum(d1[i]<=d2[i] for i in range(1, N+1))
print("Fennec" if 2*a>N else "Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(N+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

d1, d2 = dfs(1), dfs(N)
a = sum(d1[i]<=d2[i] for i in range(1, N+1))
print("Fennec" if a>N-a else "Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
def getSP(v,d):
    p=v
    if dist[v]==d:
        return v
    for nv in G[v]:
       if dist[nv]<dist[v]:
           p=getSP(nv,d)
    return p
    
def Sdepth(v):
    res=1
    if not G[v]:
        return 1
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        res+=Sdepth(nv)
    return res
    
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dist=[-1]*N
dfs(0,-1,0)
P=(dist[N-1]-1)//2
sp=getSP(N-1,dist[N-1]-P)
dep=Sdepth(sp)
Sunu=dep-(dist[N-1]-dist[sp]+1)
Fene=N-dep-dist[sp]
if dist[N-1]%2:
    print('Fennec' if Fene>Sunu else 'Snuke')
else:
    print('Fennec' if Fene>=Sunu else 'Snuke')

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(edges, n_nodes):
    visited = [None] * n_nodes
    visited[0] = "B"
    visited[-1] = "W"

    q = deque([0, n_nodes - 1])

    while q:
        i = q.popleft()

        for j in edges[i]:
            if visited[j] is None:
                visited[j] = visited[i]
                q.append(j)

    return visited


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

    visited = bfs(edges, N)
    if visited.count("B") > visited.count("W"):
        print("Fennec")
    else:
        print("Snuke")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b=map(int1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    cost=[INF]*N
    cost[0]=0
    stack=[0]
    while stack:
        v=stack.pop()
        for nv in edge[v]:
            if cost[nv]==INF:
                cost[nv]=cost[v]+1
                stack.append(nv)
                if nv==N-1:
                    break
    d=cost[N-1]
    v=N-1
    for i in range(d+1):
        if i==(d-1)//2:
            sv=v
        elif i==(d+1)//2:
            fv=v
            break
        for nv in edge[v]:
            if cost[nv]==cost[v]-1:
                v=nv
                break

    stack=[sv]
    used=[False]*N
    used[fv]=True
    c=0
    while stack:
        v=stack.pop()
        used[v]=True
        c+=1
        for nv in edge[v]:
            if not used[nv]:
                stack.append(nv)
    if c>=N-c:
        print('Snuke')
    else:
        print('Fennec')
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ab = [[] for i in range(n)]

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

fnc = deque()
snk = deque()

fnc.appendleft(0)
snk.appendleft(n-1)

check = [0]*(n)

check[0] = 1
check[n-1] = 1

fnc_num = 0
snk_num = 0

while len(fnc) > 0 or len(snk) > 0:
    for i in range(len(fnc)):
        tmp = fnc.popleft()
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                fnc_num += 1
                check[ab[tmp][j]] = 1
                fnc.append(ab[tmp][j])
                
    for i in range(len(snk)):
        tmp = snk.popleft()
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                snk_num += 1
                check[ab[tmp][j]] = 1
                snk.append(ab[tmp][j])
                
    #fnc.popleft()
    #snk.popleft()
    
if fnc_num > snk_num:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque


def bfs(v, N):
    dist = [-1 for _ in range(N)]
    que = deque()
    que.append((v, 0, -1))
    while que:
        (now, cost, par) = que.popleft()
        dist[now] = cost
        for edge in edges[now]:
            if edge == par:
                continue
            que.append((edge, cost + 1, now))
    return dist


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

dist_from_one = bfs(0, N)
dist_from_N = bfs(N - 1, N)
fennec = 0
for i in range(N):
    fennec += int(dist_from_one[i] <= dist_from_N[i])

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

Submission status: Accepted

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

qf = queue.Queue()
qs = queue.Queue()
qf.put(1)
qs.put(n)
who = ["" for i in range(n+1)]
wht = [10**5+5 for i in range(n+1)]
who[0] = "N"
who[1] = "F"
who[n] = "S"
wht[0] = 0
wht[1] = 0
wht[n] = 1


while not(qf.empty() and qs.empty()):
    if not qf.empty():
        fi = qf.get()
        if who[fi] == "F":
            for i in way[fi]:
                if wht[i] > wht[fi] + 2:
                    qf.put(i)
                    wht[i] = wht[fi] + 2
                    who[i] = "F"
    if not qs.empty():
        si = qs.get()
        if who[si] == "S":
            for i in way[si]:
                if wht[i] > wht[si] + 2:
                    qs.put(i)
                    wht[i] = wht[si] + 2
                    who[i] = "S"

if who.count("F") > who.count("S"):
    print("Fennec")
else:
    print("Snuke")