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:
n,m=map(int,input().split())
li=[[] for i in range(n)]
for i in range(m):
    ai,bi=map(int,input().split())
    li[ai-1].append(bi-1)
    li[bi-1].append(ai-1)
#print(li)
flag=0
fl2=0
for i in range(n):
    if len(li[i])==0:
        flag=1
        break
if flag==1:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        if 0 in li[i]:
            print(1)
        else:
            for j in range(len(li[i])):
                if li[i][j] in li[0]:
                    print(li[i][j]+1)
                    fl2=1
                    break
            if fl2==0:
                for k in range(len(li[0])):
                    for j in range(li[i]):
                        if li[i][j] in li[li[0][k]]:
                            print(li[i][j]+1)
                            break

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

n, m = map(int, rl().split())
li = [[] for _ in range(m+1)]
for _ in range(m):
  a, b = map(int, rl().split())
  a -= 1
  b -= 1
  li[a].append(b)
  li[b].append(a)

marks = [-1]*n
marks[0] = 0
def dfs(aa, x):
  marks[x] = aa
  for nr in li[x]:
    if marks[nr] == -1:
      dfs(x, nr)
  
  
dfs(0, 0)
if -1 in marks:
  print('No')
else:
  print('Yes')
  for i in marks[1:]:
    print(i+1)

Submission status: Runtime Error

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

l = [[] for i in range(N + 1)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    l[a].append(b)
    l[b].append(a)

p = [[] for i in range(N + 1)]
c = [-1] * (N + 1)
c[1] = 0


def dfs(i):
    for j in range(len(l[i])):
        if c[l[i][j]] == -1:
            p[l[i][j]] = i
            c[l[i][j]] = c[i] + 1
            dfs(l[i][j])
        elif c[l[i][j]] > c[i] + 1:
            p[l[i][j]] = i
            c[l[i][j]] = c[i] + 1
            dfs(l[i][j])


dfs(1)
flag = 1
for i in range(2, N + 1):
    if c[i] == -1:
        flag = 0
if flag == 0:
    print('No')
else:
    print('Yes')
    for i in range(2, N + 1):
        print(p[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,z = map(int,input().split())
    cost[x][y] = z
    cost[y][x] = z
d = dijkstra(0,n,w,1)
print('Yes')
for i in range(1, len(d)):
    print(d[i])

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())
R = [[] for _ in range(M)]
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(queue):
    if queue==[]:
        return
    i = queue[0]
    for j in R[i-1]:
        if ans[j-1]!=0:
            continue
        else:
            ans[j-1]=i
            queue.append(j)
    queue.pop(0)
    bfs(queue)
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:
from collections import defaultdict
import itertools
import math

def dfs(vum,s,visit,depth):
    # print('first')
    # print(s,depth,visit)
    if visit[s-1] >= 0:
        return visit
    visit[s-1] = depth
    # print(vum[s])
    for u in vum[s]:
        # print('now', str(u))
        if visit[u-1] >= 0:
            # print('skip', str(u))
            if visit[u-1] > depth:
                visit[u-1] = depth
                # print('update', str(u))
            continue
        s = u
        depth += 1
        visit = dfs(vum,s,visit,depth)
    return visit


def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    s = 1 # 現在地 (初期値はゴールを設定)
    visit = [-1]*len(vum) # 訪問リスト
    depth = 0 # 移動数(深さ)
    visit = dfs(vum,s,visit,depth)
    if -1 in visit:
        print('No')
    else:
        print('Yes')
    for v in visit[1:]:
        print(v)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10


# N個の部屋とM本の通路
N, M = [int(x) for x in stdin.readline().rstrip().split()]

route = [[] for _ in range(M+1)]

for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    route[A].append(B)
    route[B].append(A)


kyori_to_1 = [INF for _ in range(N+1)]
kyori_to_1[1] = 0

miti = [0 for _ in range(N+1)]
miti[0] = -1
miti[1] = -1

is_visited = [False for _ in range(N+1)]

# 幅優先探索
# 試すべき位置をキューで管理
que = deque([1])

# キューが空じゃなければ
while len(que) != 0:
    now = que.popleft()
    
    if is_visited[now]:
        continue

    is_visited[now] = True

    for place in route[now]:
        que.append(place)

        if kyori_to_1[now]+1 < kyori_to_1[place]:
            kyori_to_1[place] = kyori_to_1[now]+1
            miti[place] = now

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

Submission status: Runtime Error

Solution code:
import math
import sys

def rec(rooms, num, distance):
    f = False
    for roomnum in rooms[num]:
        if roomnum not in shirube or distance + 1 < shirube[roomnum][1]:
            shirube[roomnum] = (num, distance + 1)
            f = True
    
    if f:
        for roomnum in rooms[num]:
            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)

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

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = map(int, input().split())
r = [[0] for i in range(n+1)]
num = {0:0, 1:1}
e = deque([]) 
for i in range(m):
	a, b = map(int, input().split())
	r[a].append(b)
	r[b].append(a)
def c(x):
	for y in r[x]:
		if y not in num:
			num[y] = x
			e.append(y)
	if len(e) > 0:
		c(e.popleft())
	else:
		return
c(1)
print("Yes")
for i in range(2, n+1):
	print(num[i])

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = [int(s) for s in input().split()]
edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(M)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

dq = deque([0])
visited = [False] * N
visited[0] = True
parent = [0]*N
while(dq):
    search_obj = dq.pop()
    for candidate_obj in graph[search_obj]:
        if not visited[candidate_obj]:
            dq.appendleft(candidate_obj)
            parent[candidate_obj] = search_obj
            visited[candidate_obj] = True

total_visited = sum(visited)
if total_visited < N:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(parent[i]+1)

Submission status: Runtime Error

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

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

#print(N,M)
#print(AB_list)

mat = np.zeros((N, N))
for a, b in AB_list:
    mat[a][b] = 1
    mat[b][a] = 1
#print(mat)


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]


dist_list = [-1] * N

d, p = shortest_path(mat, return_predecessors=True, unweighted=True)
for n in range(1, N):
    shpath = get_path(n, 0, p)
    #print(n, shpath)
    for i in range(len(shpath)-1):
        #print(shpath[i], shpath[i+1], dist_list)
        if dist_list[shpath[i]] == -1: 
            dist_list[shpath[i]] = shpath[i+1]
        else:
            if dist_list[shpath[i]] != shpath[i+1]:
                print('No')
                exit()
print('Yes')
for dist in dist_list[1:]:
    print(dist+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())
R = [[] for _ in range(M)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for i in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(queue):
    if queue==[]:
        return
    i = queue[0]
    for j in R[i-1]:
        if ans[j-1]!=0:
            continue
        else:
            ans[j-1]=i
            queue.append(j)
    queue.pop(0)
    bfs(queue)
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:
問題文が意味わかんないンゴw

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
l = []
for i in range(M):
  x = list(map(int, input().split()))
  l.append(x)
print(l)
m = []
n = [[1]]

for j in range(M):
  for i in range(M):
    for k in range(len(n[j])):
      if l[i][0] == n[j][k] or l[i][1] == n[j][k]:
        if l[i][0] == n[j][k]:
          m.append(l[i][1])
        else:
          m.append(l[i][0])
        l[i] = [0, 0]
  n.append(m)
  m = []
  print(n)

for i in range(M -1):

Submission status: Runtime Error

Solution code:
# N, M = 6, 9
# ARR = [
#     [3, 4],
#     [6, 1],
#     [2, 4],
#     [5, 3],
#     [4, 6],
#     [1, 5],
#     [6, 2],
#     [4, 5],
#     [5, 6],
# ]

N, M = map(int, input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int, input().split())))


def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeResults = [0 for i in range(n - 1)]
    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1

        nodes[startNode].append(endNode)
        nodes[endNode].append(startNode)

    return nodes, nodeStates, nodeResults


nodes, nodeStates, nodeResults = prepare(N, M, ARR)


def dfs(currentNode, parentNode, nodes):
    childrenNodes = nodes[currentNode]

    if nodeStates[currentNode] > 0:
        return

    if currentNode >= 1:
        nodeResults[currentNode - 1] = parentNode + 1

    nodeStates[currentNode] = True
    for childNode in childrenNodes:
        dfs(childNode, currentNode, nodes)


dfs(0, -1, nodes)

if sum(nodeStates) == N:
    print("Yes")
    for i in range(N - 1):
        print(nodeResults[i])
else:
    print("No")

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

n, m = map(int, rl().split())
li = [[] for _ in range(m)]
for _ in range(m):
  a, b = map(int, rl().split())
  a -= 1
  b -= 1
  li[a].append(b)
  li[b].append(a)

marks = [-1]*n
marks[0] = 0
def dfs(aa, x):
  marks[x] = aa
  for nr in li[x]:
    if marks[nr] == -1:
      dfs(x, nr)
  
  
dfs(0, 0)
if -1 in marks:
  print('No')
else:
  print('Yes')
  for i in marks[1:]:
    print(i+1)

Submission status: Runtime Error

Solution code:
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]
dp = [-1] * (N + 1)
dp[1] = 0
def sign_root(n):
    nxt = []
    for i in room[n]:
        if dp[i] == -1:
            dp[i] = n
            nxt += [i]
    for i in nxt:
        sign_root(i)
sign_root(1)
if -1 in dp[1:]:
    print("No")
else:
    print("Yes")
    for i in dp[2:]:
        print(i)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


road_dict=defaultdict(list)

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

for _ in range(M):
    A,B=map(int,input().split())
    road_dict[A].append(B)
    road_dict[B].append(A)
    
result_dict=defaultdict(list)

def next_tansaku(kiten,counter):
    for i in road_dict[kiten]:
        if (i not in result_dict) or (result_dict[i][1]>counter):
            result_dict[i]=[kiten,counter]
            next_tansaku(i,counter+1)


next_tansaku(1,0)

print('Yes')
for k in range(2,N+1):
    print(result_dict[k][0])

Submission status: Runtime Error

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

  root = [[] for i in range(M+1)]
  for i in range(M):
    A, B = list(map(int, input().split(' ')))
    root[A].append(B)
    root[B].append(A)

  mitisurube = [-1 for i in range(N+1)]
  cost = [-1 for i in range(N+1)]
  next_ = [1]
  cost[1] = 0

  while next_:
    now_pos = next_.pop(0)
    for next_pos in root[now_pos]:
      if cost[next_pos] == -1 or cost[next_pos] > cost[now_pos] + 1:
        cost[next_pos] = cost[now_pos] + 1
        mitisurube[next_pos] = now_pos
        next_.append(next_pos)
  #print('root')
  #print(*root)
  #print('cost')
  #print(*cost)
  #print('mitisirube')
  if mitisurube.count(-1) < 3:
    print('Yes')
    print(*mitisurube[2:], sep='\n')
  else:
    print('No')

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dic = {}
def make_map(a, b, dic):
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
for m in range(M):
    a, b = map(int, input().split())
    make_map(a-1, b-1, dic)
    make_map(b-1, a-1, dic)
maplist = [0]*(N)
minlist = [10**5]*N
logs = []
def dfs(point, depth, log):
    if str(point) in log:
        logs.append(log)
        return
    if minlist[point] >= depth:
        minlist[point] = depth
        if len(log) >= 1:
            maplist[point] = int(log[-1])+1
    log+=str(point)
    depth+=1
    for p in dic[point]:
        dfs(p,depth,  log)
dfs(0,0, "")
if 0 in maplist[1:]:
    print("No")
else:
    print("Yes")
    for i in range(N-1):
        print(maplist[i+1])

Submission status: Runtime Error

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

p=[0]*n
p[0]=1
now=1
cnt=0
while 0 in p and k>0:
    for to in l[now-1] and cnt<=m:
        if p[to]==0:
            p[to]=now
            cnt+=1
    now=to+1
    k-=1
if 0 in p:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(p[i])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
import numpy as np
G = np.zeros((n, n))
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1, b-1] = G[b-1, a-1] = 1

res = np.array([0] + [-1] *(n -1))

from collections import deque
q = deque([0])

while q:
    vis = q.popleft() # visit
    #     print(vis)
    cands = np.where(G[vis])[0] # next visit

    for c in cands:
        if res[c] == -1:
            res[c] = vis # mark
            q.append(c) # shoul append

if (res == -1).sum():
    print('No')
else:
    print('Yes')
    for i in res[1:]:
        print(i +1)

Submission status: Runtime Error

Solution code:
#### import numpy as np
N,M = map(int,input().split())
R = [[] for _ in range(M)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for i in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(queue):
    if queue==[]:
        return
    i = queue[0]
    for j in R[i-1]:
        if ans[j-1]!=0:
            continue
        else:
            ans[j-1]=i
            queue.append(j)
    queue.pop(0)
    bfs(queue)
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 math
 
a,b,c,d = map(float,input().split())
 
H = 30
M = 6
 
HM = 0.5
 
kakudo = abs((c*H+d*HM) - d*M)
 
if kakudo == 180:
  print(a+b)
elif kakudo == 0:
  print(abs(a-b))
else:
  print(math.sqrt(pow(a,2) + pow(b,2) - 2*a*b*math.cos(math.radians(kakudo))))

Submission status: Runtime Error

Solution code:
import numpy as np

def dijkstra(graph,node_count,start_index):
    INF = 10**9+7
    node = [INF] * node_count
    conf = [0] * node_count
    root = [-1] * node_count

    node[start_index] = 0
    count = 0
    while sum(conf) < node_count:

        change = False

        min_node_dex = -1
        min_node_val = INF
        for i in range(node_count):
            if conf[i] == 0:
                if node[i] < min_node_val:
                    min_node_val = node[i]
                    min_node_dex = i
        conf[min_node_dex] = 1
        for i in range(node_count):
            if conf[i] == 0:
                if g[min_node_dex][i] > 0:
                    new_dist = node[min_node_dex] + g[min_node_dex][i]
                    if new_dist < node[i]:
                        node[i] = new_dist
                        root[i] = min_node_dex
                        change = True

        #print(node)
        #print(conf)
        #print(root)
        count += 1
        if not change:
            break
        #if count >= 10:
        #    break
    return root

n, m = map(int, input().split())
r = []
g = np.zeros((n,n),dtype=np.uint32)

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

#c = dijkstra_heapq(g,n,0)
c = dijkstra(g,n,0)

#print(np.array(c) + 1)

ans = []
for i in range(1,n):
    if c[i] >= 0:
        ans.append(c[i]+1)
    else:
        print('No')
        exit()

print('Yes')
for i in range(len(ans)):
    print(ans[i])

#print(np.array(c)+1)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m=list(map(int,input().split()))
root=np.zeros([n,n])
for _ in range(m):
    a,b=list(map(int,input().split()))
    root[a-1,b-1]=1
    root[b-1,a-1]=1
ans=np.zeros(n)
s=set([0])
for cnt in range(1,n):
    tmp_s=set([])
    for sta in s:
        elm=np.where(root[sta]==1)[0]
        for e in elm:
            tmp_s.add(e)
    for ts in tmp_s:
        if ans[ts]==0:
            ans[ts]=cnt
    for ss in s:
        root[ss]*=0
        root[:,ss]*=0
    s=tmp_s
if 0 in ans[1:]:
    print("No")
else:
    print("Yes")
    for a in ans[1:]:
        print(int(a))

Submission status: Runtime Error

Solution code:
k=int(input())
s=input()
if(len(s)<=k):
    print(s)
else:
    print(s[0:k]+'...')

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
path = []
connect = [[] for i in range(N)]
target = [-1]*N
for i in range(M):
  path.append(list(map(int,input().split())))
  connect[path[i][0]-1].append(path[i][1])
  connect[path[i][1]-1].append(path[i][0])

count = [10000]*N
count[0] = 0

def root(n):
  for i in connect[n]:
    if count[i-1] > count[n]:
      count[i-1] = count[n]+1
      target[i-1] = n+1
      root(i-1)

root(0)

judge= "Yes"
for i in range(1,N):
  if target[i] == -1:
    judge = "No"
print(judge)
if judge == "Yes":
  for i in range(1,N):
    print(target[i])

Submission status: Runtime Error

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


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= floyd_warshall(csgraph=graph,unweighted=True, directed=False,return_predecessors=True)

if -9999 in predecessors[0][1:]:
    print("No")
else:
    ans=predecessors[0][1:]+1
    print("Yes")
    for a in ans:
        print(a)

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 False
    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():
    a, b = map(int, input().split())
    return [a, b]



n, m = map(int, input().split())
michis = [michi_input() for _ in range(m)]


michi_to = [[] for _ in range(n+1)]
for michi in michis:
    a = michi[0]
    b = michi[1]
    michi_to[a].append(b)
    michi_to[b].append(a)

INF = 1000000
kamban = [[-1, INF] for _ in range(n+1)]
kamban[1] = [1, 0]
i = 0
for j in range(1,n+1):
    tf = kamban_okude(j, i)
    if tf == False:
        continue
    else:
        break

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:
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

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 sys

N, M = map(int, sys.stdin.readline().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

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

# 深さ優先探索
sign_list = [[] for _ in range(N)]
visited = [0] * N
visited[0] = 1

def dfs(tree, pos):
    visited[pos] = 1
    children = []
    for r in tree[pos]:
        if visited[r] == 0:
            children.append(r)
    for c in children:
        sign_list[c] = pos + 1
        dfs(tree, c)

dfs(tree, 0)

for i in range(1, N):
    print(sign_list[i])

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

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

from collections import deque
def bfs(start):
    dist = [INF] * N
    dist[start] = 0
    seen = [0] * N
    shirube = [None] * N
    shirube[0] = 'Yes'
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for next_room in graph[v]:
            if seen[next_room]:
                continue
            if dv + 1 < dist[next_room]:
                dist[next_room] = dv + 1
                shirube[next_room] = v + 1
            seen[next_room] = 1
            q.append(next_room)
    if all(shirube):
        for x in shirube:
            print(x)
    else:
        # print(shirube)
        print('No')
bfs(0)

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,z = map(int,input().split())
    cost[x][y] = 1
    cost[y][x] = 1
d = dijkstra(0,n,m,1)
print("Yes")
for i in range(1, len(d)))):
    print(d[i])

Submission status: Runtime Error

Solution code:
mod = 10**9+7
import sys
import math
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations, combinations_with_replacement
from itertools import accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil,floor
from copy import deepcopy
from heapq import heappop,heappush,heapify
import heapq


# def combinations(n, r):
# 	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# def gcd(a, b):
# 	if b == 0:
# 		return a
# 	else:
# 		return gcd(b, a%b)
 
# def lcm(a, b):
# 	return a // gcd(a, b) * b

# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))


N,M = MI()
A = []
B = []
for _ in range(M):
	a,b = MI()
	A.append(a)
	B.append(b)

d = defaultdict(int)
ref_list = [''] * M

for aa, bb in zip(A,B):
	ref_list[bb-1] += str(aa)
	ref_list[aa-1] += str(bb)


def rec(i, done, num):
	d[i] = num
	candidate = list(set(ref_list[int(i)-1]))
	new_done = done+candidate
	for c in candidate:
		if not c in done:
			rec(c, new_done, num+1)
	return


rec(1, [], 0)
d[str(1)] = 0
ans = []
for i in range(1,M):
	d_i = d[str(i+1)]
	for target in list(set(ref_list[i])):
		if d[str(target)] == d_i -1:
			ans.append(target)
			break
if len(ans)==N-1:
	print('Yes')
	for f in ans:
		print(f)
else:
	print('No')

Submission status: Runtime Error

Solution code:
import math
import sys

def rec(rooms, num, distance):
    f = False
    for roomnum in rooms[num]:
        if roomnum not in shirube or distance + 1 < shirube[roomnum][1]:
            shirube[roomnum] = (num, distance + 1)
            f = True
    
    if f:
        for roomnum in rooms[num]:
            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])