Problem p02678 (python)

Fixed submission:
#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

graph = [[] for i in range(N)]

for A, B in AB:
    graph[A-1] += [B]
    graph[B-1] += [A]

D = deque([0])
visited = [0] * N
visited[0] = 1

ret = [0 for i in range(N)]

while D:
    v = D.popleft()
    for i in graph[v]:
        i -= 1
        if visited[i]: continue
        visited[i] = 1
        ret[i] = v + 1
        D.append(i)

if any(ret[1:]):
    print("Yes")
    for i in ret[1:]:
        print(i)
else:
    print("No")

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

rets_ct = [N for i in range(N)]
rets = [0 for i in range(N)]

def dfs(second, num, ct, done):
    global road, rets_ct, rets
    
    if ct > rets_ct[start]:
        return

    if num == 0:
        rets[start] = second
        rets_ct[start] = ct
        return

    if done[num]:
        return
    done[num] = 1
    
    ct += 1
    next = road[num]
    for i in next:
        if second == 0:
            dfs(i, i, ct, copy.copy(done))
        else:
            dfs(second, i, ct, copy.copy(done))

for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(0, start, ct, done)

print("Yes")
for i in rets[1:]:
    print(i+1)

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

rets_ct = [N for i in range(N)]
rets = [0 for i in range(N)]

def dfs(second, num, ct, done):
    global road, rets_ct, rets
    
    if num == 0:
        if rets_ct[start] > ct:
            rets[start] = second
            rets_ct[start] = ct

    if done[num]:
        return
    done[num] = 1
    
    ct += 1
    next = road[num]
    for i in next:
        if second == 0:
            dfs(i, i, ct, copy.copy(done))
        else:
            dfs(second, i, ct, copy.copy(done))


for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(0, start, ct, done)

print("Yes")
for i in rets[1:]:
    print(i+1)

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

rets = [N for i in range(N)]

def dfs(start, num, ct, done):
    global rets, road
    
    if num == 0:
        rets[start] = min(rets[start], ct)

    if done[num]:
        return
    done[num] = 1
    
    ct += 1
    next = road[num]
    for i in next:
        dfs(start, i, ct, copy.copy(done))

for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(start, start, ct, done)

print("Yes")
for i in rets[1:]:
    print(i)

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

road = [ [] for i in range(N) ]

for ab in AB:
    road[ab[0]-1] += [ab[1]-1]
    road[ab[1]-1] += [ab[0]-1]

print(road)
rets = [N for i in range(N)]

def dfs(start, num, ct, done):
    global rets, road
    
    print(start, done, num, ct)
    if num == 0:
        rets[start] = min(rets[start], ct)

    if done[num]:
        return
    done[num] = 1
    

    
    ct += 1
    next = road[num]
    for i in next:
        dfs(start, i, ct, copy.copy(done))

for start in range(1, N):
    ct = 0
    done = [0 for i in range(N)]
    dfs(start, start, ct, done)

print("Yes")
for i in rets[1:]:
    print(i)

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

goal = 1
rets = []
road = {i:[] for i in range(1, N+1)}

for A, B in AB:
    road[A] += [B]
    road[B] += [A]

if not road[1]:
    print("No")
    exit()

retdict = {i:0 for i in range(1, N+1)}
retdict_dis = {i:1000000 for i in range(1, N+1)}

def dfs(bef, mark, ind, dis):

    global retdict, retdict_dis
    if mark[ind] == 1:
        return

    mark[ind] = 1
    if retdict_dis[ind] > dis:
        retdict[ind] = bef
        retdict_dis[ind] = dis

    bef = ind
    dis += 1

    for i in road[ind]:
        dfs(bef, dict.copy(mark), i, dis)

dfs(0, {i:0 for i in range(1, N+1)}, 1, 0)

print("Yes")
for i in range(2, N+1):
    print(retdict[i])

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

goal = 1
rets = []
road = {i:[] for i in range(1, N+1)}

for A, B in AB:
    road[A] += [B]
    road[B] += [A]

ret, retind = [], []

def dfs(ind, inds, dis, inddict):

    global goal, ret, retind

    if inddict[ind]:
        return

    inds += [ind]
    dis += 1
    inddict[ind] = 1

    if ind == goal:
        ret += [dis]
        retind += [inds]
        return

    for i in road[ind]:
        dfs(i, copy.copy(inds), dis, dict.copy(inddict))

for start in range(2, N+1):
    ret, retind = [], []
    dfs(start, [], 0, {i:0 for i in range(1, N+1)})
    if ret:
        rets += [retind[ret.index(min(ret))][1]]
    else:
        rets += [None]

ch = list(set(rets))
if len(ch) == 1 and ch[0] == None:
    print("No")
else:
    print("Yes")
    for i in rets:
        print(i)

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]

goal = 1
rets = []
road = {i:[] for i in range(1, N+1)}

for A, B in AB:
    road[A] += [B]
    road[B] += [A]

ret, retind = [], []

def dfs(ind, inds, dis):

    global goal, ret, retind

    if ind in inds:
        return

    inds += [ind]
    dis += 1

    if ind == goal:
        ret += [dis]
        retind += [inds]
        return

    for i in road[ind]:
        dfs(i, copy.copy(inds), dis)

for start in range(2, N+1):
    ret, retind = [], []
    dfs(start, [], 0)
    if ret:
        rets += [retind[ret.index(min(ret))][1]]
    else:
        rets += [None]

ch = list(set(rets))
if len(ch) == 1 and ch[0] == None:
    print("No")
else:
    print("Yes")
    for i in rets:
        print(i)

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(M)]


goal = 1
rets = []
road = {i:[] for i in range(1, N+1)}

for A, B in AB:
    road[A] += [B]
    road[B] += [A]

ret, retind = [], []

def dfs(ind, inds, dis):

    global goal, ret, retind

    if ind == goal:
        ret += [dis]
        retind += [inds]
    
    if ind in inds:
        return

    inds += [ind]
    dis += 1
    for i in road[ind]:
        dfs(i, copy.copy(inds), dis)

for start in range(2, N+1):
    ret, retind = [], []
    dfs(start, [], 0)
    rets += [retind[ret.index(min(ret))][1]]

if not rets:
    print("No")
else:
    print("Yes")
    for i in rets:
        print(i)