Problem p02678 (python)

Fixed submission:
N, M = 6, 9
ARR = [
    [3, 4],
    [6, 1],
    [2, 4],
    [5, 3],
    [4, 6],
    [1, 5],
    [6, 2],
    [4, 5],
    [5, 6],
]

N, M = 4, 4
ARR = [
    [1, 2],
    [2, 3],
    [3, 4],
    [4, 2],
]

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))

from collections import deque


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [-1 for i in range(n)]
    prevs = [-1 for i in range(n)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStates, prevs


nodes, nodeStates, prevs = prepare(N, M, ARR)


def bfs(nodes, nodeStates, prevs, n):
    q = deque()
    q.append({'prev': -1, 'to': 0})
    while len(q) > 0:
        first = q.popleft()
        currentNode = first['to']
        previousNode = first['prev']
        if nodeStates[currentNode] != -1:
            continue
        prevs[currentNode] = previousNode
        childNodes = nodes[currentNode]
        nodeStates[currentNode] = 1
        for childNode in childNodes:
            q.append({'prev': currentNode, 'to': childNode})

    print("Yes")
    for i in range(1, n):
        print(prevs[i] + 1)


bfs(nodes, nodeStates, prevs, N)

Buggy submission (verdict: Runtime Error):
from collections import deque

N, M = map(int, input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStatus = [False for i in range(n)]
    for i in range(n):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            if nodeStatus[childNode] == True:
                continue
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

    print("Yes")
    for i in range(1, n):
        print(nodeMarks[i] + 1)


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

Buggy submission (verdict: Runtime Error):
from collections import deque

N, M = map(int, input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStatus = [False for i in range(n)]
    for i in range(n):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStatus


def calculate(n, nodes, nodeStatus):
    nodeMarks = [-1 for i in range(n)]

    q = deque()

    q.append((0, -1))

    while len(q) > 0:
        currentNode, parentNode = q.popleft()

        if nodeStatus[currentNode] == True:
            continue

        nodeStatus[currentNode] = True
        nodeMarks[currentNode] = parentNode
        childNodes = nodes[currentNode]

        for childNode in childNodes:
            q.append((childNode, currentNode))

    minusNumber = nodeMarks.count(-1)
    if minusNumber > 1:
        print("No")
        return

    print("Yes")
    for i in range(1, n):
        print(nodeMarks[i] + 1)


nodes, nodeStatus = prepare(N, M, ARR)

calculate(N, nodes, nodeStatus)

Buggy submission (verdict: Runtime Error):
# N, M = 6, 9
# ARR = [
#     [3, 4],
#     [6, 1],
#     [2, 4],
#     [5, 3],
#     [4, 6],
#     [1, 5],
#     [6, 2],
#     [4, 5],
#     [5, 6],
# ]

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeResults = [0 for i in range(n - 1)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStates, nodeResults


nodes, nodeStates, nodeResults = prepare(N, M, ARR)


def dfs(currentNode, parentNode, nodes):
    childrenNodes = nodes[currentNode]

    if nodeStates[currentNode] > 0:
        return

    if currentNode >= 1:
        nodeResults[currentNode - 1] = parentNode + 1

    nodeStates[currentNode] = True
    for childNode in childrenNodes:
        dfs(childNode, currentNode, nodes)


dfs(0, -1, nodes)

if sum(nodeStates) == N:
    print("Yes")
    for i in range(N - 1):
        print(nodeResults[i])
else:
    print("No")