Problem:


Score : 400 points

Problem Statement

Fennec and Snuke are playing a board game.

On the board, there are N cells numbered 1 through N, and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.

Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored.
Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell.
More specifically, each player performs the following action in her/his turn:

Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.

Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.

A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.

Constraints

2 \leq N \leq 10^5

1 \leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

If Fennec wins, print Fennec; if Snuke wins, print Snuke.

Sample Input 1

7
3 6
1 2
3 1
7 4
5 7
1 4

Sample Output 1

Fennec

For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.

Sample Input 2

4
1 4
4 2
2 3

Sample Output 2

Snuke



Sample input:
7
3 6
1 2
3 1
7 4
5 7
1 4


Sample output:
Fennec

Submission status: Accepted

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

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

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

shortest = []
def get_path(start, end, par):
    if end in e[start]:
        shortest.append(end)
        return True
    for item in e[start]:
        if item != par:
             if get_path(item, end, start):
                 shortest.append(item)
                 return True

def tree_count(start, par, a, b):
    count = 0
    for item in e[start]:
        if start == a and item == b:
            continue
        if start == b and item == a:
            continue
        if item != par:
            count += 1
            count += tree_count(item, start, a, b)
    return count

get_path(0, n-1, -1)
shortest.append(0)
shortest = shortest[::-1]
cut_l = (len(shortest)-1) // 2
p = tree_count(0, -1, shortest[cut_l], shortest[cut_l+1])
q = n - p - 2 
if p > q:
    print("Fennec")
else:
    print("Snuke")

Submission status: Accepted

Solution code:
import heapq

N = int(input())
d = [0] * N
INF = float('inf')
        
G = [[] for i 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)
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heapq.heappush(h, [d[e], e])

dijkstra(0)
d2 = d.copy()
F = d2

dijkstra(N - 1)
S = d

Fennec = 0
for i in range(N):
    if F[i] <= S[i]:
        Fennec += 1
        
print('Fennec' if Fennec > N - Fennec else 'Snuke')

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

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

    qo = deque()
    qo.append(1)
    while len(qo) > 0:
        i = qo.popleft()
        for j in A[i]:
            if dist_one[j] != -1:
                continue

            dist_one[j] = dist_one[i] + 1
            qo.append(j)

    qn = deque()
    qn.append(N)
    while len(qn) > 0:
        i = qn.popleft()
        for j in A[i]:
            if dist_n[j] != -1:
                continue

            dist_n[j] = dist_n[i] + 1
            qn.append(j)

    co, cn = 0, 0
    for i in range(1, N+1):
        if dist_one[i] <= dist_n[i]:
            co += 1
        else:
            cn += 1

    if co > cn:
        return 'Fennec'
    else:
        return 'Snuke'


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from queue import Queue


def distances(tree: list, size: int, root: int)->list:
    dists = [0] * size

    q = Queue()
    q.put((root, -1, 0))

    while not q.empty():
        v, prev, d2v = q.get()
        dists[v] = d2v

        for u, dv2u in tree[v]:
            if u == prev:
                continue
            q.put((u, v, d2v + dv2u))

    return dists


def fennec_vs_snuke(N: int, edges: list)->str:
    tree = [[] for _ in range(N)]
    for a, b in edges:
        tree[a-1].append((b-1, 1))
        tree[b-1].append((a-1, 1))

    d_from1 = distances(tree, N, 0)
    d_fromN = distances(tree, N, N-1)

    fennec, snuke = 0, 0
    for i in range(N):
        if d_fromN[i] < d_from1[i]:
            snuke += 1
        else:
            fennec += 1
    return 'Fennec' if fennec > snuke else 'Snuke'


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(int(s) for s in input().split()) for _ in range(N-1)]
    ans = fennec_vs_snuke(N, edges)
    print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
from collections import deque
N = int(input())
adj = [[] for _ in range(N+1)]

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

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

if sum(df[i] > ds[i] for i in range(1,N+1)) >= N/2:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

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

def dfs(v):
    d= [0] * n
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        visited[v] = 1
        visited.append(v)
        for i in edges[v]:
            if not visited[i]:
                d[i] = d[v] + 1
                q.append(i)
    return d

dist_from0 = dfs(0)
dist_fromn = dfs(n-1)

f = 0
s = 0
for i in range(n):
    if dist_fromn[i] >= dist_from0[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
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
brack[N]=0
check=deque([1])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if brack[i]>10**9:
            brack[i]=brack[now]+1
            check.append(i)
white=[float('inf')]*(N+1)
white[N]=0
white[1]=0
check=deque([N])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if white[i]>10**9:
            white[i]=white[now]+1
            check.append(i)
brack[N]=float('inf')
white[1]=float('inf')
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc067/submissions/2975640

from collections import deque

INF = 10 ** 5 + 10

N = int(input())
f = [INF for _ in range(N)]
# f[v]:=頂点0からの最短距離
s = [INF for _ in range(N)]
# s[v]:=頂点N-1からの最短距離

e = [[] for _ in range(N)]
# 道, 隣接リスト, 0-indexed

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

q = deque()
q.append((0, 0))

while q:
    v, d = q.popleft()
    f[v] = d
    for nv in e[v]:
        if f[nv] <= d + 1: continue
        q.append((nv, d + 1))

q = deque()
q.append((N - 1, 0))

while q:
    v, d = q.popleft()
    s[v] = d
    for nv in e[v]:
        if s[nv] <= d + 1: continue
        q.append((nv, d + 1))

Fennec_count = 0
for v in range(N):
    if f[v] <= s[v]:
        # 頂点0から近い場合
        # 等距離なら先に塗れる黒になる
        Fennec_count += 1
        # 黒

print('Fennec' if Fennec_count > N - Fennec_count else 'Snuke')

Submission status: Accepted

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

N = int(input())
ad = [[] for _ in range(N)]
dis = [[-1]*N,[-1]*N]

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

def bfs(s):
    index = 0 if s == 0 else 1
    dq = deque()
    dq.append((s,0,-1))
    while dq:
        v,d,pre = dq.popleft()
        dis[index][v] = d
        for nv in ad[v]:
            if nv == pre:continue
            dq.append((nv,d+1,v))

bfs(0); bfs(N-1)
f = 0; s = 0
for d0,d1 in zip(dis[0],dis[1]):
    if d0 <= d1: f += 1
    else: s += 1
ans = "Fennec" if f > s else "Snuke"
print(ans)

Submission status: Accepted

Solution code:
import sys,copy
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
inf = float('inf')

N = int(input())
ad = [{} for _ in range(N)]
dis = [inf]*N
near = [-1]*N
player = ["Fennec","Snuke"]

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

back_up = [copy.deepcopy(line) for line in ad]

def dfs(v,start,depth=0):
    if dis[v] > depth:
        dis[v] = depth
        near[v] = start
    if not ad[v]:
        return
    while ad[v]:
        key,nv = ad[v].popitem()
        ad[nv].pop(key)
        dfs(nv,start,depth+1)

dfs(0,0)
ad = back_up
dfs(N-1,N-1)
f = near.count(0)
s = N-f
ans = player[0] if f > s else player[1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N = int(input())
    adj = [set() for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].add(b)
        adj[b].add(a)
    state = [None] * (N+1)
    q = deque([(1, "B"), (N, "W")])
    while len(q):
        node, color = q.popleft()
        if state[node] is not None:
            continue
        state[node] = color
        for nxt in adj[node]:
            if state[nxt] is None:
                adj[nxt].remove(node)
                q.append((nxt, color))
    result = {"B": 0, "W": 0}
    for s in state:
        if s in result:
            result[s] += 1
    if result["B"] > result["W"]:
        print("Fennec")
    else:
        print("Snuke")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = deque()
q.append(0)
d_f[0] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import queue
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = deque()
q.append(0)
d_f[0] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import queue
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = queue.Queue()
q.put(0)
d_f[0] = 0
while not q.empty():
    x = q.get()
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.put(y)
d_s = [-1 for i in range(n)]
q.put(n-1)
d_s[n-1] = 0
while not q.empty():
    x = q.get()
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.put(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n-1)]
for i in range(n-1):
    a[i+1] += a[i]
for i in range(n-1):
    b[i] = abs(2*a[i]-a[n-1])
print(min(b))
"""

#D
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d_f = [-1 for i in range(n)]
q = []
q.append(0)
d_f[0] = 0
while q:
    x = q.pop(-1)
    for y in v[x]:
        if d_f[y] == -1:
            d_f[y] = d_f[x] + 1
            q.append(y)
d_s = [-1 for i in range(n)]
q.append(n-1)
d_s[n-1] = 0
while q:
    x = q.pop(-1)
    for y in v[x]:
        if d_s[y] == -1:
            d_s[y] = d_s[x] + 1
            q.append(y)
f = 0
s = 0
for i in range(n):
    if d_f[i] <= d_s[i]:
        f += 1
    else:
        s += 1
if f > s:
    print("Fennec")
else:
    print("Snuke")
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

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

def dfs(v):
    d = [-1 for i in range(n)]
    q = []
    d[v] = 0
    q.append(v)
    while len(q):
        v = q.pop()
        for i in a[v]:
            if d[i] == -1:
                d[i] = d[v]+1
                q.append(i)
    return d
c1 = dfs(0)
c2 = dfs(n-1)
c = 0
for i in range(n):
    if c1[i]>c2[i]:
        c += 1
if c>= n/2:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

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

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

i=0
b=1
w=1
f[1]=1
f[N]=1
bq=d[1]
wq=d[N]

while len(bq)>0 or len(wq)>0:
    tmp=[]
    if i==0:
        for q in bq:
            if f[q]==0:
                f[q]=1
                b+=1
                tmp+=d[q]
    else:
        for q in wq:
            if f[q]==0:
                f[q]=1
                w+=1
                tmp+=d[q]
    if i==0:
        i=1
        bq=tmp
    else:
        i=0
        wq=tmp

if b>w:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
num_hen = n-1
info = [list(map(int,input().split())) for i in range(num_hen)]

for i in range(num_hen):
  info[i][0] -=1
  info[i][1] -=1

tree=[[] for i in range(n)]
for i in range(num_hen):
  tree[info[i][0]].append(info[i][1])
  tree[info[i][1]].append(info[i][0])
  
#paintedが0のときまだ塗られていない、1のとき黒、-1のとき白
painted=[0]*n
painted[0]=1
painted[n-1]=-1

#0からn-1まで行くための経路を求める（dfsで経路復元する）。
#keiroが経路になる
que = deque()
for i in range(len(tree[0])):
  que.append([tree[0][i],0])
visited=[False]*n 
visited[0]=True
keiro ={}
while que:
  v = que.pop()
  keiro[v[1]]=v[0]
  if v[0] == n-1:
    final = v[1]
    break
  elif not visited[v[0]]:
    for i in range(len(tree[v[0]])):
      que.append([tree[v[0]][i],v[1]+1])
    visited[v[0]]=True

#経路を黒と白で塗る
for i in range(final):
  if i%2==0:
    painted[keiro[i//2]]=1
  else:
    painted[keiro[final-1-i//2]]=-1

#全部の頂点に渡ってペイントするためのdfs
def dfs(i,color):
  que2 = deque()
  for element in tree[i]:
    que2.append(element)
  while que2:
    w = que2.pop()
    if painted[w]==0:
      painted[w]=color
      for element in tree[w]:
        que2.append(element)
  return

for i in range(n):
  if painted[i]==1:
    dfs(i,1)
  elif painted[i]==-1:
    dfs(i,-1)

print("Fennec" if painted.count(1) > painted.count(-1) else "Snuke")

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
li = []
for _ in range(n - 1):
    li.append(list(map(int, input().split())))

# construct graph
edges = [set() for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].update({j})
    edges[j].update({i})

# search middle edge and cut
Q = deque()
Q.append([0, 0])
visited = {0}
pre = {}
while len(Q) > 0:
    u, d = Q.pop()
    if u == n - 1:
        i = (d - 1) // 2
        a = u
        for _ in range(i + 1):
            b = a
            a = pre[b]
        edges[a].remove(b)
        edges[b].remove(a)
        break
    for v in edges[u]:
        if v not in visited:
            pre[v] = u
            visited.update({v})
            Q.append([v, d + 1])

# count Fennec's area
Q = deque()
Q.append(0)
visited = {0}
while len(Q) > 0:
    u = Q.pop()
    for v in edges[u]:
        if v not in visited:
            visited.update({v})
            Q.append(v)

ans = 'Snuke' if len(visited) <= n // 2 else 'Fennec'

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

INF = 10 ** 20

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

def dijkstra(start):
    dist = [INF] * n
    dist[start] = 0
    que = deque()
    que.append((0, start))
    while que:
        score, node = que.popleft()
        for to in edges[node]:
            if dist[to] > score + 1:
                dist[to] = score + 1
                que.append((score + 1, to))
    return dist

dist1 = dijkstra(0)
dist2 = dijkstra(n - 1)
black = 0
for i in range(n):
    if dist1[i] <= dist2[i]:black += 1
white = n - black
if white >= black:
    print("Snuke")
else:
    print("Fennec")

Submission status: Accepted

Solution code:
#067-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n=I()
nl=[[] for i in range(n)]
distfen=[-1 for i in range(n)]
distsnu=[-1 for i in range(n)]

for i in range(n-1):
    a,b=IL()
    nl[a-1].append(b-1)
    nl[b-1].append(a-1)
    
q=[[0,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distfen[v]=d+1
            q.append([v,d+1])

q=[[n-1,0]]
vis=[False for i in range(n)]
while len(q)!=0:
    s,d=q.pop(0)
    vis[s]=True
    for v in nl[s]:
        if not vis[v]:
            distsnu[v]=d+1
            q.append([v,d+1])
        
fen=0
snu=0

for i in range(1,n-1):
    if distfen[i]<=distsnu[i]:
        fen+=1
    else:
        snu+=1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


d1 = [None] * (N+1)
dn = [None] * (N+1)


def dfs(v, d, d_list):
    d_list[v] = d
    for nv in G[v]:
        if d_list[nv] is None:
            dfs(nv, d+1, d_list)

dfs(1, 0, d1)
dfs(N, 0, dn)

cnt = 0
for i in range(1, N+1):
    if d1[i] <= dn[i]:
        cnt += 1
    else:
        cnt -= 1

print('Fennec' if cnt > 0 else 'Snuke')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


d1 = [None] * (N+1)
dn = [None] * (N+1)


def dfs(v, d, d_list):
    d_list[v] = d
    for nv in G[v]:
        if d_list[nv] is None:
            dfs(nv, d+1, d_list)

dfs(1, 0, d1)
dfs(N, 0, dn)

cnt = 0
for i in range(1, N+1):
    if d1[i] <= dn[i]:
        cnt += 1
    else:
        cnt -= 1

if cnt > 0:
    print('Fennec')
else:
    print('Snuke')

Submission status: Accepted

Solution code:
import queue

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

stack = [0]
visited = [False for _ in range(n)]
white = 0
black = 0
wQueue = queue.Queue()
wQueue.put(0)
bQueue = queue.Queue()
bQueue.put(n-1)
# print(ab)
while 1:
    wSize = wQueue.qsize()
    if wSize != 0:
        for i in range(wSize):
            now = wQueue.get()
            if not visited[now]:
                white += 1
                visited[now] = True
                for j in range(len(ab[now])):
                        wQueue.put(ab[now][j])
    bSize = bQueue.qsize()
    if bSize != 0:
        for i in range(bSize):
            now = bQueue.get()
            if not visited[now]:
                black += 1
                visited[now] = True
                for j in range(len(ab[now])):
                        bQueue.put(ab[now][j])
    if wSize == 0 and bSize == 0:
        if white > black:
            print("Fennec")
        else:
            print("Snuke")
        # print("w:{} b:{}".format(white, black))
        exit()

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


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

path = Dijkstra(graph, 0, N - 1).execute()
cost = len(path) - 1

black = 1
if cost % 2 == 0:
    tmp = (cost - 1) // 2
    black += tmp + 1
else:
    tmp = (cost - 1) // 2
    black += tmp
not_path = set(path[black:])
visited = [False for _ in range(N)]
q = [0]
visited[0] = False
while len(q) != 0:
    dist = q.pop()
    for d in graph[dist].keys():
        if visited[d] or d in not_path:
            continue
        q.append(d)
        visited[d] = True
for p in tuple(path):
    visited[p] = False
for v in visited:
    if v:
        black += 1
white = N - black

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

Submission status: Accepted

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


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

path = Dijkstra(graph, 0, N - 1).execute()
cost = len(path) - 1

black = 1
if cost % 2 == 0:
    tmp = (cost - 1) // 2
    black += tmp + 1
else:
    tmp = (cost - 1) // 2
    black += tmp
not_path = set(path[black:])
visited = [False for _ in range(N)]
q = [0]
visited[0] = False
while len(q) != 0:
    dist = q.pop()
    for d in graph[dist].keys():
        if visited[d] or d in not_path:
            continue
        q.append(d)
        visited[d] = True
for p in path:
    visited[p] = False
for v in visited:
    if v:
        black += 1
white = N - black

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, 1))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, 1))

fennec = [float('inf')] * (N+1)
snuke = [float('inf')] * (N+1)
# 木の最短経路を算出するDFS
def dfs(memo: list, cur: int, prev: int, dist: int) -> None:
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(memo, nxt, cur, dist+cost)

dfs(fennec, 1, -1, 0)
dfs(snuke, N, -1, 0)

fn = sn = 0
for i in range(2, N):
    # 距離の近い方がそのマスを取れる(同じ距離なら先手が取る)
    if fennec[i] <= snuke[i]:
        fn += 1
    else:
        sn += 1
# 取れるマスの多い方(同点だと後手が勝つ)
if fn > sn:
    print('Fennec')
else:
    print('Snuke')