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:
N=int(input())
from collections import defaultdict,deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
check={0}
bef=[-2]*N
bef[0]=-1
dist=[float('inf')]*N
dist[0]=0
while len(check)>0:
    now=check.pop()
    for nex in branch[now]:
        if bef[nex]==-2:
            bef[nex]=now
            check|={nex}
            dist[nex]=dist[now]+1
NG=set()
OK={0}
now=N-1
checked={0}
for i in range((1+dist[N-1])//2):
    NG|={now}
    now=bef[now]
checked|=NG
for i in range(N):
    if i in checked:
        continue
    else:
        visited={i}
        now=i
        while True:
            now=bef[now]
            visited|={now}
            if now in NG:
                NG|=visited
                checked|=visited
                break
            elif now in OK:
                OK|=visited
                checked|=visited
                break
if len(OK)>N//2:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

# 入力
N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)

# 頂点1, N から各蝶点への距離を求める
G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1
INF = 10**10


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp1 = dijkstra(G, 1)
dpN = dijkstra(G, N)
# 頂点Nより頂点1のほうが近い、または、頂点1と頂点Nとの距離が等しいは
# 頂点1から頂点Nの間のパスに含まれる頂点のうち、Fennecが塗れる頂点である。
ans = (
    'Fennec' if sum(dp1[i] <= dpN[i] for i in range(1, N + 1)) > N // 2 else
    'Snuke'
)

# 出力
print(ans)

Submission status: Accepted

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

# 入力
N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)

G = [set() for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x].add(y)
    G[y].add(x)


dp = [0 for _ in range(N + 1)]
dp[1] = 1


def f(i):
    for j in G[i]:
        if dp[j] == 0:
            dp[j] = i
            f(j)


f(1)
p = []
i = N
while i != 1:
    p.append(i)
    i = dp[i]
p.append(1)
dp2 = [0 for _ in range(N + 1)]
for j in range(len(p)):
    if dp2[p[-(j + 1)]] == 0:
        dp2[p[-(j + 1)]] = 1
    if dp2[p[j]] == 0:
        dp2[p[j]] = -1
dp3 = [0 for _ in range(N + 1)]
dp3[1] = 1


def g(i):
    for j in G[i]:
        if dp3[j] == 0 and dp2[j] != -1:
            dp3[j] = 1
            g(j)


g(1)
ans = (
    'Fennec' if dp3.count(1) > N // 2 else
    'Snuke'
)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N=int(input())

B=[[]for i in range(N+1)]

F=[10**10 for i in range(N+1)]
F[1]=0
S=[10**10 for i in range(N+1)]
S[N]=0

for i in range(N-1):
    a,b=map(int,input().split())
    B[a].append(b)
    B[b].append(a)
    
#print(B)
def dfsF(f):
    for i in B[f]:
        if F[i]==10**10:
            F[i]=F[f]+1
            dfsF(i)
dfsF(1)

def dfsS(s):
    for i in B[s]:
        if S[i]==10**10:
            S[i]=S[s]+1
            dfsS(i)
dfsS(N)
#print(F)
#print(S)
Fennec=0
Snuke=0
for i in range(1,N+1):
    if F[i]<=S[i]:
        Fennec+=1
    else:
        Snuke+=1
if Fennec>Snuke:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*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)
visited = [False for _ in range(N)]
fennec = [-1 for _ in range(N)]
snuke = [-1 for _ in range(N)]
def dfs(start,visited,distance,d):
    visited[start] = True
    d[start] = distance
    for term in edges[start]:
        if visited[term]:
            continue
        dfs(term,visited,distance + 1,d)
dfs(0,visited,0,fennec)

visited = [False for _ in range(N)]
    
dfs(N-1,visited,0,snuke)
F = S = 0
for i in range(N):
    if fennec[i] <= snuke[i]:
        F+=1
    else:
        S+=1
if F>S:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
d = [[-1] * N for _ in range(2)]
for i in range(2):
    d[i][i * (N - 1)] = 0
    q = deque([i * (N - 1)])
    while len(q) > 0:
        u = q.popleft()
        for v in edge[u]:
            if d[i][v] > -1:
                continue
            d[i][v] = d[i][u] + 1
            q.append(v)
S = 0
F = 0
for i in range(N):
    if d[0][i] > d[1][i]:
        S += 1
    else:
        F += 1
if F > S:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
n = int(input())
nl = {}
for _ in range(n-1):
  a, b = map(int, input().split())
  if a-1 in nl:
    nl[a-1].append(b-1)
  else:
    nl[a-1] = [b-1]
  if b-1 in nl:
    nl[b-1].append(a-1)
  else:
    nl[b-1] = [a-1]

fenl = [-1 for _ in range(n)]
sunl = [-1 for _ in range(n)]
fenl[0] = 1
sunl[-1] = 1
now = [0]
while now:
  tmp = []
  for _n in now:
    for nxt in nl[_n]:
      if fenl[nxt] == -1:
        tmp.append(nxt)
        fenl[nxt] = fenl[_n] + 1
  now = tmp

now = [n-1]
while now:
  tmp = []
  for _n in now:
    for nxt in nl[_n]:
      if sunl[nxt] == -1:
        tmp.append(nxt)
        sunl[nxt] = sunl[_n] + 1
  now = tmp

fm, sm = 0, 0
for i in range(n):
  if fenl[i] <= sunl[i]:
    fm += 1
  else:
    sm += 1

if fm <= sm:
  print('Snuke')
else:
  print('Fennec')

Submission status: Accepted

Solution code:
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)
dp = [0]*n
dp[0] =1
fp = [0]*n
fp[n-1] =1
def bfs(u):
    q = []
    q.append(u)
    while q:
        p = q.pop()
        for i in edges[p]:
            if dp[i] ==0 :
                q.append(i)
                dp[i]+=dp[p]+1
def ffs(u):
    q = []
    q.append(u)
    while q:
        p = q.pop()
        for i in edges[p]:
            if fp[i] ==0 :
                q.append(i)
                fp[i]+=fp[p]+1
bfs(0)
ffs(n-1)
c = 0
for i in range(n):
    if dp[i] <= fp[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
board = [0]*n
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
q = deque()
q.append((0,1))
q.append((-1,-1))
while q:
    from_, color = q.popleft()
    if board[from_] != 0:
        continue
    board[from_] = color
    for i in edge[from_]:
        q.append((i,color))
if sum(board) > 0:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
tree = dd(list)
def dfs_route(tree,start,goal):
    visited = set()
    stack = list()
    visited.add(start)
    stack.append(start)
    while stack:
        node = stack[-1]
        if node == goal:
            return stack
        else:
            child = [x for x in tree[node] if x not in visited]
            if child == []:
                stack.pop()
            else:
                visited.add(child[0])
                stack.append(child[0])
n = int(input())
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
l = dfs_route(tree,1,n)
fl = l[(len(l)-1)//2]
sl = l[(len(l)+1)//2]
tree[fl].remove(sl)
tree[sl].remove(fl)
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
if len(gr(tree,1))*2 > n:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N = int(input())
L = [[] for i in range(N + 1)]
Fd = [float("inf") for i in range(N + 1)]
Sd = [float("inf") for i in range(N + 1)]
Fd[1] = 0
Sd[N] = 0

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

Q = []
heappush(Q, 1)
while Q:
    n = heappop(Q)
    d = Fd[n]
    for x in L[n]:
        if Fd[x] == float("inf"):
            Fd[x] = d + 1
            heappush(Q, x)

Q = []
heappush(Q, N)
while Q:
    n = heappop(Q)
    d = Sd[n]
    for x in L[n]:
        if Sd[x] == float("inf"):
            Sd[x] = d + 1
            heappush(Q, x)

f = 0
s = 0
for i in range(1, N + 1):
    if Fd[i] <= Sd[i]:
        f += 1
    else:
        s += 1

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

Submission status: Accepted

Solution code:
from scipy.sparse import*
n,*a=map(int,open(0).read().split())
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix(([1]*~-n,(a[::2],a[1::2])),[n+1]*2),0,[1,n])))*2>=n::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*
n,*a=map(int,open(0).read().split())
c=[1]*~-n
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix((c,(a[::2],a[1::2])),[n+1]*2),0,[1,n])))*2>=n::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=lambda*z:map(int,input().split())
n,=f()
c=[1]*~-n
print('FSennunkeec'[sum(g>h for g,h in zip(*csgraph.dijkstra(csr_matrix((c,list(zip(*map(f,c)))),[n+1]*2),0,[1,n])))*2>=n::2])

Submission status: Accepted

Solution code:
from collections import*
input=open(0).readline
n=int(input())
e=[[]for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
f=[0]*n
v=[1]+[0]*~-n
q=deque([(0,0)])
while q:
    t,c=q.pop()
    v[t]=1
    f[t]=c
    for i in e[t]:
        if not v[i]:
            q.append((i,c+1))
s=[0]*n
v=[0]*~-n+[1]
q=deque([(n-1,0)])
while q:
    t,c=q.pop()
    v[t]=1
    s[t]=c
    for i in e[t]:
        if not v[i]:
            q.append((i,c+1))
a=b=0
for i,j in zip(f,s):
    if i<=j:
        a+=1
    else:
        b+=1
if a>b:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
N=int(input())

import sys
sys.setrecursionlimit(10**5)
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]

#print(ab)
for a,b in ab :
  con[a].append(b)
  con[b].append(a)

#black Fennec
pc=[0]*(N+1)
q=[(1,0)]
vis=[False]*(N+1)
vis[1]=True
Fcnt=N
while q:
  n,c=q.pop()
  pc[n]=c
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
q=[(N,0)]
vis=[False]*(N+1)
vis[N]=True
while q:
  n,c=q.pop()
  if pc[n]>c:
    Fcnt-=1
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
if Fcnt>N-Fcnt:
  print("Fennec")
else:
  print("Snuke")

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

import sys


class UnionFind:
    '''
    配列を用いたUnionFind
    '''

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        '''
        xのグループ番号を返す
        '''
        return self.table[x]

    def union(self, val, y):
        '''
        Fennecは0
         SnukeはN-1とすることで、O(1)にする
         '''
        self.table[y] = val

    def same(self, x, y):
        '''
        xとyが同じグループならtrue
        '''
        x1 = self.find(x)
        y1 = self.find(y)
        return x1 == y1

    def get_table(self):
        return self.table
# python template for atcoder1


sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

Un = UnionFind(N)
S = [N-1]
F = [0]
S_or = N-1
F_or = 0


def oneStep(turn):
    ret = []
    if turn == 1:
        while S:
            c = S.pop(0)
            for i in adj[c]:
                if not Un.same(S_or, i) and not Un.same(F_or, i):
                    Un.union(S_or, i)
                    ret.append(i)
    else:
        while F:
            c = F.pop(0)
            for i in adj[c]:
                if not Un.same(S_or, i) and not Un.same(F_or, i):
                    Un.union(F_or, i)
                    ret.append(i)
    return ret


turn = 0
while S or F:
    if turn == 1:
        if len(S) != 0:
            S = oneStep(turn)
        turn = 0
    else:
        if len(F) != 0:
            F = oneStep(turn)
        turn = 1

cntF = Un.get_table().count(0)
cntS = Un.get_table().count(N-1)
if cntF > cntS:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

prev = [-1]*N
def DFS(start):
    res = 0
    for u in G[start]:
        if u != prev[start]:
            prev[u] = start
            res += DFS(u)
    return res+1

DFS(0)
start = N-1
path = [N-1]
while True:
    path.append(prev[start])
    start = prev[start]
    if start == 0:
        break
path.reverse()
num = len(path)
c, d = (path[(num+1)//2-1], path[(num+1)//2])
G[c].remove(d)
G[d].remove(c)
prev = [-1]*N
DFS0 = DFS(0)
prev = [-1]*N
if DFS0 > DFS(N-1):
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

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

for _ in range(N-1):
    go,to = map(int,input().split())
    go -= 1
    to -= 1
    edge[go].append(to)
    edge[to].append(go)
    
from collections import deque
que = deque(maxlen=N)
que.append([0,0])
dist0 = [None]*N
distn = [None]*N
while(que):
    v = que.popleft()
    c = v[0]
    d = v[1]
    for i in edge[c]:
        if dist0[i] is None:
            dist0[i] = d + 1
            que.append([i,d+1])
que.append([N-1,0])
while(que):
    v = que.popleft()
    c = v[0]
    d = v[1]
    for i in edge[c]:
        if distn[i] is None:
            distn[i] = d + 1
            que.append([i,d+1])
w = b = 0
for d1,dn in zip(dist0,distn):
    if d1<=dn:
        b += 1
    else:
        w += 1
print('Fennec' if b-w > 0 else 'Snuke')

Submission status: Accepted

Solution code:
import heapq
N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
G = {}
for a, b in AB:
    a -= 1
    b -= 1
    #0-indexed
    G[a] = G.get(a, set())
    G[b] = G.get(b, set())
    G[a].add(b)
    G[b].add(a)


def dijkstra_stack(i):
    D = [-1] * N
    D[i] = 0
    stack = [i]
    while True:
        i = stack.pop(0)
        update = False
        for j in G[i]:
            if D[j] == -1:
                update = True
                D[j] = D[i] + 1
                stack += [j]
        if not stack:
            break
    return D


D_Fennec = dijkstra_stack(0)
D_Snuke = dijkstra_stack(N - 1)

f = 0
s = 0
for i in range(N):
    if D_Fennec[i] <= D_Snuke[i]:
        f += 1
    else:
        s += 1
if f > s:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
def bfs(graph,start,n,check):
    if check == False:
        arrival = [0 for i in range(n+1)]
    else:
        arrival = [0 for i in range(n+1)]
        arrival[check] = -1
    q = [start]
    arrival[start] = 1
    while len(q) != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == 0:
                q.append(graph[q[0]][i])
                arrival[graph[q[0]][i]] = arrival[q[0]]+1
        q.pop(0)
    return arrival

n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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


fstart = bfs(graph,1,n,False)
sstart = bfs(graph,n,n,False)
fennec = 0
snuke = 0
for i in range(1,n+1):
    if abs(fstart[i]-fstart[1]) <= abs(sstart[i]-sstart[n]):
        fennec += 1
    else:
        snuke += 1


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

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,input().split());n,=f();c=[1]*~-n;g,h=csgraph.dijkstra(csr_matrix((c,list(zip(*map(f,c)))),[n+1]*2),0,[1,n]);print('FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,input().split());n,=f();g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,list(zip(*map(f,[0]*~-n)))),[n+1]*2),0,[1,n]);print('FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,[1,n]);print('FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());n,=f();a,b=zip(*map(f,[0]*~-n));g,h=csgraph.dijkstra(csr_matrix(([1]*~-n,(a,b)),[n+1]*2),0,[1,n]);print'FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2]

Submission status: Accepted

Solution code:
import sys

def main():
    sys.setrecursionlimit(1000000) # recursion limit hack
    buf = input()
    N = int(buf)
    a = []
    b = []
    for i in range(N-1):
        buf = input()
        buflist = buf.split()
        a.append(int(buflist[0]) - 1)
        b.append(int(buflist[1]) - 1)
    graph = []
    for i in range(N):
        graph.append([])
    for i in range(N-1):
        graph[a[i]].append(b[i])
        graph[b[i]].append(a[i])
    path = find_path(graph, 0, N-1, [])
    split_point = (len(path) + 1) // 2
    fennec_base = path[0:split_point]
    snuke_base = path[split_point:len(path)]
    fennec_vertex_count = len(fennec_base)
    snuke_vertex_count = len(snuke_base)
    for i, v in enumerate(fennec_base):
        for j in graph[v]:
            if i != 0:
                if j == fennec_base[i-1]:
                    continue
            if i != len(fennec_base) - 1:
                if j == fennec_base[i+1]:
                    continue
            else:
                if j == snuke_base[0]:
                    continue
            fennec_vertex_count += get_vertex_count(graph, v, j)
    for i, v in enumerate(snuke_base):
        for j in graph[v]:
            if i != 0:
                if j == snuke_base[i-1]:
                    continue
            else:
                if j == fennec_base[-1]:
                    continue
            if i != len(snuke_base) - 1:
                if j == snuke_base[i+1]:
                    continue
            snuke_vertex_count += get_vertex_count(graph, v, j)
    if fennec_vertex_count > snuke_vertex_count:
        print("Fennec")
    else:
        print("Snuke")

def find_path(graph, current, target, path):
    path.append(current)
    if current == target:
        return path
    for i in graph[current]:
        if len(path) >= 2:
            if i == path[-2]:
                continue
        result = find_path(graph, i, target, path)
        if result:
            return path
    path.pop()
    return None

def get_vertex_count(graph, base, next):
    count = 1
    for i in graph[next]:
        if i == base:
            continue
        count += get_vertex_count(graph, next, i)
    return count

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b = inpl()
    path[a].append(b)
    path[b].append(a)

inf = float('inf')
ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
ctr = 1
now = {N}
distS = [inf for _ in range(N+1)]
distS[N] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distS[nb] > distS[na] + 1:  
                distS[nb] = distS[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
ctr = 0
for i in range(1,N+1):
    if distF[i] <=  distS[i]:
        ctr += 1
if 2*ctr > N:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b = inpl()
    path[a].append(b)
    path[b].append(a)

inf = float('inf')
ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
ctr = 1
now = {N}
distS = [inf for _ in range(N+1)]
distS[N] = 0
while True:
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distS[nb] > distS[na] + 1:  
                distS[nb] = distS[na] + 1
                now.add(nb)
                ctr += 1
    if ctr >=  N:
        break
D = distF[N]
for i in range(1,N+1):
    if distF[i] == D//2 and distF[i]+distS[i] == D:
        St = i
    if distF[i] == D//2 + 1 and distF[i]+distS[i] == D:
        En = i
path[St].remove(En)
path[En].remove(St)

ctr = 1
now = {1}
distF = [inf for _ in range(N+1)]
distF[1] = 0
ctr1 = 0
while ctr1 != ctr:
    ctr1 = ctr
    for na in now.copy():
        na = now.pop()
        for nb in path[na]:
            if distF[nb] > distF[na] + 1:  
                distF[nb] = distF[na] + 1
                now.add(nb)
                ctr += 1
if 2*ctr > N:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
n = int(input())
edge = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

inf = 10**6


fvisited = [inf for _ in range(n+1)]
fvisited[1] = 0
q = deque([1])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if fvisited[e]==inf:
            fvisited[e] = fvisited[s]+1
            q.append(e)

svisited = [inf for _ in range(n+1)]
svisited[n] = 0
q = deque([n])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if svisited[e]==inf:
            svisited[e] = svisited[s]+1
            q.append(e)

# print(fvisited)
# print(svisited)
fcnt = 0
scnt = 0
for i in range(1,n+1):
    if fvisited[i]<=svisited[i]:
        fcnt += 1
    else:
        scnt += 1

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

Submission status: Accepted

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

def dfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
    return d

ans=0
for i,j in zip(dfs(0),dfs(n-1)):
    if i<=j:ans+=1
if ans<=n/2:print('Snuke')
else:print('Fennec')

Submission status: Accepted

Solution code:
def dfs(x):
    d = [-1] * (N + 1)
    stack = [x]
    while stack:
        x = stack.pop()
        for i in G[x]:
            if d[i] == -1:
                d[i] = d[x] + 1
                stack.append(i)
    return d

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

d1, dn = dfs(1), dfs(N)
num = 0
for i in range(1, N + 1):
    if d1[i] <= dn[i]:
        num += 1
if num > N // 2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())

path = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = ai_()
    path[a].append(b)
    path[b].append(a)

from collections import deque
q = deque()
q.append(0)

d1 = [float('inf') for _ in range(n)]
d1[0] = 0
w = set()
while q:
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            d1[vv] = d1[v] + 1
            q.append(vv)


q = deque()
q.append(n-1)

dn = [float('inf') for _ in range(n)]
dn[n-1] = 0
w = set()
while q:
    v = q.popleft()
    w.add(v)
    for vv in path[v]:
        if vv not in w:
            dn[vv] = dn[v] + 1
            q.append(vv)


d = [1 if d1[v] <= dn[v] else -1 for v in range(n)]

if sum(d) > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1 << 30)

N = read()
edges = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = reads()
  a, b = a-1, b-1
  edges[a].append(b)
  edges[b].append(a)

def dist(u, d):
  for v in edges[u]:
    if d[v] >= 0:
      continue
    d[v] = d[u] + 1
    dist(v, d)
  return d

distf = dist(0, [0]+[-1]*(N-1))
dists = dist(N-1, [-1]*(N-1)+[0])

numf = sum(distf[i] <= dists[i] for i in range(N))
nums = N - numf

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        visited.append(label)

        for v in d[label]:
            if tekazu[v] == float("inf"):
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

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

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

tekazu = [float("inf") for _ in range(n)]
tekazu[0] = 0
bfs(0)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)]
tekazu[-1] = 0
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label not in visited:
        visited.append(label)

        for v in d[label]:
            if tekazu[v] == float("inf"):
                tekazu[v] = tekazu[label] + 1
                queue.appendleft(v)

    return

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

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

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[0] = 0
bfs(0)
tekazu_Fennec = tekazu

tekazu = [float("inf") for _ in range(n)] # nは頂点数
tekazu[-1] = 0
bfs(n - 1)
tekazu_Snuke = tekazu

Fennec = 0
Snuke = 0

for i in range(n):
    if tekazu_Fennec[i] <= tekazu_Snuke[i]:
        Fennec += 1
    else:
        Snuke += 1

#print(tekazu_Fennec, tekazu_Snuke)

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

Submission status: Accepted

Solution code:
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)
 
def bfs(v):
    q = []
    depth = [n]*n
    q.append(v)
    depth[v] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth
 
d1 = bfs(0)
d2 = bfs(n-1)
 
c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)
n = int(input())
p = []
for i in range(n-1):
    p.append(list(map(int, input().split()))+ [1])
l = [[] for i in range(n+1)]
for pi in p: 
    l[pi[0]].append([pi[0],pi[1]])
    l[pi[1]].append([pi[1],pi[0]])
kyo = [float("inf")]*(n+1)
kyo[1] = 0
memo = [0] * (n+1)
memo[1] = 1
ruto = []
def dfs(start,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    if memo[a[1]] == 1:
      continue
    kyo[a[1]] = kyo[a[0]] + 1
    dfs(a[1],ruto)
  return
dfs(1,ruto)

nkyo = [float("inf")]*(n+1)
nkyo[n] = 0
memo = [0] * (n+1)
memo[n] = 1
ruto = []
def dfs(start,ruto):
  ruto.extend(l[start])
  memo[start] = 1
  while ruto:
    a = ruto.pop()
    if memo[a[1]] == 1:
      continue
    nkyo[a[1]] = nkyo[a[0]] + 1
    dfs(a[1],ruto)
  return
dfs(n,ruto)
iti = 0
nko = 0
for i in range(1,n+1):
  if kyo[i] <= nkyo[i]:
    iti += 1
  else:
    nko += 1
if iti <= nko:
  print("Snuke")
else:
  print("Fennec")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

INF = 100001
G = [[] for i in range(N)]
dist1, dist2 = [INF for j in range(N)], [INF for k in range(N)]


def bfs(s, d):
    check, q = [0 for i in range(N)], deque()
    check[s], d[s] = 1, 0
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for i in G[u]:
            if check[i] == 0:
                check[i], d[i] = 1, d[u] + 1
                q.append(i)
        check[u] = 2


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

    bfs(0, dist1)
    bfs(N-1, dist2)

    cnt_f = 0
    for i in range(N):
        if dist1[i] <= dist2[i]:
            cnt_f += 1

    if N // 2 < cnt_f:
        print("Fennec")
    else:
        print("Snuke")


if __name__ == '__main__':
    main()