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:
x,y= list(map(int, input().split()))
flsg=0
hantei=[]
lis=[0]*(x-1)
a=[1]
del_list=[]
for k in range(y):
    i,j= list(map(int, input().split()))
    if i in a:
        if lis[j-2]==0:
            a.append(j)
            lis[j-2]=i
        else:
            flag=1
            break
    elif j in a:
        if lis[i-2]==0:
            a.append(i)
            lis[i-2]=j
        else:
            flag=1
            break
    else:
        hantei.append([i,j])
while flag==0 :
    for k in range(len(hantei)):
        if hantei[k]==[0,0]:
            pass
        else:
            if hantei[k][0] in a:
                if lis[(hantei[k][1])]==0:
                    a.append(hantei[k][1])
                    lis[hantei[k][1]-2]=hantei[k][0]
                    del_list.append(k)
                    hantei[k]=[0,0]
                else:
                    flag=1
                    break
            elif hantei[k][1] in a:
                if lis[(hantei[k][0])]==0:
                    a.append(hantei[k][0])
                    lis[hantei[k][0]-2]=hantei[k][1]
                    hantei[k]=[0,0]
                else:
                    flag=1
                    break

if 0 in lis:
    print("No")
else:
    print("Yes")
    for j in range(len(lis)):
        print(lis[j])

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
n,m = map(int, input().split())
a = []
b = []
for _ in range(m):
    temp_a, temp_b = map(int, input().split())
    a.append(temp_a)
    b.append(temp_b)

matrix = np.zeros((n,n))
for i in range(m):
    matrix[a[i]-1,b[i]-1] = 1
    matrix[b[i]-1,a[i]-1] = 1

result = np.zeros((n))
q = deque()
result[0] = -1

def func(num):
    q.append(1)
    while True:
        
        #print("func", num)
        
        index_list = np.where(matrix[num-1, :] == 1)[0]
        for i in range(len(index_list)):
            if result[index_list[i]] == 0:
                q.append(index_list[i]+1)
                result[index_list[i]] = num
        q.popleft()
        if len(q) == 0:
            break
        num = q[0]
    


func(1)
#print(result)
#print(matrix)
if all(result != 0):
    print("Yes")
    for i in range(1,n):
        print(int(result[i]))
else :
    print("No")

Submission status: Runtime Error

Solution code:
import queue

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

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

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

# cost to isMin
result = [[999999999999999, None, False] for i in range(n)]

# from tom
q = queue.Queue()

result[0] = [0, None, True]
for i in road[0]:
    q.put([0,i])

while not q.empty():
    n = q.get()
    if(not result[n[1]][2]):
        result[n[1]]=[result[n[0]][0]+1, n[0], True]
        for i in road[n[1]]:
            q.put([n[1], i])

flag = True
for i in result:
    if(not i[2]):
        flag = False
        break

if(flag):
    print("Yes")
    for i in range(1,len(result)):
        print(result[i][1]+1)
else:
    print("No")

Submission status: Runtime Error

Solution code:
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

l = inlt()
n = l[0]
m = l[1]

rooms = []
for i in range(n):
    rooms.append([])

for i in range(m):
    tmp = inlt()

    a = tmp[0]
    b = tmp[1]

    rooms[a-1].append(b)
    rooms[b-1].append(a)

#print(rooms)
sorted = []
ans = [0] * n
clear = [1]
while(clear):
    clear_room = clear[0]
    clear.pop(0)
    for i in range(6):
        if clear_room in rooms[i] and i not in sorted:
            ans[i] = clear_room
            sorted.append(i)
            clear.append(i)

if(len(sorted) != n):
    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.csgraph import shortest_path
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
l = [[0 for _ in range(m)] for _ in range(m)]
for _ in range(m):
  a, b = map(int, input().split())
  l[a-1][b-1] = 1
  l[b-1][a-1] = 1

csr = csr_matrix(l)
d, p = shortest_path(csr, indices=0, directed=False, unweighted=True, return_predecessors=True)
p += 1

print('Yes')
for i in p:
  if i < 0: continue
  print(i)

Submission status: Runtime Error

Solution code:
n ,m = map(int, input().split())
to = []
inside = []
ans = []
done = False
dp = [0 for i in range(m+1)]
for _ in range(m):
    f,l = map(int, input().split())
    to.append([max(f,l), min(f,l)])
to = sorted(to, key = lambda x: x[1])
for i in to:
    dp[i[0]] = dp[i[1]]+1
    dp[i[1]] = dp[i[0]]+1
for i in range(1, n):
    if(dp[i] == 0 and i > 1):
        done = True
        break
    else:
        ans.append(dp[i+1])
if(done):
    print('No')
else:
    print('Yes')
    for i in range(len(ans)):
        print(ans[i])

Submission status: Runtime Error

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

n, m = map(int, input().split())
d = np.full((n, n), np.inf)


for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = 1
    d[y][x] = 1
for i in range(n):
    d[i][i] = 0

a = np.array(d)

q, p = shortest_path(a, return_predecessors=True)


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
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
        if len(path) > 2:
            break
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


if all([i > 0 for i in q[0][1:]]):
    print('Yes')
    for i in range(1, n):
        print(get_path(i, 0, p)[1] + 1)
else:
    print('No')

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
a = []
res = [0 for i in range(n-1)]
f = False

for i in range(m):
    a1,b1 = list(map(int,input().split()))
    a.append([a1,b1])
    if a1 == 1 or b1 == 1:
        f = True

temp = [1]
temp2 = [1]

if f:
    for l in range(n):
        temp = temp2.copy()
        temp2 = []
        for j in temp:
            for p in [0,1]:
                for q in range(n):
                    if a[q][p] == j:
                        if p == 0:
                            temp2.append(a[q][1])
                        else:
                            temp2.append(a[q][0])
            for k in temp2:
                if res[k-2] == 0:
                    res[k-2] = j
        if res.count(0) == 0:
            break
    if res.count(0) == 0:    
        print("Yes")
        for i in res:
            print(i)
    else:
        print("No")
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
from scipy.sparse import csr_matrix

def get_path_row(start, goal, pred_row):
    i = goal
    cnt = 0
    while i != start and i >= 0 and cnt <= 2:
        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(1,N):
    d,p = shortest_path(graph,directed=False,return_predecessors=True,unweighted=True)
    get_path_row(0,i,p[0])

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+1,N+1),int)
for _ in range(M):
    a,b=map(int,input().split())
    graph[a,b]=1
    graph[b,a]=1




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

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

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(predecessors[n+1]+1))

Submission status: Runtime Error

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

tsuro = [list(map(int, input().split())) for _ in range(m)]

ikeru = [set() for _ in range(n+1)]

for i,j in tsuro:
    ikeru[i].add(j)
    ikeru[j].add(i)

ans = [n+5]*(n+1)
visited = [0]*(n+1)

def dfs(heya,kaiso):
    if visited[heya] != 0 and ans[heya] <= kaiso:
        return True
    else:
        visited[heya] = 1
        ans[heya] = kaiso
        for j in ikeru[heya]:
            dfs(j, kaiso+1)
        return True

hantei = True
if dfs(1,0):
    for i in range(1, n+1):
        if visited[i] == 0:
            hantei = False
    if hantei:
        print('Yes')
        for j in range(2,n+1):
            print(ans[j])
    else:
        print('No')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(9999)

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:
N,M = map(int,input().split())
way = []
for i in range(N):
    a_,b_ = map(int,input().split())
    a,b = min(a_,b_), max(a_,b_)
    way.append([a,b])

ans = [0] * N
ans[0] = 1
check = [False] * N
check[0] = True
l = [1]

inf = 10**9
for j in range(inf):
    m = []
    for k in l:
        for i in range(len(way)):
            if k in way[i]:
                numls = [j for j in way[i] if j != k]
                num = numls[0]
                if check[num-1]:
                    continue
                else:
                    m.append(num)
                    ans[num-1] = k
                    check[num-1] = True
    if m == []:
        break
    else:
        l = m

if False in check:
    print("No")
else:
    print("Yes")
    print(*ans[1:], sep="\n")

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 0 in guideposts:
    print("No")
else:
    print("Yes")
    for i in range(1,len(guideposts)):
        print(int(guideposts[i]))

Submission status: Runtime Error

Solution code:

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

def resolve():
    N, M = map(int, input().split())
    G = np.zeros((N + 1, N + 1), dtype=np.int64)

    for _ in range(M):
        x, y = map(int, input().split())
        G[x, y] += 1
        G[y, x] += 1
    csr = csr_matrix(G)
    dist, pred = dijkstra(csgraph=csr ,return_predecessors=True)

    ok = False
    for i in range(2, N+1):
        ans = get_path(i, 1, pred)
        if len(ans)<1:
            print("No")
            return
        else:
            if ok == False:
                print("Yes")
                ok = True
            print(ans[1])

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def dots(n,m,ab):
    d = {}
    for a,b in ab:
        if a in d.keys():
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d.keys():
            d[b].append(a)
        else:
            d[b] = [a]
    next_is = ['1']
    ans = {}
    for i in range(n):
        ans[str(i+1)] = 0
    while True:
        if next_is == []:
            break
        for v in next_is:
            next_is = d[v]
            # print('v: '+v)
            for next_i in next_is:
                if ans[next_i] == 0:
                    ans[next_i] = v
                # print('next: '+next_i)
                d[next_i].remove(v)

    del ans['1']
    if 0 in ans.values():
        print('No')
    else:
        print('Yes')
        for v in ans.values():
            print(v)

n, m = [int(i) for i in input().split()]
ab = []
for _ in range(m):
    ab.append(input().split())
dots(n,m,ab)

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,1)
#print(r)
#print(steps)
if len(ans) < n:
  print('No')
  #exit()
else:
  print('Yes')
  for i in range(1,n):
    print(ans[i]+1)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
class tree():
    def __init__(self):
        self.num = 0
        self.flag = 0
        self.step = -1
        self.leaf = []

li = [tree() for i in range(N)]
def saiki(que, step):
    pop = que.pop()
    li[pop].flag = 2


    for i in range(len(li[pop].leaf)):
        if li[li[pop].leaf[i]].flag == 0:
            que.append(li[pop].leaf[i])
            li[li[pop].leaf[i]].flag = 1
            if li[li[pop].leaf[i]].step != -1:
                if li[li[pop].leaf[i]].step > li[pop].step + 1:
                    li[li[pop].leaf[i]].step = li[pop].step + 1
                    li[li[pop].leaf[i]].num = pop
            else:
                li[li[pop].leaf[i]].step = li[pop].step + 1
                li[li[pop].leaf[i]].num = pop


    #print(que)
    if len(que) != 0:
        saiki(que, li[pop].step)
for i in range(M):
    A, B = map(int, input().split())
    li[A-1].leaf.append(B-1)
    li[B-1].leaf.append(A-1)

que = deque()
que.append(0)
li[0].step = 0
saiki(que, 0)
flag = 1
for i in range(len(li)):
    if li[i].flag == 0:
        flag = 0
        break
if flag == 0:
    print("No")
else:
    print("Yes")
for i in range(1, len(li)):
    print(li[i].num+1)

Submission status: Runtime Error

Solution code:
import numpy as np
import copy

N,M = (int(x) for x in input().split())

edge = np.zeros([N,N])
for i in range(M):
    e = [int(x) for x in input().split()]
    edge[e[0]-1,e[1]-1] = 1
    edge[e[1]-1,e[0]-1] = 1

sign = np.zeros(N-1)
room = np.ones(N)
room[0] = 0
n_check = 0

# edge luck
if M<N-1:
    print('No')
else:
    check = [0]
    flag = 1
    
    for i in range(N):
        if flag:
            check_ = []
                
            for c in check:
                connect = np.nonzero(edge[int(c)])[0]
                nogo = np.nonzero(room)[0]
                if len(nogo)==0:
                    flag = 0
                    break
                """
                for2 con in list(set(connect)&set(nogo)):
                    room[con] = 0
                    check_.append(con)
                    sign[con-1] = int(c+1)
                """    
                cons = np.array(list(set(connect)&set(nogo)))
                room[cons] = 0
                check_ = np.append(check_,cons)
                sign[cons-1] = cons+1
                        
                n_check += len(connect)
                if n_check>=2*M:
                    flag = 0
            if len(check_) == 0:
                flag = 0
                break
            else:
                check = copy.deepcopy(check_)
        else:
            break
    if len(np.nonzero(sign)[0]) == N-1:
        print('Yes')
        for s in sign:
            print(int(s))
    else:
        print('No')

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
li = [[] for i in range(m)]
for i in range(m):
    a, b = map(int,input().split())
    li[a-1].append(b-1)
    li[b-1].append(a-1)
sign = {0: 0}
step = {0: 0}
now = {0}

while len(now) > 0:
    next = set()
    for i in now:
        for j in li[i]:
            if not j in sign:
                sign[j] = i
                step[j] = step[i] + 1
                next.add(j)
    now.clear()
    now = next

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

Submission status: Runtime Error

Solution code:
import heapq
class Dijkstra:
    """
    使用方法

    # ゴールが設定されていなかった場合、
    # スタートから各頂点までの最短距離を格納したリストを返す
    dijkstra_result = Dijkstra(n, mp2, s - 1).execute()

    # 設定されていた場合、
    # ゴールまでの最短経路と距離を2つ返す
    dijkstra_result = Dijkstra(n, mp2, s - 1, t - 1).execute()

    # mp2の例 [[現在地, 繋がっている先の場所, 距離], [...]]
    # mp2 = [[2, 4, 2], [3, 4, 5], [3, 2, 1], [1, 3, 2], [2, 0, 8], [0, 2, 8], [1, 2, 4], [0, 1, 3]]
    """

    def __init__(self, n, mp2, start_point, goal_point=None):
        rote_map = [dict() for _ in range(n)]
        for ele in mp2:
            u, v, l = map(int, ele)
            rote_map[u-1][v-1] = l
            # 道が一方通行の場合は下の１行を消す
            rote_map[v - 1][u - 1] = l
        self.rote_map = rote_map
        self.start_point = start_point - 1
        if goal_point == None:
            self.goal_point = goal_point
        else:
            self.goal_point = goal_point - 1

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev), dist[self.goal_point]
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return [n + 1 for n in list(reversed(path))]


n, m = map(int, input().split())
mp2 =[]

for _ in range(m):
    aa, bb = map(int, input().split())
    mp2.append([aa-1, bb-1, 1])

dijkstra_result = []
for i in range(2, n+1):
    result = Dijkstra(n, mp2, i - 1, 1 - 1).execute()
    # print(result)
    dijkstra_result.append(result)

# print(dijkstra_result)
if float('inf') in dijkstra_result[1]:
    print("No")
else:
    print("Yes")
    for i in dijkstra_result:
        print(i[0][1]+1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

line = []

for i in range(m):
    line.append(list(map(int,input().split( ))))

# print(line)

line = np.array(line)

ans=[0 for i in range(n)]
target=[1]

for j in range(n):
    # print(target)
    next_target=[]
    for i in target:
        a = line[np.any(line == i, axis=1)]
        for b in list(a):
            if b[0] == i:
                c = b[1]
            else:
                c = b[0]
            if ans[c-1]==0:
                ans[c-1]=i
            next_target.append(c)
        line = line[~np.any(line == i, axis=1)]
        # print(line)
        # print(next_target)
    target = next_target
    if np.count_nonzero(np.ndarray(ans))==n-1:
        break

print('Yes')
for i in range(n-1):
    print(ans[i+1])

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
n,m = map(int, input().split())
a = []
b = []
for _ in range(m):
    temp_a, temp_b = map(int, input().split())
    a.append(temp_a)
    b.append(temp_b)

matrix = np.zeros((n,n))
for i in range(m):
    matrix[a[i]-1,b[i]-1] = 1
    matrix[b[i]-1,a[i]-1] = 1

result = np.zeros((n))
q = deque()
result[0] = -1

def func(num):
    q.append(1)
    while True:
        
        #print("func", num)
        
        index_list = np.where(matrix[num-1, :] == 1)[0]
        for i in range(len(index_list)):
            if result[index_list[i]] == 0:
                q.append(index_list[i]+1)
                result[index_list[i]] = num
        q.popleft()
        if len(q) == 0:
            break
        num = q[0]
    


func(1)
#print(result)
#print(matrix)
if all(result != 0):
    print("Yes")
    for i in range(1,n):
        print(int(result[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:
            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:
MAX_INT = 10**6
N, M = map(int, input().split())
room = dict()
for i in range(M):
    a, b = map(int, input().split())
    if room.get(a):
        room[a] += [b]
    else:
        room[a] = [b]
    if room.get(b):
        room[b] += [a]
    else:
        room[b] = [a]

dis = [MAX_INT] * (N + 1)
sign = [-1] * (N + 1)
dis[1] = 0
def sign_root(n):
    nxt = []
    for i in room[n]:
        if dis[n] + 1 < dis[i]:
            sign[i] = n
            dis[i] = dis[n] + 1
            sign_root(i)
sign_root(1)
if MAX_INT in dis[2:]:
    print("No")
else:
    print("Yes")
    for i in sign[2:]:
        print(i)

Submission status: Runtime Error

Solution code:
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]=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:
import sys
input = sys.stdin.readline


def kamban_okude(imano_room, i):
    imano_room = int(imano_room)
    global michi_to
    global kamban
    i += 1
    next_room = michi_to[imano_room]
    if next_room == []:
        return
    for element in next_room:
        next_doko(element, imano_room, i)
    return

def next_doko(element, imano_room, i):
    global kamban
    if kamban[element][0] == -1:
        kamban[element][0] = imano_room
        kamban[element][1] = i
        return(kamban_okude(element, i))
    elif  kamban[element][1]> i:
        kamban[element][0] = imano_room
        kamban[element][1] = i
        return(kamban_okude(element, i))
    else:
        return

def michi_input(m):
    michi_to = [[] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        michi_to[a].append(b)
        michi_to[b].append(a)
    return michi_to



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

INF = 1000000
kamban = [[-1, INF] for _ in range(n+1)]
kamban[1] = [1, 0]
i = 0

tf = kamban_okude(1, i)

if [-1, INF] in kamban[1:]:
    print("No")
else:
    print("Yes")
    for k in kamban[2:]:
        print(k[0])

Submission status: Runtime Error

Solution code:
import numpy as np

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

line = []

for i in range(m):
    line.append(list(map(int,input().split( ))))

# print(line)

line = np.array(line)

ans=[0 for i in range(n)]
target=[1]

for j in range(n):
    # print(target)
    next_target=[]
    for i in target:
        a = line[np.any(line == i, axis=1)]
        for b in list(a):
            if b[0] == i:
                c = b[1]
            else:
                c = b[0]
            if ans[c-1]==0:
                ans[c-1]=i
            next_target.append(c)
        line = line[~np.any(line == i, axis=1)]
        # print(line)
        # print(next_target)
    target = next_target
    if np.count_nonzero(np.ndarray(ans))==n-1:
        break

print('yes')
for i in range(n-1):
    print(ans[i+1])

Submission status: Runtime Error

Solution code:
inf = 10**6
n, m = map(int, input().split())

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

unsearched_nodes = list(range(n)) # 未探索ノード
distance = [inf] * n # ノードごとの距離のリスト
previous_nodes = [-1] * n # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = inf # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]:
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for target_node in target_edge:
        if distance[target_node] > (distance[target_min_index] + 1):
            distance[target_node] = distance[target_min_index] + 1 # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
            previous_nodes[target_node] = target_min_index #　ひとつ前に到達するノードのリストも更新

print('Yes')
for previous_node in previous_nodes[1:]:
  print(previous_node + 1)