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

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

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


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

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

#print(graph)

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

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

Submission status: Accepted

Solution code:

from collections import deque

def bfs(s, dist):
    visited = [False] * (N+1)
    q = [(s, 1)]
    visited[s] = True

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


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

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

bfs(1, dist[0])
bfs(N, dist[1])

b = w = 0
for i in range(2, N):
    if dist[0][i] <= dist[1][i]:
        b += 1
    else:
        w += 1
if b <= w:
    print('Snuke')
else:
    print('Fennec')

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s, dist):
    visited = [False] * (N+1)
    q = [(s, 1)]
    visited[s] = True

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

def main():
    dist = [[0] * (N+1) for i in range(2)]
    
    for i in range(N-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    bfs(1, dist[0])
    bfs(N, dist[1])
    
    b = w = 0
    for i in range(2, N):
        if dist[0][i] <= dist[1][i]:
            b += 1
        else:
            w += 1
    if b <= w:
        print('Snuke')
    else:
        print('Fennec')

if __name__ == '__main__':
    N = int(input())
    graph = [deque() for i in range(N+1)]

    dist = [[0] * (N+1) for i in range(2)]
    
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import copy
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
point = [[] for _ in range(n+1)]
for l in ab:
  point[l[0]].append(l[1])
  point[l[1]].append(l[0])
adone = set()
bdone = set()
adone.add(1)
bdone.add(n)
da,db = [0]*(n+1),[0]*(n+1)
alist = [1]
blist = [n]
anext,bnext = [],[]
c = 0
while alist:
  c += 1
  for i in alist:
    for j in point[i]:
      if j not in adone:
        adone.add(j)
        anext.append(j)
        da[j] = c
  alist = copy.deepcopy(anext)
  anext = []
c = 0
while blist:
  c += 1
  for i in blist:
    for j in point[i]:
      if j not in bdone:
        bdone.add(j)
        bnext.append(j)
        db[j] = c
  blist = copy.deepcopy(bnext)
  bnext = []
a,b = 0,0
for i in range(1,n+1):
  if da[i] <= db[i]:
    a += 1
  else:
    b += 1
if a > b:
  print("Fennec")
else:
  print("Snuke")

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

from collections import deque
f = deque()
s = deque()
 
f.append(0)
s.append(n-1)
 
f_visit = [-1]*n
s_visit = [-1]*n
f_visit[0] = 0
s_visit[n-1] = 0

def bfs(queue, visit):
  x = queue.popleft()
  for new_x in g[x]:
    if visit[new_x] == -1:
      visit[new_x] = visit[x]+1
      queue.append(new_x)
    else:
      continue

while f:
  bfs(f, f_visit)

while s:
  bfs(s, s_visit)

fp = 0
sp = 0
for i in range(n):
  if f_visit[i] <= s_visit[i]:
    fp += 1
  else:
    sp += 1
if fp <= sp:
  print('Snuke')
else:
  print('Fennec')

Submission status: Accepted

Solution code:
from heapq import *
n=int(input())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def f(a):
    p=[float("INF")for i in range(n+1)]
    p[a],q=0,[[0,a]]
    while q:
        i,j=heappop(q)
        for w in s[j]:
            if p[w]>i+1:
                p[w]=i+1
                heappush(q,[i+1,w])
    else:
        return p[1:]
s1,t1=f(1),f(n)
a,b=0,0
for i in range(n):
    if s1[i]<=t1[i]:
        a+=1
    else:
        b+=1
print("Fennec" if a>b else "Snuke")

Submission status: Accepted

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

N = int(input())

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

qa, qb = [0], [N-1]
sa, sb = 0, 0
visited = [False] * N
visited[0] = visited[N-1] = True

while qa or qb :
    qa_ = []
    while qa :
        cur = qa.pop()
        for nex in v[cur] :
            if not visited[nex] :
                visited[nex] = True
                qa_.append(nex)
                sa += 1
    qa = qa_
    
    qb_ = []
    while qb :
        cur = qb.pop()
        for nex in v[cur] :
            if not visited[nex] :
                visited[nex] = True
                qb_.append(nex)
                sb += 1
    qb = qb_
    
if sa > sb :
    print('Fennec')
else :
    print('Snuke')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict, deque
import heapq

INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.edges = defaultdict(list)
        pass

    def add_edge(self, from_, to_, weight=1):
        """必ず0インデックスで入力すること。
        """
        self.edges[from_].append([to_, weight])
        self.edges[to_].append([from_, weight])

    def remove_edge(self, from_, to_):
        for t_, w_ in self.edges[from_]:
            if t_ == to_:
                break
        self.edges[from_].remove([t_, w_])
        self.edges[t_].remove([from_, w_])


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.edges[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


class UnionFind(object):
    """UnionFind木
    """

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, a: "List[int]", b: "List[int]"):
    g = Graph(N)
    for x, y in zip(a, b):
        g.add_edge(x-1, y-1, 1)

    dist, prev = shortestPath(g, 0)

    depth = dist[N-1]
    boundary = N-1
    for _ in range((depth-1) // 2):
        boundary = prev[boundary]
    g.remove_edge(boundary, prev[boundary])
    # print(boundary, prev[boundary])

    visited = [False]*N
    countA = 0
    q = deque()
    q.append(0)
    while len(q) > 0:
        curr = q.popleft()
        visited[curr] = True
        countA += 1
        for t_, w_ in g.edges[curr]:
            if visited[t_] == False:
                q.append(t_)
    countB = N-countA
    if countA > countB:
        print("Fennec")
    else:
        print("Snuke")
    # print(countA, countB)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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)

que = deque([])
que.append((0, 0))

minDist = [float('inf') for _ in range(N)]

while que:
    now, dist = que.popleft()

    if minDist[now] <= dist:
        continue
    minDist[now] = dist

    for to in edges[now]:
        if dist + 1 < minDist[to]:
            que.append((to, dist + 1))

now = N - 1
minPath = [now]
dist = minDist[N - 1]
while dist > 0:
    for back in edges[now]:
        if minDist[back] == dist - 1:
            minPath.append(back)
            dist -= 1
            now = back
            break


edges[minPath[len(minPath) // 2]].remove(minPath[len(minPath) // 2 - 1])
edges[minPath[len(minPath) // 2 - 1]].remove(minPath[len(minPath) // 2])

confilm = [0 for _ in range(N)]
que.clear()
que.append(0)

while que:
    now = que.popleft()

    confilm[now] = 1

    for to in edges[now]:
        if confilm[to] == 0:
            que.append(to)

blackCount = sum(confilm)
witeCount = N - blackCount

if blackCount > witeCount:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import collections

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

def f(first):
    d = [-1] * n
    d[first] = 0
    stack = [first]
    while stack:
        current = stack.pop()
        for nxt in nxts[current]:
            if d[nxt] == -1:
                d[nxt] = d[current] + 1
                stack.append(nxt)
    return d

d1 = f(0)
d2 = f(n - 1)
c1 = sum(1 for x1, x2 in zip(d1, d2) if x1 <= x2)
c2 = n - c1


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

Submission status: Accepted

Solution code:
from collections import deque

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

# print(edges)

def bfs(v):
    dist = [N] * N
    dist[v] = 0
    q = deque()
    q.append(v)
    while q:
        p = q.popleft()
        d = dist[p]
        for e in edges[p]:
            if dist[e] == N:
                dist[e] = d + 1
                q.append(e)
    return dist

fennec = bfs(0)
snuke = bfs(N-1)

cnt = 0
for i in range(N):
    if fennec[i] <= snuke[i]:
        cnt += 1
if 2 * cnt > N:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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)

que = deque()
que.append((0,0))
c1 = [False]*n
dist1 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist1[v] = min(dist1[v],d)
    if not c1[v]:
        c1[v] = True
        for u in g[v]:
            que.append((d+1,u))
que = deque()
que.append((0,n-1))
c2 = [False]*n
dist2 = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist2[v] = min(dist2[v],d)
    if not c2[v]:
        c2[v] = True
        for u in g[v]:
            que.append((d+1,u))

w,b = 0,0
for i in range(n):
    if dist1[i] <= dist2[i]:
        b += 1
    else:
        w += 1
if w < b:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10**9)

def dfs(v):
  ret=0
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      ret+=1+dfs(u)
  return ret

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
q=collections.deque()
pn=[-1]*(n+1)
checked=[0]*(n+1)
checked[1]=1
q.append(1)
cnt=0
while cnt!=n-1:
  v=q.popleft()
  for u in g[v]:
    if checked[u]==0:
      cnt+=1
      checked[u]=1
      q.append(u)
      pn[u]=v
path=[n]
while 1:
  tmp=pn[path[-1]]
  if tmp==1:
    break
  path.append(tmp)
path=path[::-1]
l=len(path)
if l==1:
  fg=n
  sg=1
else:
  fg=path[l//2]
  sg=path[l//2-1]
checked=[0]*(n+1)
checked[1]=1
checked[fg]=1
ans1=dfs(1)
ans2=(n-2)-ans1
if ans1>ans2:
  print('Fennec')
else:
  print('Snuke')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())

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

def dfs(v,p,path):
    for c in g[v]:
        if c == p: continue
        if c == n-1:
            path.append(n-1)
            path.append(v)
            return True
        if dfs(c,v,path):
            path.append(v)
            return True
    return False            

path = []
dfs(0,-1,path)

from collections import deque
q = deque()
memo = [-1]*n #0 sente 1: gote
for i in path[:len(path)//2]:
    memo[i] = 1
    q.append(i)
for i in path[len(path)//2:]:
    memo[i] = 0
    q.append(i)

res = len(path)//2 #Sunuke's point

while q: #キューが空になるまで
    v = q.popleft() #キューから情報を取り出す
    for c in g[v]:
        if memo[c] != -1: continue
        #(nx,ny)が未確認のとき、確認済みにしてキューに入れる------------------
        memo[c] = memo[v]
        res += memo[c]
        q.append(c)

if n - res > res: print("Fennec")
else: print("Snuke")

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())

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

"""
def dfs(v,p,path):
    for c in g[v]:
        if c == p: continue
        if c == n-1:
            path.append(n-1)
            path.append(v)
            return True
        if dfs(c,v,path):
            path.append(v)
            return True
    return False            

path = []
dfs(0,-1,path)
path.reverse()
"""


from collections import deque

def bfs(g,root,memo):
    q = deque()
    #memo = [-1]*n: あらかじめ初期化しておく
    """初期化、キューに入れて使用済みにする"""
    memo[root] = 0
    q.append(root)
    """BFS"""
    while q: #キューが空になるまで
        v = q.popleft() #キューから情報を取り出す
        for c in g[v]:
            if memo[c] != -1: continue #確認済みならスキップ
            # 確認済みにしてキューに入れる
            memo[c] = memo[v] + 1
            q.append(c)

memo0 = [-1]*n
memo1 = [-1]*n

bfs(g,0,memo0)
bfs(g,n-1,memo1)

ans = 0
for i,j in zip(memo0,memo1):
    if i <= j: ans += 1

#print(memo0)
#print(memo1)

if ans > n - ans: print("Fennec")
else: print("Snuke")

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())

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

def dfs(v,p,path):
    for c in g[v]:
        if c == p: continue
        if c == n-1:
            path.append(n-1)
            path.append(v)
            return True
        if dfs(c,v,path):
            path.append(v)
            return True
    return False            

path = []
dfs(0,-1,path)
path.reverse()

#print(path)

from collections import deque
#0 sente 1: gote
q0 = deque()
q1 = deque()
ans = [-1]*n
for i in path[:(1+(len(path)))//2]:
    ans[i] = 0
    q0.append(i)
for i in path[(1+(len(path)))//2:]:
    ans[i] = 1
    q1.append(i)

turn = len(path)&1

while q0 and q1: #キューが空になるまで
    if turn: v = q1.popleft() #キューから情報を取り出す
    else: v = q0.popleft()
    for c in g[v]:
        if ans[c] != -1: continue
        #(nx,ny)が未確認のとき、確認済みにしてキューに入れる------------------
        ans[c] = turn
        if turn: q1.append(c)
        else: q0.append(c)
    turn ^= 1

if q0: print("Fennec")
else: print("Snuke")

Submission status: Accepted

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
g=[[] for _ in [0]*n]
[g[b-1].append(a-1) for a,b in ab]
[g[a-1].append(b-1) for a,b in ab]

dist_f=[None for _ in [0]*n]
dist_s=[None for _ in [0]*n]
dist_f[0]=0
dist_s[n-1]=0

q=[0]
while q:
    qq=q.pop()
    for i in g[qq]:
        if dist_f[i]==None:
            dist_f[i]=dist_f[qq]+1
            q.append(i)
            
q=[n-1]
while q:
    qq=q.pop()
    for i in g[qq]:
        if dist_s[i]==None:
            dist_s[i]=dist_s[qq]+1
            q.append(i)
            
cnt_f,cnt_s=0,0

for i in range(n):
    if dist_f[i]<=dist_s[i]:
        cnt_f+=1
    else:
        cnt_s+=1
if cnt_f>cnt_s:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

E = [{} for _ in [0]*N]
for a,b in AB:
    E[a-1][b-1] = 1
    E[b-1][a-1] = 1

def dist_dfs_tree(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        i = q.pop()
        ci = d[i]
        for j,cj in E[i].items():
            if d[j] !=-1:continue
            d[j] = ci+cj
            q.append(j)
    return d

D1 = dist_dfs_tree(N,E,0)
Dn = dist_dfs_tree(N,E,N-1)
d1n = D1[-1]
for i,dd in enumerate(zip(D1,Dn)):
    if dd[0] == d1n//2 and sum(dd) == d1n:break

di = Dn[i]
for j in E[i]:
    if Dn[j]==di-1:break
E[i].pop(j)
E[j].pop(i)
s1 = sum(s>=0 for s in dist_dfs_tree(N,E,0))
print("Fennec" if s1 > N//2 else "Snuke")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
from collections import deque
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)
check=[False]*n
check[0]=True
check[n-1]=True
f_q=deque([0])
s_q=deque([n-1])
f_c=1
s_c=1
while not (len(f_q)==0 and len(s_q)==0):
    f_n=len(f_q)
    for i in range(f_n):
        now=f_q.popleft()
        for j in G[now]:
            if not check[j]:
                check[j]=True
                f_c+=1
                f_q.append(j)
    s_n=len(s_q)
    for i in range(s_n):
        now=s_q.popleft()
        for j in G[now]:
            if not check[j]:
                check[j]=True
                s_c+=1
                s_q.append(j)
if f_c>s_c:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
N = int(input())
T = [[] for _ in range(N)]


def dfs(k):
    q = [k]
    d = [-1] * N
    d[k] = 0
    while len(q) > 0:
        v = q.pop()
        for i in T[v]:
            if d[i] == -1:
                d[i] = d[v] + 1
                q.append(i)
    return d


def main():
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        T[a].append(b)
        T[b].append(a)
    c = dfs(0)
    d = dfs(N - 1)
    ac = 0
    for x, y in zip(c, d):
        if y >= x:
            ac += 1
    if ac > N // 2:
        print('Fennec')
    else:
        print('Snuke')


main()

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            return True
        for i in root[x]:
            if tami(i):
                return True
        else:
            del path[-1]
    return False

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[math.ceil(len(path)/2)-1]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(N)

Snuke = cnt
Fennec = N - Snuke

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

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            return True
        for i in root[x]:
            if tami(i):
                return True
        else:
            del path[-1]
    return False

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[math.ceil(len(path)/2)-1]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(N)

Snuke = cnt
Fennec = N - Snuke

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    es[a].append(b)
    es[b].append(a)
pre = [None] * (N+1)
pre[1] = 0
dq = deque()
dq.append((0, 1))
while dq:
    d, v = dq.popleft()
    if v == N:
        break
    for u in es[v]:
        if pre[u] == None:
            pre[u] = v
            dq.append((d+1, u))
col = [None] * (N+1)
v = N
sv = [N]
for i in range(d+1):
    if i < d/2:
        col[v] = 0
    else:
        col[v] = 1
    v = pre[v]
    sv.append(v)
# print(col)
# print(pre)
# print(sv)
bc, wc = 0, 0
for s in sv:
    if s == 0:
        continue
    dq = deque()
    dq.append(s)
    c = 0
    while dq:
        v = dq.popleft()
        c += 1
        for u in es[v]:
            if col[u] == None:
                col[u] = col[s]
                dq.append(u)
    if col[s] == 1:
        bc += c
    else:
        wc += c
if bc > wc:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import copy
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x):
    global f
    if visited[x] == False:
        visited[x] = True
        path.append(x)
        if x == N:
            f = 1
        else:
            for i in root[x]:
                if f == 0:
                    tami(i)
                else:
                    break
            else:
                if f == 0:
                    del path[-1]

def nas(x):
    global cnt
    if (visited[x] == False) and (data[x] == 0):
        visited[x] = True
        cnt += 1
        for i in root[x]:
            nas(i)

N = I()
ab = [IL() for i in range(N-1)]
data = np.array([0]*(N+1))
root = [[]*(N+1) for i in range(N+1)]
visited = [False]*(N+1)

path = []
f = 0
for a,b in ab:
    root[a].append(b)
    root[b].append(a)

tami(1)
middle_No = path[math.ceil(len(path)/2)-1]
data[middle_No] = 1

visited = [False]*(N+1)
cnt = 0
nas(N)

Snuke = cnt
Fennec = N - Snuke

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

Submission status: Accepted

Solution code:
import queue

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

T = {}
for a, b in ab:
  if a not in T:
    T[a] = [b]
  else:
    T[a].append(b)
  if b not in T:
    T[b] = [a]
  else:
    T[b].append(a)

R = [-1] * (N + 1)
q = queue.Queue()
put = q.put
get = q.get
put(1)
R[1] = 1
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] == -1:
        R[i] = R[t] + 1
        put(i)

L = [N]
t = N
while t != 1:
  for i in T[t]:
    if R[i] < R[t]:
      L.append(i)
      t = i
      break

k = L[len(L) // 2 - 1]

cnt = 1
put(k)
while not q.empty(): 
  t = get()
  if t in T:
    for i in T[t]:
      if R[i] > R[t]:
        cnt += 1
        put(i)

Ans = ["Fennec", "Snuke"]
print(Ans[cnt >= N - cnt])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n = int(input())
connect_list = [[] for i in range(n)]

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

def djkstra(in_connect_list):
    out_parent_list = [-1 for i in range(n)]
    out_shortest_list = [-1 for i in range(n)]
    out_shortest_list[0] = 0
    searching_list = [0]
    
    while searching_list != []:
    
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                if out_shortest_list[j] == -1:
                    out_shortest_list[j] = 1 + out_shortest_list[i]
                    out_parent_list[j] = i
                    new_search_list.append(j)
        searching_list = new_search_list


    return out_shortest_list, out_parent_list

shortest_list, parent_list = djkstra(connect_list)

nto1_list = [n-1]
while nto1_list[-1] != 0:
    nto1_list.append(parent_list[nto1_list[-1]])
nto1_list = list(reversed(nto1_list))


shortest_length = len(nto1_list) 
if shortest_length % 2 == 0:
    p = nto1_list[(shortest_length//2)-1]
    q = nto1_list[shortest_length//2]
else:
    p = nto1_list[shortest_length//2]
    q = nto1_list[(shortest_length//2)+1]

del connect_list[p][connect_list[p].index(q)]
del connect_list[q][connect_list[q].index(p)]


shortest_list, parent_list = djkstra(connect_list)

snu, fen = shortest_list.count(-1), n - shortest_list.count(-1)
if fen > snu:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc067/submissions/1562911
#コピペコード
N = int(input())
ab = [[] for i in range(N+1)]
for i in range(N-1):              #隣接リスト作成
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
 
def calc_dist(K):
    # dist[i]:頂点Kから頂点iまでの距離
    dist = [-1 for i in range(N+1)]
    dist[K] = 0
 
    # 深さ優先探索（スタック）
    stack = []
    stack.append(K)
 
    while stack:
        v = stack.pop()
        for nxt in ab[v]:            #隣接リストから値をとっていく
            if dist[nxt] == -1:
                dist[nxt] = dist[v] + 1
                stack.append(nxt)
 
    return dist
 
dist1 = calc_dist(1)
distN = calc_dist(N)
 
Fennec = 0
Snuke = 0
for v in range(1,N+1):
    if dist1[v] <= distN[v]:     #vまで行くのにどちらが早いか
        Fennec += 1
    else:
        Snuke += 1
 
if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc067/submissions/1562911
#コピペコード
N = int(input())
ab = [[] for i in range(N+1)]
for i in range(N-1):              #隣接リスト作成
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
 
def calc_dist(K):
    # dist[i]:頂点Kから頂点iまでの距離
    dist = [-1 for i in range(N+1)]
    dist[K] = 0
 
    # 深さ優先探索（スタック）
    from collections import deque
    stack = deque()
    stack.append(K)
 
    while stack:
        v = stack.pop()
        for nxt in ab[v]:            #隣接リストから値をとっていく
            if dist[nxt] == -1:
                dist[nxt] = dist[v] + 1
                stack.append(nxt)
 
    return dist
 
dist1 = calc_dist(1)
distN = calc_dist(N)
 
Fennec = 0
Snuke = 0
for v in range(1,N+1):
    if dist1[v] <= distN[v]:     #vまで行くのにどちらが早いか
        Fennec += 1
    else:
        Snuke += 1
 
if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d:
        d[b].append(a)
    else:
        d[b]=[a]
f,s=set([1]),set([n])
e=deque([0,1])
u=deque([0,n])
x=0
while 1:
    if len(e)==len(u)==1: break

    if len(e)>0:
        while e[-1]!=0:
            tmp=e.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    f.add(i)
                    e.appendleft(i)
        e.rotate()
    if len(u)>0:
        while u[-1]!=0:
            tmp=u.pop()
            for i in d[tmp]:
                if i not in f and i not in s:
                    s.add(i)
                    u.appendleft(i)
        u.rotate()

print(["Fennec","Snuke"][len(f)<=len(s)])