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())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

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


def dfs(s):
    d = [-1] * n
    p = [-1] * n
    d[s] = 0
    stack = [s]
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                stack.append(v)

    return d, p


depth, par = dfs(0)
rev = (depth[n-1] - 1) // 2
root = n - 1
for _ in range(rev):
    root = par[root]

p = par[root]
adj[p].remove(root)
adj[root].remove(p)

depth, _ = dfs(n-1)
snuke = len([e for e in depth if e != -1])
fennec = n - snuke
if fennec > snuke:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def BFS_que_tree_2(list_tree,start1,start2,visited):
    visited[start1] = 1
    visited[start2] = -1
    q = deque([[start1,1],[start2,-1]])
    while q:
        start,color  = q.popleft()
        bfs_1step(list_tree,start,visited,q,tag=color)


def bfs_1step(list_tree,start,visited,q,tag=1):
    for node in list_tree[start]:  
        if visited[node] != 0:
            continue
        else:
            visited[node] = tag
            q.append([node,tag])
    return


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

visited = [0]*n
BFS_que_tree_2(tr,0,n-1,visited)
print("Fennec" if sum(visited) > 0 else "Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict,Counter
import queue

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

q1=queue.Queue()
qN=queue.Queue()

dist=[None for i in range(N)]
dist[0]=1
dist[N-1]=-1

phase=1
for i in ab[1]:
    q1.put((i,phase))
for g in ab[N]:
    qN.put((g,phase))

while not (q1.empty() and qN.empty()):
    while True:
        if q1.empty():
            break
        next1,p=q1.queue[0]
        if p==phase:
            if dist[next1-1]==None:
                dist[next1-1]=1
            next1,p=q1.get()
            for i in ab[next1]:
                if dist[i-1]==None:
                    q1.put((i,phase+1))
        else:
            break


    while True:
        if qN.empty():
            break
        nextN,p=qN.queue[0]
        if p==phase:
            if dist[nextN-1]==None:
                dist[nextN-1]=-1
            nextN,p=qN.get()
            for i in ab[nextN]:
                if dist[i-1]==None:
                    qN.put((i,phase+1))
        else:
            break
    phase+=1

c=Counter(dist)
if c[-1]<c[1]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
from collections import defaultdict,Counter
import queue

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

q1=queue.Queue()
qN=queue.Queue()

dist=[None for i in range(N)]
dist[0]=1
dist[N-1]=-1

phase=1
F=0
S=0
for i in ab[1]:
    q1.put((i,phase))
    F+=1
for g in ab[N]:
    qN.put((g,phase))
    S+=1

while not (q1.empty() and qN.empty()):
    while True:
        if q1.empty():
            break
        next1,p=q1.queue[0]
        if p==phase:
            if dist[next1-1]==None:
                F+=1
                dist[next1-1]=1
            next1,p=q1.get()
            for i in ab[next1]:
                if dist[i-1]==None:
                    q1.put((i,phase+1))
        else:
            break


    while True:
        if qN.empty():
            break
        nextN,p=qN.queue[0]
        if p==phase:
            if dist[nextN-1]==None:
                S+=1
                dist[nextN-1]=-1
            nextN,p=qN.get()
            for i in ab[nextN]:
                if dist[i-1]==None:
                    qN.put((i,phase+1))
        else:
            break
    phase+=1

c=Counter(dist)
if c[-1]<c[1]:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
n=int(input())
edges=[[] for _ in range(n)]
dist=[0]*n
for i in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  edges[u].append(v)
  edges[v].append(u)
dist=[ [0]*n for _ in range(2)]
#do a dfs
def dfs(u,p,idd):#u=curr , p=par
  for nei in edges[u]:
    if nei==p:
      continue
    dist[idd][nei]=1+dist[idd][u]
    dfs(nei,u,idd)
dist[0][0]=0
dfs(0,0,0)
dist[1][n-1]=0
dfs(n-1,n-1,1)
cnt_f=cnt_s=0
for i in range(n):
  if dist[0][i]<=dist[1][i]:
    cnt_f+=1
  else:
    cnt_s+=1
print("Fennec") if cnt_f>cnt_s else print("Snuke")

Submission status: Accepted

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

steps = [-99 for _ in range(N)]
steps[0] = 0
isVisited = [False for _ in range(N)]
toSearch = deque([0, ])
isVisited[0] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    nowStep = steps[nowP]
    if nowP == N-1:
        break
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
            steps[nextP] = nowStep + 1

fennecLength = ((nowStep-1)+1)//2

snukePoint = 0
isVisited = [False for _ in range(N)]
toSearch = deque([N-1, ])
isVisited[N-1] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    snukePoint += 1
    nowStep = steps[nowP]
    # To FIX break condition
    if nowStep == fennecLength:
        snukePoint -= 1
        continue
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
if snukePoint >= (N+1)//2:
    print("Snuke")
else:
    print("Fennec")
#print(snukePoint)
#print(steps)

Submission status: Accepted

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


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


dq = deque([(0, 'b'), (N-1, 'w')])

colors = [0] * N
colors[0] = 'b'
colors[-1] = 'w'


while dq:
    node, color = dq.popleft()
    for dest in adj[node]:
        if colors[dest] != 0:
            continue
        else:
            colors[dest] = color
            dq.append((dest, color))

print('Fennec' if colors.count('b') > N//2 else 'Snuke')

Submission status: Accepted

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


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


dq = deque([(0, 1), (N-1, 2)])

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


while dq:
    node, color = dq.popleft()
    for dest in adj[node]:
        if colors[dest] != 0:
            continue
        else:
            colors[dest] = color
            dq.append((dest, color))

print('Fennec' if colors.count(1) > N//2 else 'Snuke')

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    dL=[[0,0] for _ in range(N)]
    
    q=queue.Queue()
    
    #0,N-1からの距離
    for j in range(2):
        if j==0:
            q.put((0,0,0))#v,pare,d
        else:
            q.put((N-1,N-1,0))#v,pare,d
        while not q.empty():
            v,p,d=q.get()
            dL[v][j]=d
            for i in range(len(adj[v])):
                nv=adj[v][i]
                if nv!=p:
                    q.put((nv,v,d+1))
                    
    s=0
    for i in range(N):
        if dL[i][0]>dL[i][1]:
            s+=1
    
        
    
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    bit=[-1]*N#未確認,F,S    
    bit[0]=0
    bit[-1]=1
    pL=[0]*N
    dS=0
    
    q=queue.Queue()
    q.put((0,0,0))#v.pare,depth
    
    #深さを調べる
    while not q.empty():
        v,p,d=q.get()
        pL[v]=p
        if v==N-1:
            dS=d
            break
        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v,d+1))
    
    #主要なところを塗る            
    v=N-1            
    for _ in range((dS-1)//2):
        v=pL[v]
        bit[v]=1
        
    q2=queue.Queue()
    q2.put((0,0))#v.pare
    while not q2.empty():
        v,p=q2.get()
        if bit[v]==-1:
            bit[v]=bit[p]

        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q2.put((nv,v))
        
        
                    
    s=sum(bit)#sunukeが塗れる
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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)

# BFS
def dist_from_X(X:int):
    dist = np.full(N, -1)
    que = deque([X])
    dist[X] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for e in E[v]:
            if dist[e] > -1:
                continue
            dist[e] = d + 1
            que.append(e)
    return dist

Fennec = dist_from_X(0)
Sunuke = dist_from_X(N-1)

cnt = np.count_nonzero(Fennec <= Sunuke)

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

Submission status: Accepted

Solution code:
from collections import deque

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

deque = deque()
deque.append(1)

Visited_one = [-1 for _ in range(n+1)]
Visited_one[1] = 0

while deque:
    node = deque.popleft()
    next_nodes = Tree_dict[node]
    for next_node in next_nodes:
        if Visited_one[next_node] != -1:
            continue
        else:
            Visited_one[next_node] = Visited_one[node] + 1
            deque.append(next_node)


deque.append(n)

Visited_n = [-1 for _ in range(n+1)]
Visited_n[n] = 0

while deque:
    node = deque.popleft()
    next_nodes = Tree_dict[node]
    for next_node in next_nodes:
        if Visited_n[next_node] != -1:
            continue
        else:
            Visited_n[next_node] = Visited_n[node] + 1
            deque.append(next_node)

# print(Visited_one)
# print(Visited_n)

fen = 0
snu = 0

for i in range(1,n+1):
    if Visited_n[i] >= Visited_one[i]:
        fen += 1
    else:
        snu += 1

if fen > snu:
    ans = 'Fennec'
else:
    ans = 'Snuke'
print(ans)

Submission status: Accepted

Solution code:
# D - Fennec VS. Snuke
# https://atcoder.jp/contests/abc067/submissions/7707307
# https://atcoder.jp/contests/abc067/submissions/10252214
from collections import deque
n=int(input())
G=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

dist_f=[-1]*n
dist_s=[-1]*n
dist_f[0]=0
dist_s[n-1]=0

q = deque()
q.append(0)
while q:
    x = q.popleft()
    for nx in G[x]:
        if dist_f[nx] == -1:
            q.append(nx)
            dist_f[nx]=dist_f[x]+1
 
q = deque()
q.append(n-1)
while q:
    x = q.popleft()
    for nx in G[x]:
        if dist_s[nx] == -1:
            q.append(nx)
            dist_s[nx]=dist_s[x]+1
f,s=0,0
for i in range(n):
    if dist_f[i]<=dist_s[i]:
        f+=1
    else:
        s+=1
if f>s:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

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


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


def dfs(v, dist):
    for u in G[v]:
        if dist[u] != -1:
            continue
        dist[u] = dist[v] + 1
        ret = dfs(u, dist)


dist_fen = [-1] * N
dist_fen[0] = 0
dfs(0, dist_fen)

dist_snu = [-1] * N
dist_snu[N-1] = 0
dfs(N-1, dist_snu)

fen = 0
for v in range(N):
    if dist_fen[v] <= dist_snu[v]:
        fen += 1
if fen > N // 2:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)

    def bfs(start):
        q = [start]
        d = [inf]*N
        d[start] = 0
        for i in range(N):
            tmp = []
            while q:
                v = q.pop()
                for to in edge[v]:
                    if d[to]==inf:
                        tmp.append(to)
                        d[to] = i+1
            q = tmp
        return d        
    
    fennec = bfs(0)
    snuke = bfs(N-1)

    f,s = 0,0
    for i in range(N):
        if fennec[i]<=snuke[i]:
            f+=1
        else:
            s+=1
    if f>s:
        print("Fennec")
    else:
        print("Snuke")

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

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

dp0 = [0 for i in range(n)]
dp1 = [0 for i in range(n)]

dp0[0] = 1
dp1[-1] = 1

for i in range(n-1):
    o,p = m()
    o -= 1
    p -= 1
    tree[o].append(p)
    tree[p].append(o)

de = cl.deque([0,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp0[i] == 0:
            dp0[i] = co
            de.append(i)

de = cl.deque([n-1,-1])
co = 1
while de:
    po = de.popleft()
    if po == -1:
        co += 1
        if len(de) == 0:
            break
        de.append(-1)
        continue
    for i in tree[po]:
        if dp1[i] == 0:
            dp1[i] = co
            de.append(i)

dp0[0] = 0
dp1[-1] = 0

co = 0

for i in range(n):
    co += 1 if dp0[i] - dp1[i] <= 0 else -1
if co > 0:
    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)
#print(g)

from collections import deque
q = deque()
visit = [-1]*n
q.append(0)
visit[0] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if visit[new_x] != -1:
            continue
        visit[new_x] = visit[x]+1
        q.append(new_x)
        #if new_x == n-1:
            #break
#print(visit)

q = deque()
visit2 = [-1]*n
q.append(n-1)
visit2[n-1] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if visit2[new_x] != -1:
            continue
        visit2[new_x] = visit2[x]+1
        q.append(new_x)
#print(visit2)

fe = 0
sn = 0
for i in range(n):
    if visit[i] <= visit2[i]:
        fe += 1
    else:
        sn += 1
if fe > sn:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

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

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)


def dist(root):  # 根をnとしたときの各点の深さ
    res = [-1] * (N + 1)
    node = [root]
    res[root] = 0
    while node:
        s = node.pop()
        d = res[s]
        for t in edge[s]:
            if res[t] == -1:
                node.append(t)
                res[t] = d + 1
    return res[1:]


fenek = dist(1)
snuke = dist(N)
f, s = 0, 0
for i, j in zip(fenek, snuke):
    if i <= j:
        f += 1
    else:
        s += 1

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

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush, heappop
    N = int(input())
    ans = ["Fennec", "Snuke"]
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        edge[a].append((1, b))
        edge[b].append((1, a))

    def dijkstra(s):
        """ 始点sから各頂点への最短距離 O((|E|+|V|)log|V|) """
        d = [10**8]*N
        used = [True] * N  # True:未確定
        d[s] = 0
        used[s] = False
        edges = []
        for e in edge[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in edge[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

    d_s = dijkstra(0)
    d_g = dijkstra(N-1)
    # print(d_s, d_g, sep="\n")
    get = [0, 0]
    for s, g in zip(d_s, d_g):
        if s <= g:
            get[0] += 1
        else:
            get[1] += 1
    if get[0] > get[1]:
        print(ans[0])
    else:
        # マスの数同じならsnuke win
        print(ans[1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

from collections import deque
q = deque()
q.append((0, 0))
d = [10**6]*N
d[0] = 0
while q:
    temp = q.popleft()
    v = temp[0]
    r = temp[1]
    for t in E[v]:
        if d[t] == 10**6:
            d[t] = r+1
            q.append((t, r+1))

num = N-1
for k in range((d[N-1]-1)//2):
    for v in E[num]:
        if d[v] == d[N-1]-k-1:
            num = v
            break
used = [0]*N
used[num] = 1
q = deque([0])
while q:
    temp = q.pop()
    for v in E[temp]:
        if used[v] == 0:
            used[v] = 1
            q.append(v)

if sum(used)-1 > N-sum(used)+1:
    ans = "Fennec"
else:
    ans = "Snuke"
print(ans)

Submission status: Accepted

Solution code:
import heapq

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

# n,w = map(int,input().split()) #n:頂点数　w:辺の数
n = int(input()) #n:頂点数　w:辺の数
w = n - 1

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

d0 = dijkstra_heap(0)
d1 = dijkstra_heap(n-1)

f = 0
s = 0
for i in range(1,n-1):
    if d0[i] <= d1[i]:
        f +=1
    else:
        s += 1

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def shortest_path(pt,s,t):
    n = len(pt)
    used = [False]*n
    pre = [-1]*n
    q = [s]
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if not used[j]:
                    used[j] = True
                    pre[j] = i
                    q1.append(j)
        q = q1

    if used[t]:
        path = [t]
        p = t
        while True:
            p = pre[p]
            path.append(p)
            if p == s:
                break
        return list(reversed(path))
    else:
        return []

N = I()
a,b = MI(N-1,2)

pt = edges_to_pt(a,b,N)
path = shortest_path(pt,0,N-1)

v = path[math.ceil(len(path)/2)]
visited = [False]*N
visited[v] = True
S = [v]
num = 1
while S:
    v1 = S.pop()
    for i in pt[v1]:
        if i == path[math.ceil(len(path)/2)-1]:
            continue
        if not visited[i]:
            visited[i] = True
            num += 1
            S.append(i)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
dic = defaultdict(list)

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

dist1 = [float('inf')]*N
dist2 = [float('inf')]*N

q1 = [0]
q2 = [N-1]

dist1[0] = 0
dist2[N-1] = 0

while q1:
  e = q1.pop()
  for p in dic[e]:
    if dist1[p]>dist1[e]+1:
      dist1[p] = dist1[e]+1
      q1 += [p]

while q2:
  e = q2.pop()
  for p in dic[e]:
    if dist2[p]>dist2[e]+1:
      dist2[p] = dist2[e]+1
      q2 += [p]

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:
from bisect import *
from collections import *
N=int(input())
AB=[map(int,input().split()) for i in range(N-1)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
stack=deque([[1,0]])
visited=set([1])
flag=0
while stack :
    a,m=stack.popleft()
    for p in data[a]:
        if p==N:
            flag=1
            break
        if not p in visited:
            visited.add(p)
            stack.append([p,m+1])
    if flag:
        break

M=m//2
countFennec=0
countSnuke=0
visited=set([1,N])
stackSnuke=deque([[N,0]])
while stackSnuke:
    a,m=stackSnuke.popleft()
    if m>=M:
        stackSnuke.append([a,m])
        break
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(p)
            stackSnuke.append([p,m+1])

stackFennec=deque([[1,0]])
while stackFennec:
    a,m=stackFennec.popleft()
    for p in data[a]:
        if not p in visited:
            countFennec+=1
            visited.add(p)
            stackFennec.append([p,m+1])

while stackSnuke:
    a,m=stackSnuke.popleft()
    for p in data[a]:
        if not p in visited:
            countSnuke+=1
            visited.add(p)
            stackSnuke.append([p,m+1])


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

Submission status: Accepted

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

# DFS for tree

def dfs(startp, depth):
  visited = [False for i in range(N)]
  d = deque()
  d.append(startp)

  while len(d) > 0:
    p = d.pop()
    visited[p] = True
    for q in E[p]:
      if visited[q]:
        continue
      d.append(q)
      depth[q] = depth[p] + 1

distf = [0 for i in range(N)]
dists = [0 for i in range(N)]

dfs(0, distf)
dfs(N-1, dists)

#print(distf)
#print(dists)
cntf, cnts = 0,0
for i in range(N):
  if distf[i] <= dists[i]:
    cntf += 1
  else:
    cnts += 1
    
print("Fennec" if cntf > cnts else "Snuke")

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    dst[a-1].append(b-1)
    dst[b-1].append(a-1)
b = [0]
w = [n-1]
c = [0]*n
c[0] = 1
c[n-1] = -1
while len(b)>0 or len(w)>0:
    nxtb = []
    while len(b)>0:
        x = b.pop()
        for y in dst[x]:
            if c[y]==0:
                c[y] = 1
                nxtb.append(y)
    b = nxtb
    nxtw = []
    while len(w)>0:
        x = w.pop()
        for y in dst[x]:
            if c[y]==0:
                c[y] = -1
                nxtw.append(y)
    w = nxtw
print('Snuke' if sum(c)<=0 else 'Fennec')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

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

    def root(x):
        go = [False for _ in range(N)]
        d = [0 for _ in range(N)]
        go[x] = True
        q = deque([x])
        while q:
            now = q.pop()
            for fol in dist[now]:
                if go[fol]:
                    continue
                else:
                    d[fol] = d[now] + 1
                    go[fol] = True
                    q.append(fol)
        return d
    
    fen = root(0)
    snu = root(N-1)
    fg = sg = 0
    for i in range(N):
        if fen[i] <= snu[i]:
            fg += 1
        else:
            sg += 1
            
    print("Fennec" if fg > sg else "Snuke")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# [数学、特にグラフ理論の分野における木（き、）とは、連結で閉路を持たないグラフである。]
# なので1->Nは1通り。つまり1->Nの最短経路上にあるマスをつぶすのが先
# で、残ったのを探索できるが、こういう二段構えで実装するのが面倒。
# もうちょっと考えると、1->i とi->Nの距離をみたとき、前者が小さければ先に到達できるので黒で埋められることが分かる
# （進めなくなったら負け、がめんどくさいが、すすめなくなったらパス、とすると、勝敗は変わらないことになる）
# 1とNからスタートして2回BFSすりゃいいか

import sys
from collections import deque

sys.setrecursionlimit(10 ** 8)

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

table_from_one = [10 ** 5 for _ in range(n)]
table_from_one[0] = 0
table_from_n = [10 ** 5 for _ in range(n)]
table_from_n[-1] = 0
arr_from_one = deque([0])
arr_from_n = deque([n - 1])


def set_table(table, arr):
    while len(arr) > 0:
        cur = arr.popleft()
        for next_node in graph[cur]:
            if table[next_node] < 10 ** 5:
                continue
            table[next_node] = table[cur] + 1
            arr.append(next_node)


set_table(table_from_one, arr_from_one)
set_table(table_from_n, arr_from_n)
result = 0
for i in range(n):
    if table_from_one[i] <= table_from_n[i]:
        result += 1
    else:
        result -= 1
print("Fennec" if result > 0 else "Snuke")