Problem p02678 (python)

Fixed submission:
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


n, w = map(int, input().split())

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)

Buggy submission (verdict: Runtime Error):
n, w = map(int, input().split())

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

prev = [None for _ in range(n)]
dist = [float('inf') for _ in range(n)]


def dfs(start):
    for n_r in edge[start]:
        if dist[n_r] > dist[start] + 1:
            dist[n_r] = dist[start] + 1
            prev[n_r] = start
        else:
            continue
        dfs(n_r)


dist[0] = 0
dfs(0)
if None in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)

Buggy submission (verdict: Runtime Error):
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


n, w = map(int, input().split())

edge = [[] for i in range(w)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)

Buggy submission (verdict: Runtime Error):
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


n, w = map(int, input().split())

edge = [[] for i in range(w)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i, j in enumerate(prev[1:]):
        print(j + 1)

Buggy submission (verdict: Runtime Error):
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    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())

edge = [[] for i in range(w)]
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])
d = dijkstra_heap(0)

if float('inf') in d:
    print('No')
else:
    print('Yes')
    for i, j in enumerate(d):
        if i == 0:
            continue
        print(j)