Problem:


Score: 400 points

Problem Statement

There is a cave.

The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.

It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.

Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.

If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.

Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 2 \times 10^5

1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)

A_i \neq B_i\ (1 \leq i \leq M)

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

If there is no way to place signposts satisfying the objective, print No.

Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

If we place the signposts as described in the sample output, the following happens:

Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.

Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.

Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.

Thus, the objective is satisfied.

Sample Input 2

6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

Sample Output 2

Yes
6
5
5
1
1

If there are multiple solutions, any of them will be accepted.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    i = goal
    cnt = 0
    while i != start and i >= 0 and cnt <= 2:
        path.append(i)
        i = pred_row[i]
        cnt += 1
        if cnt == 1:
            print(i+1)
            break

N,M = map(int,input().split())
graph = np.zeros((N,N),dtype=np.int64)
for _ in range(M):
    A,B = map(int,input().split())
    A,B = A-1,B-1
    graph[A,B] = 1
    graph[B,A] = 1
#print(graph)
print("Yes")
for i in range(N):
    d,p = shortest_path(graph,directed=False,return_predecessors=True,unweighted=True)
    get_path(0,i,p)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

# AB = [list(map(int, input().split)) for _ in range(M)]

nei_L = [[] for _ in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    nei_L[a - 1].append(b - 1)
    nei_L[b - 1].append(a - 1)

ans = [-1] * N
visited = [0] * N

from collections import deque
queue = deque()

def bfs():
    queue.append(0)
    while len(queue) > 0:

        if all(visited):
            break
        now = queue.popleft()

        for c in nei_L[now]:
            if not visited[c]:
                ans[c] = now
                queue.append(c)
                visited[c] = 1

bfs()

if -1 in visited[1:]:
    print("No")
else:
    for i in range(N):
        if i == 0:
            print("Yes")
        else:
            print(ans[i] + 1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
r={}
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  #print(a,b)
  if a not in r: r[a]=[]
  r[a].append(b)
  if b not in r: r[b]=[]
  r[b].append(a)

ans = {0:0}
steps = [-1]*n
steps[0]=0
def setroot(i,step):
  newroom = [v for v in r[i] if steps[v]<0 or steps[v]>step]
  #print(i,newroom)
  if len(newroom)>0:
    for v in newroom:ans[v]=i;steps[v]=step
    for v in newroom:setroot(v,step+1)
setroot(0,0)

Submission status: Runtime Error

Solution code:
# セル3(変数のリセット)
input_count = 0

def func(i, routes, marks):
    update_rooms = []
    if i not in routes:
        return marks
    for j in routes[i]:
        room_idx = j
        if room_idx in marks:
            continue
        marks[room_idx] = i
        update_rooms.append(room_idx)
    for j in update_rooms:
        marks = func(j, routes, marks)
    return marks

def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


marks = {0:0}

N, M, routes = get_input()
marks = func(0, routes, {0: 0})
try:
    write_result(marks, N)
except:
    pass

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())

ps = [-1] * n
ps[0] = 0
tmps = {}
for _ in range(m):
    a,b=map(int,input().split())
    ai,bi=a-1,b-1
    if ai not in tmps:
        tmps[ai] = []
    tmps[ai].append(bi)
    if bi not in tmps:
        tmps[bi] = []
    tmps[bi].append(ai)

# print(tmps)

if 0 not in tmps:
    print("No")
    exit()


def puts(ks):
    nks = []
    for k in ks:
        _nks = tmps[k]
        for nk in _nks:
            if ps[nk] == -1:
                ps[nk] = k
                nks.append(nk)
        # print(k, ps)
    if nks == []:
        return
    # print(ks, ps)
    puts(nks)  
ks = [0]
puts(ks)

# print(ps)

if -1 in ps:
    print("No")
    exit()

print("Yes")
for p in ps[1:]:
    print(p+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
n, m = map(int,input().split())
mark = [-2] * (n-1)
dist = [0] * (n-1)
path = [[] for _ in range(n-1)]
path0 = []

def search(i):
    d = dist[i]
    for p in path[i]:
        if dist[p] > d or dist[p] == 0:
            dist[p] = d + 1
            mark[p] = i
            search(p)

for _ in range(m):
    a, b = map(lambda x: int(x)-2, input().split())
    if a == -1:
        path0.append(b)
        dist[b] = 1
        mark[b] = -1
    elif b == -1:
        path0.append(a)
        dist[a] = 1
        mark[a] = -1
    else:
        path[a].append(b)
        path[b].append(a)

for p in path0:
    search(p)

if mark.count(-2) > 0:
    print("No")
else:
    print("Yes")
    for i in mark: print(i+2)

Submission status: Runtime Error

Solution code:
N,M=list(map(int,input().split()))

g=[[] for i in range(M+1)]

for i in range(M):
	a,b=list(map(int,input().split()))
	g[a].append(b)
	g[b].append(a)

from collections import deque

queue = deque([1])
d = [None] * (N+1)
d[1] = 0
while queue:
	v = queue.popleft()
	for i in g[v]:
		if d[i] is None:
			d[i] = v
			queue.append(i)

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

Submission status: Runtime Error

Solution code:
[n,m]=list(map(int,input().split()))
ab=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

chizu=[[] for i in range(n+1)]
ans=[0]*(n+1)
ans[1]=-1

for i in range(m):
    chizu[ab[i][0]].append(ab[i][1])
    chizu[ab[i][1]].append(ab[i][0])

kaisu=[chizu[1]]
for i in chizu[1]:
    ans[i]=1

j=-1
counter=len(chizu[1])
while True:
    j+=1
    for now in kaisu[j]:#スタートからj距離の点たちについて操作
        kari=[]
        for i in chizu[now]:#ある点から隣り合う点決めていく
           if ans[i]==0:
                ans[i]=now
                kari.append(ans[i])
                counter+=1
        kaisu.append(kari)
    if counter==n-1:
        break

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

Submission status: Runtime Error

Solution code:


def func(i, routes, marks):
    update_rooms = []
    if i not in routes:
        return marks
    for j in routes[i]:
        room_idx = j
        if room_idx in marks:
            continue
        marks[room_idx] = i
        update_rooms.append(room_idx)
    for j in update_rooms:
        marks = func(j, routes, marks)
    return marks

def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


marks = {0:0}

N, M, routes = get_input()
    marks = func(0, routes, {0: 0})
try:
    write_result(marks, N)
except:
    pass

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    data[a - 1].append(b - 1)
    data[b - 1].append(a - 1)

ans = [0] * (n - 1)

def bfs(i, queue, p):
    q = []
    if len(queue) == 0:
        return 
    while len(queue) > 0:
        x = queue.pop(0)
        pre = p.pop(0)
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                q.append(data[x[j]])
                p.append(x[j])
        bfs(x[j], q, p)

queue = []
pre = [0]
queue.append(data[0])
bfs(0, queue, pre)

if 0 not in ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")

Submission status: Runtime Error

Solution code:
import math
import sys

def rec(rooms, num, distance):
    for roomnum in rooms[num]:
        if roomnum not in shirube or distance + 1 < shirube[roomnum][1]:
            shirube[roomnum] = (num, distance + 1)
            rec(rooms, roomnum, distance + 1)
            

N, M = map(int,input().split())

rooms = {}

for cor in [tuple(map(int,input().split())) for i in range(M)]:
    rooms.setdefault(cor[0], set())
    rooms[cor[0]].add(cor[1])
    rooms.setdefault(cor[1], set())
    rooms[cor[1]].add(cor[0])

shirube = {}
shirube[1] = (0, 0)

rec(rooms, 1, 0)

if any([i not in shirube for i in range(2, N+1)]):
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(shirube[i][0])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

# AB = [list(map(int, input().split)) for _ in range(M)]

nei_L = [[] for _ in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    nei_L[a - 1].append(b - 1)
    nei_L[b - 1].append(a - 1)

ans = [-1] * N
visited = [0] * N
cost = [0] * N

from collections import deque
queue = deque()

def bfs():
    queue.append(0)

    while len(queue) > 0:

        if all(visited):
            break
        now = queue.popleft()

        for c in nei_L[now]:
            if not visited[c]:
                ans[c] = now
                queue.append(c)
                cost[c] = cost[now] + 1
                visited[c] = 1

bfs()

if -1 in visited[1:]:
    print("No")
else:
    for i in range(N):
        if i == 0:
            print("Yes")
        else:
            print(ans[i] + 1)

Submission status: Runtime Error

Solution code:
def count(d,n,s,c):
    if(s[n-1]==1):
        return None
    s[n-1] = 1
    c += 1
    for i in d[n-1]:
        if(i==1):
            return c
        q = count(d,i,s,c)
        if(q!=None):
            return q

d = []
n, m = input().split()
n = int(n)
m = int(m)
for i in range(n):
    d.append([])
for i in range(m):
    a, b = input().split()
    a = int(a)
    b = int(b)
    d[a-1].append(b)
    d[b-1].append(a)

#print(d)
flag = True
w = []
for i in range(2,n+1):
    s = [0]*n
    num = count(d,i,s,0)
    #print(num)
    if(num==None):
        flag = False
        break
    else:
        w.append(num)

if(flag):
    print("Yes")
    for i in w:
        print(i)
else:
    print("No")

Submission status: Runtime Error

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
for _ in range(m):
    x = sys.stdin.readline()
    g.add_edge(int(x[0]), int(x[2]))
l=[None]*(n-1)
for i in range(2,n+1):
    l[i-2] = nx.shortest_path(g, source=1, target=i)[-2]
if None in l:
    print("No")
else:
    print("Yes")
    for x in l:
        print(x)

Submission status: Runtime Error

Solution code:
import copy

def cape(iri):
    ima = set()
    for i in iri:
        for j in root[i]:
#            print(i, j)
            if ans[j] == 0:
                ans[j] = i
                root[j] -= {i}
                ima = ima | {j}
    if ima != set():
        cape(ima)

N, M = map(int, input().split())
root = [set() for i in range(N + 1)]
ans = [0 for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    root[a].add(b)
    root[b].add(a)
#print(root)
cape({1})
#print(ans)
print("Yes")
for i in range(2, N + 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n,w = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    cost[x][y] = 1
    cost[y][x] = 1
d = dijkstra(0,n,w,cost)
print('Yes')
for i in range(1, len(d)):
    print(d[i])

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=list(map(int,input().split()))

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

guideposts_cost=np.array([float("inf")]*N*N).reshape(N,N)
guideposts=[0]*N

for i,g in enumerate (guideposts_cost):
    g[i]=0

# print(guideposts_cost)

for ab in AB:
    old_guideposts_cost=guideposts_cost.copy()
    guideposts_cost[ab[0]-1]=np.minimum(guideposts_cost[ab[0]-1],guideposts_cost[ab[1]-1]+1)
    guideposts_cost[ab[1]-1]=np.minimum(guideposts_cost[ab[1]-1],guideposts_cost[ab[0]-1]+1)
    if guideposts_cost[ab[0]-1][0]!=old_guideposts_cost[ab[0]-1][0]:
        guideposts[ab[0]-1]=ab[1]
    if guideposts_cost[ab[1]-1][0]!=old_guideposts_cost[ab[1]-1][0]:
        guideposts[ab[1]-1]=ab[0]
    # print(guideposts_cost)
    # print(old_guideposts_cost)

for ab in AB:
    old_guideposts_cost=guideposts_cost.copy()
    guideposts_cost[ab[0]-1]=np.minimum(guideposts_cost[ab[0]-1],guideposts_cost[ab[1]-1]+1)
    guideposts_cost[ab[1]-1]=np.minimum(guideposts_cost[ab[1]-1],guideposts_cost[ab[0]-1]+1)
    if guideposts_cost[ab[0]-1][0]!=old_guideposts_cost[ab[0]-1][0]:
        guideposts[ab[0]-1]=ab[1]
    if guideposts_cost[ab[1]-1][0]!=old_guideposts_cost[ab[1]-1][0]:
        guideposts[ab[1]-1]=ab[0]
    # print(guideposts_cost)

# print(guideposts_cost)

if list(filter(lambda x: x[0]==float("inf"),guideposts_cost))!=[]:
    print("No")
else:
    print("Yes")
    for i in range(1,len(guideposts)):
        print(int(guideposts[i]))

Submission status: Runtime Error

Solution code:
#168
#d
n,m = map(int, input().split())# n = 　部屋数, m = 通路数
ln = [[0] for i in range(n+1)] #  部屋i が繋がる部屋はln[i] に示される
line = [0 for i in range(n-1)] # 1~nの印 部屋i の印はline[i-2]
for k in range(m):
    i,j  = map(int, input().split())
    ln[i].append(j)
    ln[j].append(i)

hy = [1]
while min(line) == 0 :
    new_hy = []
    for i in hy:
        for j in ln[i]:
            if line[j-2] == 0:
                line[j-2] = i
            new_hy.append(j)
            
    hy = set(new_hy)
    hy = list(new_hy)
    
print('Yes')            
for i in line:
    print(i)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

# AB = [list(map(int, input().split)) for _ in range(M)]

nei_L = [[] for _ in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    nei_L[a - 1].append(b - 1)
    nei_L[b - 1].append(a - 1)

ans = [-1] * N
visited = [0] * N
cost = [0] * N

from collections import deque
queue = deque()

def bfs():
    queue.append(0)

    while len(queue) > 0:

        if all(visited):
            break
        now = queue.popleft()

        for c in nei_L[now]:
            if not visited[c]:
                ans[c] = now
                queue.append(c)
                cost[c] = cost[now] + 1
                visited[c] = 1

bfs()
print(ans)

if -1 in visited[1:]:
    print("No")
else:
    for i in range(N):
        if i == 0:
            print("Yes")
        else:
            print(ans[i] + 1)

Submission status: Runtime Error

Solution code:
def dfs(x,N,M,michi,sumi,cnt):
	cnt+=1
	for i in range(M):
		for h in range(2):
			if michi[i][h]==x:
				if michi[i][1-h]!=1 and (sumi[michi[i][1-h]][0]==0 or sumi[michi[i][1-h]][1]>=cnt):
					sumi[michi[i][1-h]][0]=michi[i][h]
					sumi[michi[i][1-h]][1]=cnt
					dfs(michi[i][1-h],N,M,michi,sumi,cnt)

N,M=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(M)]
cnt=0
ls=[[0,0] for _ in range(N+1)]
dfs(1,N,M,AB,ls,cnt)

if all(ls[i][0]>=1 for i in range(2,N+1)):
	print("Yes")
	for i in range(2,N+1):
		print(ls[i][0])

else:
	print("No")

Submission status: Runtime Error

Solution code:
N, M = map( int, input("").split(" "))

result ={}


paths={}
for i in range(N):
    paths[i+1] = []

for i in range(M):
    A, B = map( int ,input("").split(" "))
    if( B!=1):
        paths[A].append(B)
    if( A!=1):
        paths[B].append(A)


def search( fid, cnt):
    idss = paths[fid]
    for ids in idss:
        if( ids in result.keys()):
            if( result[ids][0] <= cnt ):
                continue
        result[ids]=[cnt,fid]
        search( ids, cnt+1 )

search(1,1)

err_flg = 0
for i in range(2,N+1):
    if( not (i in result.keys())):
        err_flg = 1
        break

if(err_flg == 1):
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(result[i][1])

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = [int(i) for i in input().split()]

e = np.zeros([n,n])



for _ in range(m):
    a, b = [int(i) for i in input().split()]
    e[a-1,b-1] = b-1
    e[b-1,a-1] = a-1

ans = np.ones(n-1)
next_cand = [0]
cout = 0
check = np.zeros(n-1)
for next_ in next_cand:
    if cout == n-1:
        break
    connec = np.nonzero(e[next_,:])

    for i in connec[0]:

        i = int(i)
        if check[i-1] == 0:
            check[i-1] = 1
            cout +=1
            ans[i-1] = next_ +1
            next_cand.append(i)
            e[next_,:] = 0
            e[:,next_] = 0
            cout += 1
            if cout == n-1:
                break


print('Yes')

for i in ans:
    print(int(i))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    cnt = 0
    while i != start and i >= 0 and cnt <= 2:
        path.append(i)
        i = pred_row[i]
        cnt += 1
        if cnt == 1:
            print(i+1)
            break
    if i < 0:
        return []
    path.append(i)
    return path

N,M = map(int,input().split())
graph = np.zeros((N,N),dtype=np.int64)
for _ in range(M):
    A,B = map(int,input().split())
    A,B = A-1,B-1
    graph[A,B] = 1
    graph[B,A] = 1
#print(graph)
print("Yes")
result = shortest_path(graph)
result = floyd_warshall(graph)
for i in range(N):
    d,p = shortest_path(graph,directed=False,return_predecessors=True,unweighted=True)
    get_path(0,i,p)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
r={}
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  #print(a,b)
  if a not in r: r[a]=[]
  r[a].append(b)
  if b not in r: r[b]=[]
  r[b].append(a)

ans = {0:0}
steps = [-1]*n
steps[0]=0
def setroot(i,step):
  newroom = [v for v in r[i] if steps[v]<0 or steps[v]>step]
  #print(i,newroom)
  if len(newroom)>0:
    for v in newroom:ans[v]=i;steps[v]=step
    for v in newroom:setroot(v,step+1)
setroot(0,0)
#print(r)
#print(steps)
if len(ans) < n:
  print('No')
  exit()
print('Yes')
for i in range(1,n):
  print(ans[i]+1)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().strip().split()))

root = {}
for i in range(M):
  A, B = list(map(int, input().strip().split()))
  if A not in root:
    root[A] = set()
  root[A].add(B)  
  if B not in root:
    root[B] = set()
  root[B].add(A)
    
#print(root)

if 1 not in root or len(root) != N:
  print('No')
else:
  A = {}
  A[1] = 0
  current = 1
  last = 0
  while True:
    print(f'{current=}')
    print(A)
    for r in root[current]:
      if r not in A:
        A[r] = current
        last = r
    current = last
    if len(A) == N:
      break

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

Submission status: Runtime Error

Solution code:

def func(i, routes, marks):
    update_rooms = []
    if i not in routes:
        return marks
    for j in routes[i]:
        room_idx = j
        if room_idx in marks:
            continue
        marks[room_idx] = i
        update_rooms.append(room_idx)
    for j in update_rooms:
        marks = func(j, routes, marks)
    return marks

def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy

N, M, routes = get_input()

marks = {0:0}

marks = func(0, routes, {0: 0})
write_result(marks, N)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
room = []
ans = []
for i in range(1,n):
  room.append([i,i])
  ans.append(0)
room.append(n)
ab = []
for i in range(m):
  a,b = map(int,input().split())
  ab.append([min(a,b)-1,max(a,b)-1])
ab.sort()
for i in range(len(ab)):
  if(room[ab[i][0]][1]==1):
    ans[ab[i][1]]=room[ab[i][0]][0]
    room[ab[i][1]][1]==1
judge = 0
for i in range(n):
  if(room[i][1]==1):
    None
  else:
    judge = 1
    break
if(judge==0):
  print("Yes")
  for i in range(len(ans)):
    print(len(i))
else:
  print("No")

Submission status: Runtime Error

Solution code:
from queue import Queue
import sys

sys.setrecursionlimit(10 ** 6)

def main():
  n, m = map(int, input().split())

  edges = [[] for _ in range(m)]

  for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    edges[a].append(b)
    edges[b].append(a)

  visited = {0: -1}

  q = Queue()
  q.put(0)

  while not q.empty():
    current = q.get()
    for nxt in edges[current]:
      if nxt not in visited:
        visited[nxt] = current
        q.put(nxt)

  if len(visited) == n:
    print("Yes")
    for i in range(1, n):
      print(visited[i] + 1)
  else:
    print("No")


main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

to = [[] for _ in range(110000)]
ans = [0] * 110000
queue = []
passed = [0] * 110000
passed[1] = 1

def search(i):
  global queue
  global passed
  global ans
  for j in to[i]:
    if passed[j] == 0:
      queue.append(j)
      passed[j] = 1
      ans[j] = i
  if queue:
    return search(queue.pop(0))
  


for _ in range(m):
  a, b = map(int, input().split())
  to[a].append(b)
  to[b].append(a)

search(1)

print("Yes")
for i in ans[2:n + 1]:
  print(i)

Submission status: Runtime Error

Solution code:
import math
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

next = [1]
reached = {0:-1}
fromnode = {}

N,M = nm()
# print(N,M)
tunnel = [{} for i in range(N+1)]
# print(tunnel)
for _ in range(M):
    a,b = nm()
    # print(a,b)
    tunnel[a][b] = 1
    tunnel[b][a] = 1
# print(tunnel)

d = 0
while len(next) != 0:
    # print(d,next,reached,fromnode)
    now = next
    next = []
    for node in now:
        reached[node] = d

    for node in now:
        for nn in tunnel[node]:
            # print('check',nn)
            if not (nn in reached):
                fromnode[nn] = node
                next.append(nn)
                del tunnel[nn][node]
    d += 1

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

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
if __name__ == '__main__':    
    N, M = map(int, input().split())
    p = np.zeros((N, N))
    for m in range(M):
        A, B = map(int, input().split())
        p[A-1, B-1] = 1
        p[B-1, A-1] = 1
    csr = csr_matrix(p)
    mat, predecessors = shortest_path(csr, directed=False, indices=0, return_predecessors=True)
    if -9999 in predecessors[1:]:
        print('No')
    else:
        print('Yes')
        for n in range(N-1):
            print(int(mat[n+1]))

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
p = [[] for x in range(n)]
r = [-2] + [-1] * (n - 1)
for _ in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    p[a].append(b)
    p[b].append(a)
def bfs(room):
    global r
    l = []
    for iroom in p[room]:
        if r[iroom] == -1:
            r[iroom] = room
            l.append(iroom)
    for iroom in l:
        bfs(iroom)
bfs(0)

if -1 in r:
    print('No')
else:
    print('Yes')
    for i in r[1:]:
        print(i+1)

Submission status: Runtime Error

Solution code:
import sys
import networkx as nx
n,m=map(int,input().split())
g = nx.Graph()
for _ in range(m):
    x = sys.stdin.readline()
    g.add_edge(int(x[0]),int(x[2]))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
r={}
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  #print(a,b)
  if a not in r: r[a]=[]
  r[a].append(b)
  if b not in r: r[b]=[]
  r[b].append(a)

ans = {0:0}
steps = [m+1]*n
steps[0]=0
def setroot(i,step):
  newroom = [v for v in r[i] if steps[v]>step]
  #print(i,newroom)
  if len(newroom)>0:
    for v in newroom:ans[v]=i;steps[v]=step
    for v in newroom:setroot(v,step+1)
setroot(0,0)
#print(r)
#print(steps)
if len(ans) < n:
  print('No')
  exit()
print('Yes')
for i in range(1,n):
  print(ans[i]+1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
path = list(list(map(int, input().split())) for _ in range(m))

dic = dict()
for i in range(m):
    p = path[i]
    if p[0] not in dic:
        dic[p[0]] = [p[1]]
    else:
        dic[p[0]].append(p[1])
    if p[1] not in dic:
        dic[p[1]] = [p[0]]
    else:
        dic[p[1]].append(p[0])
        
table = [0]*n
sign = [0]*n

def bfs(k):
    for i in dic[k]:
        if table[i-1] == 0 and i != 1:
            table[i-1] = table[k-1] + 1
            sign[i-1] = k
        elif table[k-1] + 1 < table[i-1]:
            table[i-1] = table[k-1] + 1
            sign[i-1] = k
        else:
            continue
        bfs(i)
    return

bfs(1)

print("Yes")
for i in range(n-1):
    print(sign[i+1])

Submission status: Runtime Error

Solution code:
def saiki(visited, inv, path, nows):
  buf = []
  for now in nows:
    for p in path[now]:
      if p not in visited:
        buf.append(p)
        visited.append(p)
        inv[p-2]=now
  if len(buf)==0:
    return
  saiki(visited, inv, path, buf)
  
N, M = map(int, input().split())

inv = [i for i in range(N-1)]
visited = [1]

path = {i :[] for i in range(1, N+1)}
for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
saiki(visited, inv, path, [1])
print("Yes")
for i in inv:
  print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())
R = [[] for _ in range(N)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for _ in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(que):
    if que==[]:
        return
    i = que[0]
    for j in R[i-1]:
        if ans[j-1]!=0:
            continue
        else:
            ans[j-1]=i
            que.append(j)
    que.pop(0)
    bfs(que)
    
bfs(queue)
if len(ans[ans==0])>0:
    print('No')
else:
    print('Yes')
    for i in range(1,N):
        print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


N,M = map(int,input().split())
graph=np.zeros((N,N),int)
for _ in range(M):
    a,b=map(int,input().split())
    graph[a-1,b-1]=1
    graph[b-1,a-1]=1




graph = csr_matrix(graph)
dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, indices=0, return_predecessors=True)

if np.count_nonzero(dist_matrix >N)==0:
    ans=predecessors[1:]
    print("Yes")
    for a in ans:
        print(a+1)
else:
    print("No")

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

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

mat=np.zeros((n,n))
for i in range(m):
    a,b = map(int,input().split())
    mat[a-1,b-1]=1
    mat[b-1,a-1]=1

sp=shortest_path(mat,unweighted=True,directed=False,return_predecessors=True)[1][0]

print('Yes')
sp+=1
for i in range(1,len(sp)):
    print(sp[i])