Problem p03660 (python)

Fixed submission:
# 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')

Buggy submission (verdict: Runtime Error):
def dfs(v, d):
    for u in g[v]:
        if d[u] != init:
            continue
        d[u] = d[v] + 1
        dfs(u, d)


def main():
    import sys
    input = sys.stdin.readline

    global g, init

    n = int(input())

    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    init = n

    dist_1 = [init] * n
    dist_1[0] = 0
    dfs(0, dist_1)

    dist_n = [init] * n
    dist_n[n - 1] = 0
    dfs(n - 1, dist_n)

    fennec = sum(dist_1[v] <= dist_n[v] for v in range(n))
    snuke = n - fennec

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


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def dfs(v, d, path):
    # 頂点(0, N - 1)間の最短距離を求める
    # m_dist[v]:=頂点0からの最短距離
    res = []
    if m_dist[v] < float('inf'):
        return
    m_dist[v] = min(m_dist[v], d)
    if v == N - 1:
        return path
    for nv in e[v]:
        ret = dfs(nv, d + 1, path + [nv])
        if ret:
            res = ret
            break
    return res


def dfs_to_color(v, my_color):
    # 着色可能な範囲を着色する
    # 自分の色（黒、白）の幹から出ている未着色のマスが着色可能
    if m_bl[v]: return
    m_bl[v] = True
    if m[v] == my_color or m[v] == None:
        m[v] = my_color
        for nv in e[v]:
            dfs_to_color(nv, my_color)


N = int(input())
m = [None for _ in range(N)]
m[0] = True
m[N - 1] = False
# 色, 0-indexed
# True == 黒 == Fennec
# False == 白 == Snuke
m_dist = [float('inf') for _ in range(N)]
# 頂点0からの距離
m_bl = [False for _ in range(N)]
# 着色作業が完了したか

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)

path = dfs(0, 0, [0])
# 頂点(0, N - 1)間の最短距離をm_dist[N-1]に代入
# 最短パスを返す

for p in path:
    if m_dist[p] <= abs(m_dist[N - 1] - m_dist[p]):
        # 頂点0から近い場合
        # 等距離なら先に塗れる黒になる
        m[p] = True
        # 黒
    else:
        # 頂点N-1から近い場合
        m[p] = False
        # 白
# 最短経路を先に着色する

dfs_to_color(0, True)
# Fennec

dfs_to_color(N - 1, False)
# Snuke

print('Fennec' if m.count(True) > m.count(False) else 'Snuke')