Problem p02678 (python)

Fixed submission:
from collections import deque

def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.popleft()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.append(next)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

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


def main():
    n,m = map(int,input().split())
    arr = np.zeros([n, n], dtype=int)
    for _ in range(m):
        a, b = map(int,input().split())
        arr[a-1][b-1] = 1
        arr[b-1][a-1] = 1
    q = deque([0])
    ans = {i:-1 for i in range(n)}
    ans[0] = 0
    while True:
        now = q.popleft()
        for i in range(n):
            if arr[now][i] == 0:
                continue
            if ans[i] == -1:
                ans[i] = now
                q.append(i)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i]+1)


if __name__=='__main__':
    main()

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


def main():
    n,m = map(int,input().split())
    arr = np.zeros([n, n])
    for _ in range(m):
        a, b = map(int,input().split())
        arr[a-1][b-1] = 1
        arr[b-1][a-1] = 1
    q = deque()
    q.append(0)
    ans = {i:0 for i in range(1, n)}
    while q:
        now = q.popleft()
        for i in range(n):
            if arr[now][i] == 0:
                continue
            if i == 0:
                continue
            if ans[i] == 0:
                ans[i] = now+1
                q.append(i)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])


if __name__=='__main__':
    main()

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

def main():
    n,m = map(int,input().split())
    arr = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        arr[a-1].append(b-1)
        arr[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.popleft()
        for i in ab[now]:
            if ans[i] == -1:
                ans[i] = now+1
                q.append(i)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

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

def main():
    n,m = map(int,input().split())
    arr = np.zeros([n,n])
    for _ in range(m):
        a, b = map(int,input().split())
        arr[a-1][b-1] = 1
        arr[b-1][a-1] = 1
    q = deque()
    q.append(0)
    path = {i:0 for i in range(2, n+1)}
    while q:
        pos = q.popleft()
        for i in range(1, n):
            if arr[pos][i] == 1:
                q.append(i)
                if path[i+1] == 0:
                    path[i+1] = pos + 1
        if len(q) == 0:
            break
        flag = True
        for i in path:
            if path[i] == 0:
                flag = False
        if flag:
            break
    print('Yes')
    for i in path:
        print(path[i])

if __name__=='__main__':
    main()

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

import numpy as np

sys.setrecursionlimit(100000000)


def solve(n, arr, q, path, c):
  flag = True
  for i in path:
    if path[i] == 0:
      flag = False
  if flag:
    return path
  if c > 100000000:
    return -1
  if len(q) == 0:
    return -1
  pos = q.popleft()
  for i in range(1, n):
    if arr[pos][i] == 1:
      q.append(i)
      if path[i+1] == 0:
        path[i+1] = pos+1
  return solve(n, arr, q, path, c+1)
        

def calc(n, arr):
  path = {i:0 for i in range(2, n+1)}
  queue = deque([0])
  result = solve(n, arr, queue, path, 0)
  if result == -1:
    return ["No"]
  else:
    L = ["Yes"]
    for i in result:
      L.append(result[i])
    return L

n, m = map(int, input().split())
arr = np.zeros([n, n])
for i in range(m):
  tmp0, tmp1 = map(int, input().split())
  arr[tmp0-1][tmp1-1] = 1
  arr[tmp1-1][tmp0-1] = 1

answer = calc(n, arr)
for i in answer:
  print(i)

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

import numpy as np

sys.setrecursionlimit(100000000)


def solve(n, arr, q, path, c):
  flag = True
  for i in path:
    if path[i] == 0:
      flag = False
  if flag:
    return path
  if c > 100000000:
    return -1
  if len(q) == 0:
    return -1
  pos = q.popleft()
  for i in range(1, n):
    if arr[pos][i] == 1:
      q.append(i)
      if path[i+1] == 0:
        path[i+1] = pos+1
  return solve(n, arr, q, path, c+1)
        

def calc(n, arr):
  path = {i:0 for i in range(2, n+1)}
  queue = deque([0])
  result = solve(n, arr, queue, path, 0)
  if result == -1:
    return ["No"]
  else:
    L = ["Yes"]
    for i in result:
      L.append(result[i])
    return L

n, m = map(int, input().split())
arr = np.zeros([n, n])
for i in range(m):
  tmp0, tmp1 = map(int, input().split())
  arr[tmp0-1][tmp1-1] = 1
  arr[tmp1-1][tmp0-1] = 1

answer = calc(n, arr)
for i in answer:
  print(i)

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

import numpy as np

sys.setrecursionlimit(100000000)


def solve(n, arr, q, path, c):
  flag = True
  for i in path:
    if path[i] == 0:
      flag = False
  if flag:
    return path
  if c > 100000000:
    return -1
  if len(q) == 0:
    return -1
  pos = q.popleft()
  for i in range(1, n):
    if arr[pos][i] == 1:
      q.append(i)
      if path[i+1] == 0:
        path[i+1] = pos+1
  return solve(n, arr, q, path, c+1)
        

def calc(n, arr):
  path = {i:0 for i in range(2, n+1)}
  queue = deque()
  for i in range(n):
    if arr[0][i] == 1:
      queue.append(i)
      path[i+1] = 1
  result = solve(n, arr, queue, path, 0)
  if result == -1:
    return ["No"]
  else:
    L = ["Yes"]
    for i in result:
      L.append(result[i])
    return L

n, m = map(int, input().split())
arr = np.zeros([n, n])
for i in range(m):
  tmp0, tmp1 = map(int, input().split())
  arr[tmp0-1][tmp1-1] = 1
  arr[tmp1-1][tmp0-1] = 1

answer = calc(n, arr)
for i in answer:
  print(i)

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

import numpy as np


def solve(n, arr, q, path, c):
  flag = True
  for i in path:
    if path[i] == 0:
      flag = False
  if flag:
    return path
  if c > 100000000:
    return -1
  if len(q) == 0:
    return -1
  pos = q.popleft()
  for i in range(1, n):
    if arr[pos][i] == 1:
      q.append(i)
      if path[i+1] == 0:
        path[i+1] = pos+1
  return solve(n, arr, q, path, c+1)
        

def calc(n, arr):
  path = {i:0 for i in range(2, n+1)}
  queue = deque()
  for i in range(n):
    if arr[0][i] == 1:
      queue.append(i)
      path[i+1] = 1
  result = solve(n, arr, queue, path, 0)
  if result == -1:
    return ["No"]
  else:
    L = ["Yes"]
    for i in result:
      L.append(result[i])
    return L

n, m = map(int, input().split())
arr = np.zeros([n, n])
for i in range(m):
  tmp0, tmp1 = map(int, input().split())
  arr[tmp0-1][tmp1-1] = 1
  arr[tmp1-1][tmp0-1] = 1

answer = calc(n, arr)
for i in answer:
  print(i)

Buggy submission (verdict: Runtime Error):
from operator import mul
from functools import reduce
from collections import deque

import numpy as np


def is_ok(n, lst):
  flags = [0 for i in range(n)]
  for i in lst:
    flags[i[0]-1] = 1
    flags[i[1]-1] = 1
  if reduce(mul, flags) > 0:
    return True
  return False  


n, m = map(int, input().split())
arr = np.zeros([n, n])
for i in range(m):
  tmp0, tmp1 = map(int, input().split())
  arr[tmp0-1][tmp1-1] = 1
  arr[tmp1-1][tmp0-1] = 1
  

can_solve = is_ok(n, lst)
if can_solve:
  print("Yes")
else:
  print("No")