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:
# coding: utf-8
# Your code here!

import numpy as np
n,m = map(int,input().rstrip().split())
connection_map = np.zeros((n+1,n+1),int)
for _ in range(m):
    r = list(map(int,input().rstrip().split()))
    connection_map[r[0]][r[1]] = 1
    connection_map[r[1]][r[0]] = 1
mask = [-1 for _ in range(n+1)]
mask[0] = 0 # dummy
mask[1] = 1

search_list = [1]
while 1:
    while len(search_list) > 0:
        pivot = search_list.pop(0)
        connect = np.where(connection_map[pivot]>0)[0].tolist()
        for c in connect:
            if mask[c] < 0:
                mask[c] = pivot
                search_list.append(c)
    if -1 in mask:
        pass
    else:
        break
print('Yes')
for i in range(2,n+1):
    print(mask[i])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

import numpy as np
n,m = map(int,input().rstrip().split())
connection_map = np.zeros((n+1,n+1),int)
for _ in range(m):
    r = list(map(int,input().rstrip().split()))
    connection_map[r[0]][r[1]] = 1
    connection_map[r[1]][r[0]] = 1
mask = [-1 for _ in range(n+1)]
mask[0] = 0 # dummy
mask[1] = 1

search_list = [1]
while 1:
    while len(search_list) > 0:
        pivot = search_list.pop(0)
        connect = np.where(connection_map[pivot]>0)[0].tolist()
        for c in connect:
            if mask[c] < 0:
                mask[c] = pivot
                search_list.append(c)
    if -1 in mask:
        pass
    else:
        break
#print(mask)
print('yes')
for i in range(2,n+1):
    print(mask[i])

Submission status: Runtime Error

Solution code:
from collections import deque
INF = 10000000
N, M = map(int, input().split())
# 隣接リストを作成する
dist = [INF for _ in range(M)]
pre = [-1 for _ in range(M)]
to = [[] for _ in range(100005)] 

# 隣接リスト：to[v]の中にはvに隣接している要素が入っている
for i in range(M):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    to[a].append(b)
    to[b].append(a)

queue = deque()
dist[0] = 0
queue.append(0)
while(len(queue) != 0):
    v = queue.popleft()
    for u in to[v]:
        # もう値が設定されていれば更新しない
        if (dist[u] != INF):
            continue
        dist[u] = dist[v] + 1
        pre[u] = v
        queue.append(u)

print("Yes")
for i in range(N):
    if (i == 0):
        continue
    ans = pre[i]
    ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N,M = map(int, input().split())
root = []
for i in range(M):
  tmp = list(map(int, input().split()))
  root.append(tmp)

visited = np.zeros(N)
Q = []				# キューを格納するための箱
visited[0] = 1		# 訪問済み
Q.append(1)			# 探索する要素を追加
while len(Q) != 0:
  q = Q.pop(0)
  for i in range(len(root)):
    del_idx = []
    if (q in root[i] and visited[root[i][0]-1] == 0) or (q in root[i] and visited[root[i][1]-1] == 0):
      if root[i][0] == q:	
        visited[root[i][1]-1] = q
        Q.append(root[i][1])
        del_idx.append(i)
      elif root[i][1] == q:	
        visited[root[i][0]-1] = q
        Q.append(root[i][0])
        del_idx.append(i)
  for i in range(len(del_idx)):
    del root[i]
if sum(visited) != 1:
  print('Yes')
  for i in range(1,N,1):
    print(int(visited[i]))
else:
  print('No')

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
A=[0]*(H);p=0;mm=100000
for i in range(H):
  A[i]=list(map(int,input().split()))
#print(A)
for i in range(H):
  for j in range(W):
    #print(i,j,mm)
    for h in range(H):
      for w in range(W):
        if A[h][w]!=0:
          p=p+min(abs(i-h),abs(j-w))
    if mm>p:
      mm=p
      I=i;J=j
    p=0
#print(mm,I,J)
print(mm)"""

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import deque
import numpy as np

N,M = map(int,input().split())
AB = [[] for _ in range(M+1)]
for i in range(0,M):
    Ai,Bi = map(int,input().split())
    AB[Ai].append(Bi)
    AB[Bi].append(Ai)

ans = [0]*(N+1)
ans[1] = 1

d = deque([])
d.append(1)

while len(d)>0:
    Now = d.popleft()

    for i in AB[Now]:
        if ans[i] == 0:
            ans[i] = Now
            d.append(i)

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

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = map(int,input().split())
def vertex_node()  -> list:
    v_c = [[] for _ in range(n+1)]
    v = [i.split() for i in q.split("\n")]
    for i in range(m):
        a,b = map(int,input().split())
        v_c[a].append(b)
        v_c[b].append(a)
    return v_c

def bfs(l) -> list:
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0
    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        for i in l[v]:
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
    return dist
if __name__ == "__main__":
    i = vertex_node()
    ans = bfs(i)[2:]
    print(*ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import deque
import numpy as np

N,M = map(int,input().split())
AB = np.zeros((N,N))
for i in range(0,M):
    Ai,Bi = map(int,input().split())
    AB[Ai-1,Bi-1] = 1
    AB[Bi-1,Ai-1] = 1 # 転置
#[list(map(int,input().split())) for x in range(0,M)]

ans = [0]*(N+1)
ans[1] = 1

d = deque([])
d.append(1)

while len(d)>0:
    Now = d.popleft()

    for i in range(0,N):
        if AB[Now-1,i] != 0:
            if ans[i+1] == 0:
                ans[i+1] = Now
                d.append(i+1)

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

Submission status: Runtime Error

Solution code:
import collections

N, M = map(int, input().split())
adj = collections.defaultdict(set)
for m in range(M):
    A, B = map(int, input().split())
    adj[A].add(B)
    adj[B].add(A)

visited = [False] * (N + 1)
posts = [float("inf")] * (N + 1)

def dfs(n, dep):
    posts[n] = min(dep, posts[n])
    if visited[n]:
        return
    visited[n] = True
    for m in adj[n]:
        dfs(m, dep + 1)

dfs(1, 0)

for i in range(1, N + 1):
    if posts[i] == float("inf"):
        print("No")
        break
else:
  print("Yes")
  print("\n".join(str(s) for s in posts[2:]))

Submission status: Runtime Error

Solution code:
import collections

N, M = map(int, input().split())
adj = collections.defaultdict(set)
for m in range(M):
    A, B = map(int, input().split())
    adj[A].add(B)
    adj[B].add(A)

visited = [False] * (N + 1)
posts = [float("inf")] * (N + 1)

def dfs(n, dep):
    posts[n] = min(dep, posts[n])
    if visited[n]:
        return
    visited[n] = True
    for m in adj[n]:
        dfs(m, dep + 1)

dfs(1, 0)

for i in range(1, N + 1):
    if posts[i] == float("inf"):
        print("No")
        break
else:
   print("Yes")
   print("\n".join(str(s) for s in posts[2:]))

Submission status: Runtime Error

Solution code:
import math

def solve():
    ans = [-1 for i in range(n+1)]
    remaining = set(range(1, n+1))
    remaining.remove(1)
    last_visited = [1]
    last_visited2 = []
    c = 0
    while remaining:
        print(remaining)
        for r in last_visited:
            for ad in adj[r]:
                if ad in remaining:
                    last_visited2.append(ad)
                    remaining.remove(ad)
                    ans[ad] = r
        last_visited = last_visited2
        last_visited2 = []
        c += 1
    if -1 in ans[2:]:
        print("No")
        return
    print("Yes")
    for i in ans[2:]:
        print(i)
    return

n, m = [int(ii) for ii in input().split()]
adj = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = [int(ii) for ii in input().split()]
    adj[a].append(b)
    adj[b].append(a)
solve()

Submission status: Runtime Error

Solution code:
from typing import List
N, M = map(int, input().split())
graph:List[List[int]] = [[] for _ in range(N)]
for _ in range(N):
    a,b = map(lambda x : int(x) -1 , input().split())
    graph[a].append(b)
    graph[b].append(a)
prev = [-1]*N
prev[0] = 0
import queue
qu = queue.Queue()
qu.put(0)
while not qu.empty():
    top = qu.get()
    for nxt in graph[top]:
        if prev[nxt] == -1:
            prev[nxt] = top
            qu.put(nxt)
if all(x != -1 for x in prev[1:]):
    print("Yes")
    print("\n".join(map(lambda x : str(x+1), prev[1:])))
else :
    print("No")

Submission status: Runtime Error

Solution code:
from typing import List
N, M = map(int, input().split())
graph:List[List[int]] = [[] for _ in range(N)]
for _ in range(N):
    a,b = map(lambda x : int(x) -1 , input().split())
    graph[a].append(b)
    graph[b].append(a)
prev = [-1]*N
prev[0] = 0
import queue
qu = queue.Queue()
qu.put(0)
while not qu.empty():
    top = qu.get()
    for nxt in graph[top]:
        if prev[nxt] == -1:
            prev[nxt] = top
            qu.put(nxt)
if all(x != -1 for x in prev[1:]):
    print("\n".join(map(lambda x : str(x+1), prev[1:])))
else :
    print("no")

Submission status: Runtime Error

Solution code:
from networkx import Graph,predecessor
import matplotlib.pyplot as plt
#import networkx as nx

G = Graph() #無効グラフ生成
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
G.add_edges_from(ab) #辺リスト生成
preds = predecessor(G,source=1)  #sourceはstart node
print("Yes")
for i in range(2,n+1):
    print(preds[i][0])

#描画

Submission status: Runtime Error

Solution code:
#https://docs.pyq.jp/python/math_opt/graph.html
from networkx import Graph,predecessor
import matplotlib.pyplot as plt
import networkx as nx

G = Graph() #無効グラフ生成
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
G.add_edges_from(ab) #辺リスト生成
preds = predecessor(G,source=1)  #sourceはstart node
print("Yes")
for i in range(2,n+1):
    print(preds[i][0])

#描画
#nx.draw_networkx(G)
#plt.show()

Submission status: Runtime Error

Solution code:
from networkx import Graph,predecessor
import matplotlib.pyplot as plt
import networkx as nx

G = Graph() #無効グラフ生成
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
G.add_edges_from(ab) #辺リスト生成
preds = predecessor(G,source=1)  #sourceはstart node
print(preds)
print("Yes")
for i in range(2,n+1):
    print(preds[i][0])

#描画
#nx.draw_networkx(G)
#plt.show()

Submission status: Runtime Error

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
l=[0]*N
que=deque([])
que.append(1)
bfs():
  while que:
     if 0 not in l:
         exit()
    p=que.popleft
      for i in range(M):
          if ab[i][0]==p:
            que.append(ab[i][1])
             l[ab[i][1]-1]=p
          if ab[i][1]==p:
             que.append(ab[i][0])
              l[ab[i][0]-1]=p
  print("Yes")
  print(*l)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
l=[0]*N
que=deque([])
que.append(1)
def bfs():
	while que:
  		if 0 not in l:
    		exit()
  		p=que.popleft
  		for i in range(M):
    		if ab[i][0]==p:
      			que.append(ab[i][1])
      			l[ab[i][1]-1]=p
    		if ab[i][1]==p:
      			que.append(ab[i][0])
      			l[ab[i][0]-1]=p
	print("Yes")
	print(*l)
bfs()

Submission status: Runtime Error

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
l=[0]*N
que=deque([])
que.append(1)
def bfs()
	while que:
  		if 0 not in l:
    		exit()
  		p=que.popleft
  		for i in range(M):
    		if ab[i][0]==p:
      			que.append(ab[i][1])
      			l[ab[i][1]-1]=p
    		if ab[i][1]==p:
      			que.append(ab[i][0])
      			l[ab[i][0]-1]=p
	print("Yes")
	print(*l)
bfs()

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())

p = [0] * (n+1)
a = [0] * m
b = [0] * m


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

s=list()
t=list()
t.append(1)


while(1):
    for j in t:
        for k in range(m):
            if a[k]==j and p[b[k]] == 0:
                p[b[k]]=a[k]
                s.append(b[k])

            if b[k]==j and p[a[k]]==0:
                p[a[k]]=b[k]
                s.append(a[k])
                

    if len(s)==0:
        break
    else:
        t = s
        s = []
    
if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)

Submission status: Runtime Error

Solution code:
import numpy as np

N,M = map(int,input().split())
vector = np.zeros((N,N), dtype='int8')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
l = []
v = [-1]*M
v_old = v[:]
v[0] = 0
#print(v_old)
#print(v)
for i in range(M):
  a, b = list(map(int, input().strip().split()))
  if a > b:
    c = a
    a = b
    b = c
  l.append([a, b])
  #print(a, b)
l.sort()

count = 0
while v != v_old:
  v_old = v[:]
  #print(count)
  count = count + 1
  for i in range(M):
    room_1 = l[i][0] -1
    room_2 = l[i][1] -1
    if v[room_2] == -1:
      if v[room_1] == -1:
        pass
      else:
        v[room_2] = v[room_1] + 1
    elif v[room_1] < v[room_2]:
      v[room_2] = v[room_1] + 1
    elif v[room_1] > v[room_2]:
      v[room_1] = v[room_2] + 1
#print(l)
#print(v)
print('Yes')
for i in v:
  if i != 0:
    print(i)

Submission status: Runtime Error

Solution code:
import collections
import itertools
N, M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

ans_list = [0] * (N+1)

dq = collections.deque()

dq.append(1)

for hoge in range(500000)
    i = dq.popleft()
    iList = [temp for temp in ABs if i in temp]

    iList = list(itertools.chain.from_iterable(iList))
    iList = [temp for temp in iList if iList !=i]

    for hoge in iList:
        if(ans_list[hoge] == 0):
            ans_list[hoge] = i
        dq.append(hoge)

    if(0 not in ans_list[2:]):
        break

for ans in ans_list[2:]:
    print(ans)

Submission status: Runtime Error

Solution code:
# d
import numpy as np
n, m = [int(i) for i in input().split()]
a = np.array([0]*m)
b = np.array([0]*m)
ans = np.array([0]*(n))
count =  np.array([0]*n)
roop = 0
Checks =  np.array([0]) # チェックする部屋の番号
Next =  np.array([]) # 次チェックする部屋番号をリストアップする
Li = np.array([1]*n)
for i in range(m):
    a[i], b[i] = [int(j)-1 for j in input().split()]

# 入力の受け取り完了
while np.sum(Li) != 0:
    roop += 1
    for check in Checks:
        if np.any(a == check):
            ind = np.where(a == check)
            nex = b[ind]
            ans[nex] = check+1
            Li[nex] = 0
#             print(nex)
        if np.any(b == check):
            ind = np.where(b == check)
            nex2 = a[ind]
            ans[nex2] = check+1
            Li[nex2] = 0
#             print(nex2)
    
    Next = np.append(Next, nex)
    Next = np.append(Next, nex2)
    Checks = []
    Checks = Next
#     print("roop = " + str(roop))
#     print(Next)
    # 初期化
    nex = []
    nex2 = []
    
    if roop == 1000:
        break
# print('ans')
print(ans[1:])

Submission status: Runtime Error

Solution code:
import numpy as np

N,M = map(int,input().split())
vector = np.zeros((N, N), dtype=int)

Submission status: Runtime Error

Solution code:
import numpy as np

N,M = map(int,input().split())
vector = np.zeros((N, N))

Submission status: Runtime Error

Solution code:
import numpy as np

N,M = map(int,input().split())
vector = np.zeros((N, N))

for i in range(0, M):
	A,B = map(int,input().split())
	vector[A-1:A,B-1:B] = 1
	vector[B-1:B,A-1:A] = 1

depth = np.zeros((1, N))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
l = []
v = [-1]*M
v[0] = 0
for i in range(M):
  a, b = list(map(int, input().strip().split()))
  if a > b:
    c = a
    a = b
    b = c
  l.append([a, b])
  #print(a, b)
l.sort()
for i in range(M):
  room_1 = l[i][0] -1
  room_2 = l[i][1] -1
  if v[room_2] == -1:
    v[room_2] = v[room_1] + 1
  elif v[room_1] < v[room_2]:
    v[room_2] = v[room_1] + 1
  elif v[room_1] > v[room_2]:
    v[room_1] = v[room_2] + 1
#print(l)
#print(v)
print('Yes')
for i in v:
  if i != 0:
    print(i)

Submission status: Runtime Error

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

room_and_connecting_room_dict = {i:set() for i in range(1,N+1)}

for i in range(M):
    A,B = map(int, input().split())
    room_and_connecting_room_dict[A].add(B)
    room_and_connecting_room_dict[B].add(A)

def get_child_ans(room_numbers_set): #room_number_list:前の部屋番の子ども全て
    
    next_room_numbers_set = set()
    
    for room_number in room_numbers_set:
        for child_room in room_and_connecting_room_dict[room_number]:
            if child_room not in calculated_room_numbers_set:
                ans_dict[child_room] = room_number #前の部屋番の子供は全て、前の部屋番に回答が確定する
                next_room_numbers_set.add(child_room)
                calculated_room_numbers_set.add(child_room)
 
    #終了判定
    if len(calculated_room_numbers_set) == N: #全部計算済み
        return 1
    elif len(next_room_numbers_set) == 0: #1から繋がる全てを計算したのに未計算がある
        return -1
    else: #孫がいるのでまだやる
        return get_child_ans(next_room_numbers_set)

ans_dict = dict()
ans_dict[1] = 0
calculated_room_numbers_set = set()
calculated_room_numbers_set.add(1)

is_there_ans = get_child_ans(set([1]))  

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

Submission status: Runtime Error

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

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)

prev = [None for _ in range(n)]
dist = [float('inf') for _ in range(n)]


def dfs(start):
    for n_r in edge[start]:
        if dist[n_r] > dist[start] + 1:
            dist[n_r] = dist[start] + 1
            prev[n_r] = start
        else:
            continue
        dfs(n_r)


dist[0] = 0
dfs(0)
if None in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M=map(int,input().strip().split())
G=defaultdict(list)
for i in range(M):
  u,v=map(int,input().strip().split())
  G[u].append(v)
  G[v].append(V)
dist=[(-1,parent)]*(N+1)
valid=False
Q=[1]
visited=[False]*(N+1)
while(len(Q)!=0):
  top=Q[0]
  Q.pop(0)
  for u in G[top]:
    if not visited[u]:
      Q.append(u)
      dist[u][0]=1+dist[top][0]
      dist[u][1]=top
      visited[u]=True
for pair in dist[1:]:
  if pair[0]==-1:
    valid=True
    print("No")
    return 
if not valid:
  print("Yes")
  for pair in dist[1:]:
    print(pair[1])

Submission status: Runtime Error

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

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

es = [[] for _ in range(N)]
for a, b in AB:
    es[a-1].append(b-1)
    es[b-1].append(a-1)

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

from collections import deque
que = deque
que.insert(0)

while que:
    s = que.popleft()
    for v in es[s]:
        if ans[v] == -1:
            ans[v] = s+1
            que.put(v)

print("Yes")
print(*ans[1:], sep="\n")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = [[] for i in range(n)]
for i in range(m + 1):
  a, b = map(int, input().split())
  l[a].append(b)
  l[b].append(a)
ans = [-1] * (n+1)
ans[0] = 0
x = [1]
y = []
count = 1
while x != []:
  for i in x:
    for j in l[i]:
      if ans[j] == -1:
        ans[j] = i
        y.append(j)
        count += 1
  x = y
  y = []
print('Yes')
for i in range(2, n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


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

edge = [[] for i in range(w)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)

Submission status: Runtime Error

Solution code:
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


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

edge = [[] for i in range(w)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i, j in enumerate(prev[1:]):
        print(j + 1)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
n, m = map(int, input().split())
route = np.zeros((n, n), dtype = np.bool)
for _ in range(m):
    a, b = map(int, input().split())
    route[a-1][b-1] = True
    route[b-1][a-1] = True

q = deque()
visited = [0] * n
pre = [-1] * n
q.append(0)
visited[0] = 1
while q:
    # visitした
    v = q.popleft()
    for i in range(n):
        if visited[i] == 1 or route[v][i] == False: continue
        visited[i] = 1
        pre[i] = v
        q.append(i)
print("Yes")
for p in pre[1:]:
    p += 1
    print(p)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
outs = defaultdict(list)

for _ in range(M):
    v1, v2 = map(int, input().split())
    # if v1>v2: v1,v2 = v2,v1
    outs[v1].append(v2)
    outs[v2].append(v1)

#print(outs)
q = deque([1])
depth = defaultdict(int)
depth[1] = 0
visit = [False]*M #配列なので0オリジン
visit[0] = True

while q:
    v1 = q.popleft()
    for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
        if visit[v2-1]==False:
            visit[v2-1] = True
            if depth[v2] == 0:
                depth[v2] = v1
            q.append(v2)
            print(v2,q,depth)

b = sorted(depth.items())
#print(b)
print("Yes")
for i in range(1,N):
    print(b[i][1])

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
outs = defaultdict(list)

for _ in range(M):
    v1, v2 = map(int, input().split())
    # if v1>v2: v1,v2 = v2,v1
    outs[v1].append(v2)
    outs[v2].append(v1)

#print(outs)
q = deque([1])
depth = defaultdict(int)
depth[1] = 0
visit = [False]*M #配列なので0オリジン
visit[0] = True

while q:
    v1 = q.popleft()
    for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
        if visit[v2-1]==False:
            visit[v2-1] = True
            if depth[v2] == 0:
                depth[v2] = depth[v1] + 1
            q.append(v2)
            #print(v2,q,depth)

b = sorted(depth.items())
#print(b)
print("Yes")
for i in range(1,N):
    print(b[i][1])

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
outs = defaultdict(list)

for _ in range(M):
    v1, v2 = map(int, input().split())
    # if v1>v2: v1,v2 = v2,v1
    outs[v1].append(v2)
    outs[v2].append(v1)

#print(outs)
q = deque([1])
depth = defaultdict(int)
depth[1] = 0
visit = [False]*M #配列なので0オリジン
visit[0] = True

while q:
    v1 = q.popleft()
    for v2 in outs[v1]: #v1のノードから出ている矢印をみる．
        if visit[v2-1]==False:
            visit[v2-1] = True
            if depth[v2] == 0:
                depth[v2] = depth[v1] + 1
            q.append(v2)
            #print(v2,q,depth)

b = sorted(depth.items())
print(b)
print("Yes")
for i in range(1,N):
    print(b[i][1])

Submission status: Runtime Error

Solution code:
from collections import deque

n,m=map(int,input().split())
L=[[] for i in range(n)]
for i in range(m):
	L[a-1].append(b-1)
	L[b-1].append(a-1)
D=[float('inf') for i in range(n)]

def bfs():
	que=deque([])
	que.append(0)
	D[p]=0
	while que:
		p=que.popleft()
		for np in L[p]:
			if D[np]==float('inf'):
				que.append(np)
				D[np]=p

bfs()

if sum(D)==float('inf'):
	print('No')
else:
	print('Yes')
	for i in range(1,n):
		print(D[i])

Submission status: Runtime Error

Solution code:
import collections

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(m)]
    for i in range(m):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append(b)
        g[b].append(a)
    ans = solve(n, m, g)
    if -1 in ans:
        print('No')
    else:
        print('Yes')
        print(*ans, sep = '\n')


def solve(n, m, g):
    q = collections.deque()
    distances = [-1 for i in range(n)]
    ans  = [-1 for i in range(n)]
    distances[0] = 0
    q.append(0)
    while len(q):
        pos = q.popleft()
        for i in g[pos]:
            if distances[i] == -1:
                q.append(i)
                distances[i] = distances[pos] + 1
                ans[i] = pos + 1
    return ans[1:]


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def bfs_opt(s):
    signs[s] = 0
    Q.append(s)
    while len(Q) > 0:
        u = Q.popleft()
        for v in rooms[u]:
            if signs[v] == INFTY:
                signs[v] = u
                Q.append(v)


n, m = map(int, input().split())
rooms = [[] for i in range(n)]

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

INFTY = float('inf')
signs = [INFTY] * n

# status を保持しなくても、signs == INFTY (== 未訪問) で訪問済みかどうかの判定は可能
# for bfs()
# NOT_VISITED = 0
# VISITING = 1
# VISITED = 2
# status = [NOT_VISITED] * n

Q = deque()

bfs_opt(0)

# ok = True
# for sign in signs:
#     if sign == INFTY:
#         ok = False

# ok にならない (No になる) ケースは存在しない
print('Yes')
signs = signs[1:]
for sign in signs:
    print(sign + 1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

tree=[[0] for _ in range(N)]

for _ in range(M):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)

dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w]!=-1:
            continue
        dist[w] = v
        que.append(w)

print("Yes")
for j in range(1,N):
    print(ans[j])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

# D - .. (Double Dots)
from collections import deque
sys.setrecursionlimit(pow(10, 5))

def set_route(start, goal):
	global routes
	
	routes[goal].append(start)


def search(que):
	global routes
	global guides

	if len(que) > 0:
		goal = que.popleft()

		for start in routes[goal]:
			if guides[start] == 0:
				guides[start] = goal
				que.append(start)
		
		search(que)
	else:
		return 


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

# 空の辞書(routes)を作成
for i in range(1, n + 1):
	routes[i] = []

# すべての出入り口の情報を取得("routes"に保存)
for i in range(m):
	a, b = map(int, input().split())
	set_route(a, b)
	set_route(b, a)

# 道しるべ(最後に出力)を保存するためのリスト
guides = [0] * (n + 1)

que = deque()
que.append(1)
search(que)

ans = guides[2:]

if 0 in ans:
	print('No')
else:
	print('Yes')
	
	for a in ans:
		print(a)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

# D - .. (Double Dots)
from collections import deque

def set_route(start, goal):
	global routes
	
	routes[goal].append(start)


def search(que):
	global routes
	global guides

	if len(que) > 0:
		goal = que.popleft()

		for start in routes[goal]:
			if guides[start] == 0:
				guides[start] = goal
				que.append(start)
		
		search(que)
	else:
		return 


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

# 空の辞書(routes)を作成
for i in range(1, n + 1):
	routes[i] = []

# すべての出入り口の情報を取得("routes"に保存)
for i in range(m):
	a, b = map(int, input().split())
	set_route(a, b)
	set_route(b, a)

# 道しるべ(最後に出力)を保存するためのリスト
guides = [0] * (n + 1)

que = deque()
que.append(1)
search(que)

ans = guides[2:]

if 0 in ans:
	print('No')
else:
	print('Yes')
	
	for a in ans:
		print(a)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = []
B = []
pt = [[] for i in range(N)]
for i in range(M):
	a, b =  map(int, input().split())
	a -=1
	b -=1
	pt[a].append(b)
	pt[b].append(a)
n=M
res_list = [-1] * N
def bfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
                    res_list[j]=i
        q=q1
        c+=1
    return d
res = bfs(0)

no = 'No'
yes ='Yes'
if -1 in res:
	print(no)
else:
	print(yes)
	
for i,x in enumerate(res_list):
	if i==0:
		continue
	print(x+1)