Problem p02678 (python)

Fixed submission:
import queue
INF = float('inf')

def bfs():
    q = queue.Queue()
    [q.put([x, 0]) for x in graph[0]]
    while not q.empty():
        n = q.get()
        nex = n[0]; now = n[1]
        if visited[nex] == INF:
            visited[nex] = now
            [q.put([x, nex]) for x in graph[nex]]
    return

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)

visited = [INF for _ in range(N)]
bfs()

if INF in visited:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(visited[i]+1)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
INF = float('inf')
#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []
#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)
#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True
#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [INF for _ in range(N)]

#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if depth == N - 1:
        return 1
    visited[now] = min(visited[now], depth)
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)
    return total_paths

# 複数経路の記録完了
dfs(0, 0)

if INF in visited:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(visited[i])

Buggy submission (verdict: Runtime Error):
# coding: utf-8

#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []
#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)
#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True
#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N
depthlist = [[] for _ in range(N)]
#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    depthlist[now].append(depth)
    if depth == N - 1:
        return 1
    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)
    visited[now] = False
    return total_paths

# 複数経路の記録完了
dfs(0, 0)

MIN = float('inf')
for i in range(N):
    MIN = min(len(depthlist[i]), MIN)
if MIN == 0:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(min(depthlist[i]))

Buggy submission (verdict: Runtime Error):
# coding: utf-8

#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []
#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)
#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True
#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N
depthlist = [[] for _ in range(N)]
#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    depthlist[now].append(depth)
    if depth == N - 1:
        return 1
    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)
    visited[now] = False
    return total_paths

# 複数経路の記録完了
dfs(0, 0)

MIN = float('inf')
for i in range(N):
    MIN = min(len(depthlist[i]), MIN)
if MIN == 0:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(min(depthlist[i]))