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
sys.setrecursionlimit(10 ** 9)

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


def dfs(n):
    dist = [-1] * N
    dist[n] = 0
    stack = [n]

    while stack:
        u = stack.pop()
        for v, c in T[u]:
            if dist[v] < 0:
                dist[v] = dist[u] + 1
                stack.append(v)
    return dist


Black = dfs(0)
White = dfs(N - 1)

Black_get = 0
for b, w in zip(Black, White):
    if b <= w:
        Black_get += 1

if Black_get > N // 2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
from pprint import pprint as pp
N = int(input())
abn = [list(map(int, input().split())) for _ in range(N-1)]

graph = defaultdict(lambda: defaultdict(int))

for a,b in abn:
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

# pp(graph)

def dist(x):
    que = [(x,0)]
    distance = [-1 for _ in range(N)]
    distance[x] = 0

    while len(que) > 0:
        i,tmpdist = que.pop(0)        

        for next in [k for k,v in  graph[i].items() if v == 1]:
            if distance[next] == -1:
                distance[next] = tmpdist + 1
                que.append((next, tmpdist + 1))

    return distance

distF = dist(0)
# pp(distF)
distS = dist(N-1)
# pp(distS)

Fcnt = 0
Scnt = 0
for f,s in zip(distF,distS):
    if f > s:
        Scnt += 1
    else:
        Fcnt += 1

if Fcnt > Scnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

def bfs(S):
    dist = [N] * (N + 1)
    dist[S] = 0
    q = deque([S])
    while q:
        u = q.pop()
        for v in adj[u]:
            if dist[v] == N:
                dist[v] = dist[u] + 1
                q.appendleft(v)
    return dist

db = bfs(1)
dw = bfs(N)

if sum(db[i] > dw[i] for i in range(1, N + 1)) >= N / 2:
    print('Snuke')
else:
    print('Fennec')

Submission status: Accepted

Solution code:
n = int(input())
c = []
for i in range(n - 1):#h:高さ
    c.append([int(m) - 1 for m in input().split()])
for i in range(n - 1):
    c[i].append(1)

def DFS(K, w,edges,N):
  cnt = 0
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    cnt += 1
    if label != w:
        for i,c in roots[label]:
          if dist[i]==-1:
            dist[i]=dist[label]+c
            stack+=[i]
  return cnt - 1

def DFS2(K,w,edges,N):
  htg = []
  prl = []
  for i in range(n):
      """htg.append([])"""
      prl.append([])
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a]+=[(b,c)]
    roots[b]+=[(a,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  """htg[0].append(0)"""
  while stack:
      label = stack.pop(-1)
      """if label != 0:
        htg[label] += htg[prl[label][0]]
        htg[label].append(label)"""
      for i,c in roots[label]:
        if dist[i]==-1:
          dist[i]=dist[label]+c
          stack+=[i]
          prl[i].append(label)
        if i==w:
            htg.append(i)
            while i != 0:
                gg = prl[i][0]
                htg.append(gg)
                i = gg
            return htg
#点は0始まり
htgn = DFS2(0, n - 1, c, n)
sroot = len(htgn) // 2
pnt = htgn[sroot - 1]

fenneccnt = DFS(0, pnt, c, n)#点は0始まり
snukecnt = n - fenneccnt
if fenneccnt > snukecnt:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

from collections import defaultdict

rs = defaultdict(set)

for a, b in AB:
    rs[a].add(b)
    rs[b].add(a)

from heapq import *

cs = [0] * (N + 1)
cs[1] = 1
cs[N] = 2

h = []
heappush(h, (1, 1))
heappush(h, (2, N))

bcount = 0

while h:
    t, x = heappop(h)
    bcount += t % 2
    for n in rs[x]:
        if cs[n] == 0:
            cs[n] = t + 2
            heappush(h, (t + 2, n))

if bcount > N - bcount:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
g = [[] for i in range(N)]
 
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    g[a] += [b]
    g[b] += [a]
    
def bfs(g, st):
    queue = [st]
    distances = [-1 for i in range(N)]
    distances[st] = 0
    
    while queue:
        node = queue.pop(0)
        for h in g[node]:
            if distances[h] == -1:
                distances[h] = distances[node] + 1
                queue += [h]
 
    return distances
 
dB = bfs(g, 0)
dW = bfs(g, N-1)
 
B, W = 0, 0
for i in range(N):
    if dB[i] <= dW[i]:
        B += 1
    else:
        W += 1
print("Fennec" if B > W else "Snuke")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dps(road,dist,node,d):
    for x in road[node]:
        if dist[x]<0:
            dist[x]=d
            dps(road,dist,x,d+1)
    
N=int(input())
road=[[] for _ in range(N)]
f_d=[-1 for _ in range(N)]
s_d=[-1 for _ in range(N)]
f_d[0]=0
s_d[-1]=0

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

dps(road,f_d,0,1)
dps(road,s_d,N-1,1)

white=0
black=0

for i in range(N):
    if f_d[i]<=s_d[i]:
        black+=1
    else:
        white+=1

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

Submission status: Accepted

Solution code:
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
dfs_stack_Fennec=[0]
dfs_stack_Snuke=[N-1]
depth_Fennec=[-1]*N
depth_Snuke=[-1]*N
depth_Fennec[0]=0
depth_Snuke[N-1]=0
while dfs_stack_Fennec or dfs_stack_Snuke:
  s1=dfs_stack_Fennec.pop()
  s2=dfs_stack_Snuke.pop()
  for t1 in graph[s1]:
    if depth_Fennec[t1]==-1:
      depth_Fennec[t1]=depth_Fennec[s1]+1
      dfs_stack_Fennec.append(t1)
  for t2 in graph[s2]:
    if depth_Snuke[t2]==-1:
      depth_Snuke[t2]=depth_Snuke[s2]+1
      dfs_stack_Snuke.append(t2)
ans=0
for i in range(N):
  if depth_Fennec[i]<=depth_Snuke[i]:
    ans+=1
if 2*ans>N:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
import heapq
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append([b, 1])
    T[b].append([a, 1])


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in T[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


B = dijkstra(0)
W = dijkstra(N - 1)

result = [("B" if b <= w else "W") for b, w in zip(B, W)]
print("Fennec" if result.count("B") - result.count("W") > 0 else "Snuke")

Submission status: Accepted

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

z=[[] for _ in range(n)]
for a,b in ab:
    z[a-1].append(b-1)
    z[b-1].append(a-1)
dis1=[0 for _ in range(n)]
dis2=[0 for _ in range(n)]

from collections import deque
que=deque([])
que.append((0,-1,0))
while que:
    v,p,d=que.pop()
    dis1[v]=d
    for t in z[v]:
        if t==p:
            continue
        que.append((t,v,d+1))
que.append((n-1,-1,0))
while que:
    v,p,d=que.pop()
    dis2[v]=d
    for t in z[v]:
        if t==p:
            continue
        que.append((t,v,d+1))
#print(dis1,dis2)
x,y=0,0
for i in range(n):
    if dis1[i]<=dis2[i]:
        x+=1
    else:
        y+=1
#print(x,y)
if x>y:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue
N = int(input())
edge = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

def bfs(s):
    dist = defaultdict(lambda:float('inf'))
    dist[s] = 0
    que = queue.Queue()
    que.put(s)
    while que.qsize():
        s = que.get()
        for t in edge[s]:
            if dist[t] > dist[s] + 1:
                dist[t] = dist[s] + 1
                que.put(t)
    return dist

fdist = bfs(1)
sdist = bfs(N)
f = 0
for i in range(1,N+1):
    if fdist[i] <= sdist[i]:
        f += 1
s = N-f
if f > s:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

from math import ceil
g = Graph()
N = int(input())
for i in range(N-1):
    a,b = map(int,input().split())
    g.add_edge(a,b)
    g.add_edge(b,a)

d = Dijkstra(g,1)
path = d.shortest_path(N)
n = ceil(len(path)/2)
flist = path[:n]
slist = path[n:]
a = flist[-1]
b = slist[0]
g.graph[a].pop(g.graph[a].index((b,1)))
g.graph[b].pop(g.graph[b].index((a,1)))
d = Dijkstra(g,1)
f = len(d.dist)
s = N-f

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

Submission status: Accepted

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

INF = float("inf")
que = deque()
que.append(0)
d = [INF] * N
d[0] = 0
rec = [None] * N
while que:
    v = que.popleft()
    for w in G[v]:
        if d[w] != INF:
            continue
        d[w] = d[v] + 1
        que.append(w)
        rec[w] = v

rec1 = [N - 1]
while rec[rec1[-1]] is not None:
    q = rec[rec1[-1]]
    rec1.append(q)
rec1 = rec1[::-1]
mid = d[-1] // 2 + 1
f = rec1[mid]

visited = [False] * N
visited[f] = True
fnum = 0
que = deque()
que.append(0)
while que:
    v = que.popleft()
    visited[v] = True
    fnum += 1
    for w in G[v]:
        if visited[w]:
            continue
        que.append(w)

snum = N - fnum
if fnum > snum:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

Qb, Qw = [0], [N-1]
dB, dW = [-1 for i in range(N)], [-1 for i in range(N)]
dB[0], dW[N-1] = 0, 0
while Qb:
    temp = Qb.pop(0)
    for n in P[temp]:
        if dB[n] == -1:
            dB[n] = dB[temp] + 1
            Qb.append(n)
while Qw:
    temp = Qw.pop(0)
    for n in P[temp]:
        if dW[n] == -1:
            dW[n] = dW[temp] + 1
            Qw.append(n)

B, W = 0, 0
for i in range(N):
    if dB[i] <= dW[i]:
        B += 1
    else:
        W += 1
print("Fennec" if B > W else "Snuke")

Submission status: Accepted

Solution code:
# ABC 067 D
import sys
sys.setrecursionlimit(200000)

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

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

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

Submission status: Accepted

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

parent = [-1 for i in range(n)]
dist = [-1 for i in range(n)]
flag = [0 for i in range(n)]

def dfs(s):
    flag[s] = 1
    dist[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag[i]:
                continue
            flag[i] = 1
            parent[i] = v[0]
            dist[i] = v[1] + 1
            q.append((i, v[1] + 1))

parent2 = [-1 for i in range(n)]
dist2 = [-1 for i in range(n)]
flag2 = [0 for i in range(n)]

def dfs_f(s):
    count2 = 0
    flag2[s] = 1
    dist2[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag2[i]:
                continue
            count2 += 1
            flag2[i] = 1
            parent2[i] = v
            dist2[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count2

parent3 = [-1 for i in range(n)]
dist3 = [-1 for i in range(n)]
flag3 = [0 for i in range(n)]

def dfs_s(s):
    count3 = 0
    flag3[s] = 1
    dist3[s] = 0
    d = 0
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag3[i]:
                continue
            count3 += 1
            flag3[i] = 1
            parent3[i] = v[0]
            dist3[i] = v[1] + 1
            q.append((i, v[1] + 1))
    return count3

dfs(0)
D = dist[n-1]

j = n-1
flag2[n-1] = 1
flag3[0] = 1
for i in range(D):
    if (D - i) >= (D+2)//2:
        flag2[j] = 1
        j = parent[j]
    else:
        flag3[j] = 1
        j = parent[j]

df = dfs_f(0)
ds = dfs_s(n-1)

if df > ds:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

INF = float('inf')
dists = [INF] * N
dists[0] = 0
visited = [0]*N
back = [None]*N
stack = [0]
while stack:
    v = stack.pop()
    visited[v] = 1
    if v == N-1:
        break
    d = dists[v]
    for to in es[v]:
        if visited[to] : continue
        dists[to] = d+1
        back[to] = v
        stack.append(to)

path = [N-1]
while back[path[-1]] is not None:
    b = back[path[-1]]
    path.append(b)
path.reverse()

f_cantgo = path[dists[-1]//2 + 1]

visited = [0]*N
visited[f_cantgo] = 1
f_can_go = 0
stack = [0]
while stack:
    v = stack.pop()
    visited[v] = 1
    f_can_go += 1
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)

s_can_go = N - f_can_go
print('Fennec' if f_can_go > s_can_go else 'Snuke')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 16:27:11 2018

@author: maezawa
"""
from collections import deque
import copy

n = int(input())
adj = [[] for _ in range(n+1)]
for i in range(n-1):
    ai, bi = list(map(int, input().split()))
    adj[ai].append(bi)
    adj[bi].append(ai)
    
#print(adj)

node = [0]*(n+1)
f = 1
s = n
node[f] = 1
node[s] = -1

stack1 = deque([f])
stack2 = deque([s])
nextstack1 = deque([])
nextstack2 = deque([])
cnt1 = 0
cnt2 = 0

turn = 1

while stack1 or stack2:
    turn += 1
    while stack1:
        f = stack1.pop()
        for m1 in adj[f]:
            if node[m1] != 0:
                continue
            else:
                node[m1] = turn
                nextstack1.append(m1)
    stack1 = copy.deepcopy(nextstack1)
    nextstack1 = deque([])

    while stack2:
        s = stack2.pop()
        for m2 in adj[s]:
            if node[m2] != 0:
                continue
            else:
                node[m2] = -turn
                nextstack2.append(m2)
    stack2 = copy.deepcopy(nextstack2)
    nextstack2 = deque([])

cnt = 0
for i in node:
    if i>0:
        cnt += 1
    elif i<0:
        cnt -= 1
if cnt > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush

input = sys.stdin.readline

N = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]


g = Graph()
for _ in range(N - 1):
    a, b = map(int, input().split())
    g.add_edge(a - 1, b - 1)
    g.add_edge(b - 1, a - 1)

d1 = Dijkstra(g, 0)
d2 = Dijkstra(g, N - 1)

cnt1, cnt2 = 0, 0
for i in range(1, N - 1):
    x = d1.shortest_distance(i)
    y = d2.shortest_distance(i)
    if x <= y:
        cnt1 += 1
    else:
        cnt2 += 1

if cnt1 > cnt2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
INF = 10**6
n = int(input())
path = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [b]
    else:
        path[a].append(b)
    if not b in path.keys():
        path[b] = [a]
    else:
        path[b].append(a)
# print(path)

dist_f = [INF]*(n+1)
dist_f[1] = 0
que_f = deque([1])
while len(que_f) > 0:
    st_f = que_f.popleft()
    for en_f in path[st_f]:
        if dist_f[en_f] == INF:
            dist_f[en_f] = dist_f[st_f]+1
            que_f.append(en_f)

dist_s = [INF]*(n+1)
dist_s[n] = 0
que_s = deque([n])
while len(que_s) > 0:
    st_s = que_s.popleft()
    for en_s in path[st_s]:
        if dist_s[en_s] == INF:
            dist_s[en_s] = dist_s[st_s]+1
            que_s.append(en_s)
# print(dist_f, dist_s)

count_f, count_s = 0, 0
for d_f, d_s in zip(dist_f[1:], dist_s[1:]):
    if d_f <= d_s:
        count_f += 1
    else:
        count_s += 1
if count_f > count_s:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None

F_MODE = 1
S_MODE = 2

N = None
D = None
D_from_1, D_from_N = [], []


def dfs(v, prev, depth, mode):
    global D_from_1
    global D_from_N

    for next in D[v]:
        if next != prev:
            if mode == F_MODE:
                D_from_1[next] = depth
            else:
                D_from_N[next] = depth

            dfs(next, v, depth + 1, mode)


def main():
    global D
    global N
    global D_from_1
    global D_from_N

    N = int(input())
    D = [[] for _ in range(N + 1)]

    for i in range(N - 1):
        a, b = li_input()
        D[a].append(b)
        D[b].append(a)

    D_from_1 = [-1] * (N + 1)
    D_from_1[1] = 0
    D_from_N = [-1] * (N + 1)
    D_from_N[N] = 0

    dfs(1, -1, 1, F_MODE)
    dfs(N, -1, 1, S_MODE)

    fennec, snuke = 0, 0

    for i in range(1, N + 1):
        if D_from_1[i] <= D_from_N[i]:
            fennec += 1
        else:
            snuke += 1

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


main()

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
N = int( input())
Path = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    Path[a].append(b)
    Path[b].append(a)
Mass = [-1 for _ in range(N)]
F = deque([0])
S = deque([N-1])
while len(F) != 0 or len(S) != 0:
    KF = deque([])
    while len(F) != 0:
        f = F.pop()
        for x in Path[f]:
            if Mass[x] == -1:
                Mass[x] = 1
                KF.append(x)
    F = deepcopy(KF)
    KS = deque([])
    while len(S) != 0:
        s = S.pop()
        for y in Path[s]:
            if Mass[y] == -1:
                Mass[y] = 0
                KS.append(y)
    S = deepcopy(KS)
if sum(Mass) >= N//2+1:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
n = int(input())

edge = [[] for i in range(n)]

for i in range(n-1):
    f,t = map(int,raw_input().split())
    f -= 1
    t -= 1

    edge[f].append(t)
    edge[t].append(f)

inf = float("inf")
dist1 = [inf for i in range(n)]

dist1[0] = 0
stk = []
for i in edge[0]:
    stk.append([i,1])

while stk:
    t,c = stk.pop()
    if dist1[t] == inf :
        dist1[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

dist2 = [inf for i in range(n)]
dist2[n-1] = 0
for i in edge[n-1]:
    stk.append([i,1])
while stk:
    t,c = stk.pop()
    if dist2[t] == inf :
        dist2[t] = c
        for i in edge[t]:
            stk.append([i,c+1])

fennec = 0
snuke = 0

for i in range(n):
    if dist1[i] <= dist2[i]:
        fennec += 1
    else :
        snuke += 1


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

Submission status: Accepted

Solution code:
#import queue
import heapq
inf = float('inf')
N = int(input())
paths = [{} for i in range(N+1)]
for i in range(N-1):
    s,t = list(map(int, input().split()))
    paths[s][t] = 1
    paths[t][s] = 1

def dijkstra(start, nodes, N):
    cost = [inf] * (N + 1)
    cost[start] = 0
    q = []
    heapq.heappush(q, (0, start))
#    q.put((0, start))
    while q: #q.empty() == False:
        w, x = heapq.heappop(q)
        if cost[x] < w: continue
        for y in nodes[x]:
            if cost[x] + paths[x][y] < cost[y]:
                cost[y] = cost[x] + paths[x][y]
#                q.put((cost[y], y))
                heapq.heappush(q, (cost[y], y))
    return cost

# それぞれの位置からの到達コストを調べている
score_f = dijkstra(1, paths, N)
score_s = dijkstra(N, paths, N)

score = 0
for i in range(1, N+1):
    if score_f[i] > score_s[i]:
        score -= 1
    else:
        score += 1

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

Submission status: Accepted

Solution code:
import queue
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
q=queue.Queue()
P=[-1 for i in range(N)]
dist=[-1 for i in range(N)]
q.put(0)
#print(G)
dist[0]=0
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if dist[p]==-1:
            q.put(p)
            dist[p]=dist[r]+1
            P[p]=r
#print(dist)
S=dist[-1]
#print(P)
L=[];k=N-1
while(k!=-1):
    L.append(k)
    k=P[k]
#fennec:1
#snuke:-1
c=[0 for i in range(N)]
for p in L:
    snuke=dist[p]
    fennec=S-dist[p]
    if fennec>=snuke:
        c[p]=1
    else:
        c[p]=-1
#print(c)
q=queue.Queue()
q.put(0)
reached=[0 for i in range(N)]
reached[0]=1
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if reached[p]==0:
            if c[p]!=-1:
                q.put(p)
                c[p]=1
                reached[p]=1
for i in range(N):
    if c[i]==0:
        c[i]=-1
if sum(c)>0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
N = int(input())

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

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

c_f = dijkstra(adj, N, 1)
c_s = dijkstra(adj, N, N)

score = 0
for i in range(1, N + 1):
    if c_f[i] > c_s[i]:
        score -= 1
    else:
        score += 1

print("Fennec" if score > 0 else "Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

N = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

g = Graph()
for _ in range(N - 1):
    a, b = map(int, input().split())
    g.add_edge(a - 1, b - 1)
    g.add_edge(b - 1, a - 1)

d1 = Dijkstra(g, 0)
d2 = Dijkstra(g, N - 1)
c1, c2 = 0, 0
for i in range(N):
    if d1.shortest_distance(i) <= d2.shortest_distance(i):
        c1 += 1
    else:
        c2 += 1

if c1 > c2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
  a, b = map(int, input().split())
  T[a - 1].append(b - 1)
  T[b - 1].append(a - 1)
def dijkstra(N, s0):
  D = [N] * N
  D[s0] = 0
  Q = [N] * N
  Q[0] = s0
  tail = 1
  for i in range(N):
    s = Q[i]
    for adj in T[s]:
      if D[s] + 1 < D[adj]:
        D[adj] = D[s] + 1
        Q[tail] = adj
        tail += 1
  return D
D1 = dijkstra(N, 0)
D2 = dijkstra(N, N - 1)
score = 0
for i in range(N):
  score += 1 if D1[i] <= D2[i] else -1
print('Fennec' if score > 0 else 'Snuke')