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:
from sys import stdin


class DFS():
    def __init__(self,A_B_arr,N,M):
        self.N = N
        self.M = M
        self.route = {i:[] for i in range(N+1)}
        for A, B in A_B_arr:
            self.route[A].append(B)
            self.route[B].append(A)

        self.dp = [[None,N] for i in range(N+1)]
        self.dp[1] = [1,0]
        self.finished = [False for i in range(N+1)]

    def dfs(self,i,rank):
        for r in self.route[i]:
            if rank<self.dp[r][1]:
                self.dp[r] = [i,rank]
                self.dfs(r,rank+1)
        self.route[i] = []
        return


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dfs = DFS(A_B_arr,N,M)
    dfs.dfs(1,1)

    ans = []
    TF = 'Yes'
    for (i,_) in enumerate(dfs.dp):
        if i>1:
            if _[0] == None:
                TF = 'No'
                break
            else:
                ans.append(_[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if TF == 'Yes':
        print(TF)
        for _ in ans:
            print(_)
    else:
        print(TF)

Submission status: Runtime Error

Solution code:
from collections import deque

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

edges = [[] for j in range(N+1)]
for p in path:
    x, y = p
    edges[x].append(y)
    edges[y].append(x)

que = deque([])
dic = {1: 0}
def bfs(now):
    e = edges[now]
    for q in e:
        if not q in dic:
            dic[q] = now
            que.append(q)
    try:
        n = que.popleft()
        bfs(n)
    except IndexError:
        pass

bfs(1)

if len(dic) != N:
    print("No")
else:
    print('Yes')
    dic_sort = sorted(dic.items())
    for elem in dic_sort:
        if elem[0] != 1:
            print(elem[1])

Submission status: Runtime Error

Solution code:
ans = [-1] * (N+1)
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1):
    graph[i].sort()
    
from collections import deque
todo = deque([(1,0)])
while todo:
    x,parent = todo.pop()
    ans[x] = parent
    for y in graph[x]:
        if y == parent:
            continue
        if ans[y] == -1:
            todo.append((y,x))
print('Yes')
for i in range(2,N+2):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from queue import Queue

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

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

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

    edges[a].append(b)
    edges[b].append(a)

  visited = {}

  q = Queue()
  q.put((0, -1))

  while q.qsize() > 0:
    (current, prev) = q.get()
    if current in visited:
      continue

    visited[current] = prev

    for nxt in edges[current]:
      q.put((nxt, current))

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


main()

Submission status: Runtime Error

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

room_dict = {i+1:[] for i in range(N)}
for _ in range(N):
  _a, _b = list(map(int, input().split()))
  room_dict[_a].append(_b)
  room_dict[_b].append(_a)

rooms = set(room_dict.keys())
s_dict = {i+1:None for i in range(1, N)}
traversed_rooms = set([1])

now_rooms = [1]
from operator import add
while now_rooms:
    next_rooms = set()
    for _room in now_rooms:
        traversed_rooms.add(_room) # 訪問済みを保存
        _n_rooms  = [i for i in room_dict[_room] 
                         if (not i in traversed_rooms) and (s_dict[i] is None)]
        for n_room in _n_rooms:
            next_rooms.add(n_room) # 今の次の階層を、次のiteration用に入れる
            s_dict[n_room] = _room # 次の階層は、今の階層への道標を置けば十分
    now_rooms = [i for i in next_rooms if not i in traversed_rooms] # まだ訪れてない部屋を探す
    
print('Yes') # 常に答えは存在する

for i in range(2, N+1):
    print(s_dict[i])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(5000)
n,m =map(int,input().split())
pas = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    pas[a].append(b)
    pas[b].append(a)

seen = [False for i in range(n)]
que = deque()
def bfn(i,j):
    for x in pas[i]:
        if seen[x-1]!=False:
            continue
        seen[x-1]=i
        que.append([x,i])
    if que:
        now,pre =que.popleft()
        bfn(now,pre)
    else:
        return

bfn(1,1)

if False in seen:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(seen[i+1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
box=[[] for i in range(M)]
for i in range(M):
    a,b=map(int,input().split())
    box[a-1].append(b-1)
    box[b-1].append(a-1)
ans=[0]*(N)
que=[]
ans[0]=1
for i in range(N):
    if ans[i]!=0:
        que+=box[i]
    while len(que)>0:
        c=que.pop()
        if ans[c]==0:
            ans[c]=i+1
for i in range(1,N):
    if ans[i]==0:
        flag=0
        break
    else:
        flag=1
if flag==0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np
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
for i in range(N):
    edge[i][i] = 0

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_ = []
            nogo = np.nonzero(room)[0]
            if len(nogo)==0:
                break
                
            for c in check:
                connect = np.nonzero(edge[c])[0]
                
                for con in connect:
                    if con in nogo:
                        room[con] = 0
                        check_.append(con)
                        sign[con-1] = int(c+1)
                        
                n_check += len(connect)
                if n_check>=2*M:
                    flag = 0
            if len(check_) == 0:
                break
            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:
import math
import numpy as np
from queue import Queue

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

root = np.zeros((n+1,n+1),dtype=np.int)

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


check = [0 for _ in range(n+1)]
check[1] = 1

q = Queue()
q.put(1)

while ( not q.empty() ):
    now = q.get()
    for i in range(1,n+1):
        if(root[now][i] == 1 and check[i] == 0):
            check[i] = now
            q.put(i)

flag = 1
for i in range(2, n+1):
    if(check[i] == 0):
        flag = 0

if(flag == 1):
    print("Yes")
    for j in range(2, n + 1):
        print(check[j])
else:
    print("No")

Submission status: Runtime Error

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

G = [[] for _ in range(m)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)

ans = [-1] * n
ans[0] = 'Yes'

from collections import deque

q = deque(G)

pos = 0
while q:
    _q = q.popleft()
    for x in _q:
        if ans[x] == -1:
            ans[x] = pos
    pos += 1

print('Yes')
for _ans in ans[1:]:
    print(_ans+1)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
A = [0] * N
Ans = [0] * N
AnsC = 1
now = [0] * N
now[0] = 1
nowX = 1

for i in range(N):
  A[i] = sorted(map(int, input().split()))
sA = sorted(A)

print(sA)

Submission status: Runtime Error

Solution code:

from collections import deque


def bfs(u):
    queue = deque([u])
    d = [None] * N  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    ans = [0] * N
    while queue:
        v = queue.popleft()
        for i in g[v]:

            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                ans[i] = v + 1
    return ans

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

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

ans = bfs(0)
if 0 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000)
n,m =map(int,input().split())
pas = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    pas[a].append(b)
    pas[b].append(a)

seen = [False for i in range(n)]
que = deque()
def bfn(i,j):

    for x in pas[i]:
        if seen[x-1]!=False:
            continue
        seen[x-1]=i
        que.append([x,i])
    if que:
        now,pre =que.popleft()
        bfn(now,pre)
    else:
        return

bfn(1,1)

if False in seen:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(seen[i+1])

Submission status: Runtime Error

Solution code:
from collections import deque

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

seen = [0 for _ in range(N)]
seen[0] = 1
shirube = [-1 for _ in range(N-1)]

stack = deque([0])
while stack:
  now = stack.popleft()
  for i in G[now]:
    if seen[i] == 0:
      seen[i] = 1
      stack.append(i)
      shirube[i-1] = now
    
for i in range(N):
  if seen[i] == 0:
    print('No')
    exit()
    
print('Yes')
for j in range(N-1):
  print(shirube[j]+1)

Submission status: Runtime Error

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

from collections import defaultdict

G = defaultdict(set)


results = [-1]*N
flags   = [False]*N

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

#print(G)

### 最初の段階は、全て繋がっているかどうか。
seen = [False]*N
def rec(i):
    seen[i] = True
    for j in G[i]:
        if seen[j]:
            continue
        rec(j)

for i in range(N):
    if seen[i]:
        continue
    rec(i)

#print(seen)
#全て繋がっているなら、whileループを実装して良い
if sum(seen) != N:
    print('No')
else:
    searchs = set(range(1,N))
    for i in list(searchs):
        if 0 in G[i]:
            results[i] = 0
            flags[i]   = True
            searchs.remove(i)
    while len(searchs) != 0:
        for i in list(searchs):
            for j in G[i]:
                if flags[j] == True:
                    results[i] = j
                    searchs.remove(i)
                    break

    print('Yes')
    for i,v in enumerate(results[1:]):
        print(f'{v+1}')

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]+1)
    return d

################################
n,m = 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(m):
    x,y = map(int,input().split())
d = dijkstra(0,n,m,1)
for i in x:
    print(d)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
n,m = map(int,input().split())
rank = [300000] * n
mtrx = [[0]*n for _ in range(n)]
for i in range(m):
   a,b = map(int,input().split())
   mtrx[a-1][b-1] = 1
   mtrx[b-1][a-1] = 1
mtrx = csr_matrix(mtrx)
dij = (dijkstra(mtrx,indices=0,return_predecessors=True,directed=False,unweighted=True))
#print(type(dij[0][3]))
if np.inf in dij[0]:
   print('No')
else:
   print('Yes')
   for i in dij[1][1:]:
      print(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)
A=[0]+[-1]*(n-1)
B=[[0,L[0]]]
def wfs(A,B):
    C=[]
    f=False
    for b in B:
        for l in b[1]:
            if A[l]==-1:
                A[l]=b[0]
                C.append([l,L[l]])
                f=True
    if f:
        return wfs(A,C)
    else:
        print('Yes')
        for a in A[1:]:
            print(a+1)
wfs(A,B)

Submission status: Runtime Error

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

def func(i, d, marks):
    rooms = numpy.nonzero(d[i])[0]
    new_room = []
    if rooms.size == 0:
        return marks
    for j in rooms:
        room_idx = j
        if room_idx in marks:
            continue
        marks[room_idx] = i
        new_room.append(room_idx)
    for j in new_room:
        marks = func(j, d, marks)
    return marks

import numpy

N, M =  list(map(int, input().split()))
d = numpy.zeros((N,M))
for i in range(M):
    a, b =  list(map(int, input().split()))
    d[a-1, b-1] = 1
    d[b-1, a-1] = 1

marks = func(0, d, {0: 0})

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

Submission status: Runtime Error

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

g = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append(b)
  g[b].append(a)#番号を修正。0スタートに。
#print(g)  
reach = [0 for _ in range(N)] #0からの距離を記録。0未到達。
par = [-1 for _ in range(N)] #親の位置を記録

def dfs(v):
  #reach[v] = 1 #今の点は到達した。これいるかな？
  for i in range(len(g[v])): #点vから行ける点をすべて探索
    u = g[v][i] #今探索している点
    if u == 0:
      continue
    if reach[u] != 0:
      if reach[u] > reach[v] + 1: #距離が近ければ更新
        reach[u] = reach[v] + 1
        par[u] = v
        dfs(u)
      else:
        continue
    reach[u] = reach[v] + 1 #探索中の点の到達を記録。
    par[u] = v
    dfs(u)

dfs(0)
#print(reach,par)
if 0 not in reach[1:]:
  print("Yes")
  for i in range(1,N):
    ans = par[i]+1
    print(ans)
else:
  print("No")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
PATHS = list([tuple(map(lambda t: int(t) - 1, input().split())) for i in range(M)])

def follow_guide(start, guides):
    next_room = guides[start]

    depth = 1

    while next_room != 0:
        depth += 1
        next_room = guides[next_room]
    
    return depth


def find_shortest(start, paths, tracks, depth, known):
    if start in known:
        return known[start]

    ls_in = []
    ls_ex = []

    for r1, r2 in paths:
        if r1 == start:
            if r2 == 0: return depth, tracks + [0]

            ls_in.append((r1, r2))

        elif r2 == start:
            if r1 == 0: return depth, tracks + [0]

            ls_in.append((r2, r1))

        else:
            ls_ex.append((r1, r2))
    
    #print(ls_in, start, tracks, depth)

    result = min([find_shortest(r2, ls_ex, tracks + [r2], depth + 1, known) for r1, r2 in ls_in], key=lambda t:t[0])
    
    known[start] = result

    return result

guides = [1]
#depths = [0]

for i in range(1, N):
    depth, tracks = find_shortest(i, PATHS, [], 1, {})
    guide = tracks[0]

    guides.append(guide)
    #depths.append(depth)

#if not all([follow_guide(i, guides) == depths[i] for i in range(1, N)]):
if False:
    print("No")

else:
    print("Yes")

    for guide in guides[1:]:
        print(guide + 1)

Submission status: Runtime Error

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

graph = [[] for _ in range(m)]
for a,b in path:
    graph[a-1].append(b-1); graph[b-1].append(a-1)

parents = [-1]*n
children = [[] for _ in range(n)]
orders = []
stack = [0]
flags = [True] * n
flags[0] = False

while any(flags):
    while stack:
        tmp = stack.pop()
        for node in graph[tmp]:
            if flags[node]:
                flags[node] = False
                children[tmp].append(node)
                parents[node] = tmp
                orders.append(node)
    stack = orders[:]
    
print("Yes")
for i in parents[1:]:
    print(i+1)

Submission status: Runtime Error

Solution code:
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]
done = {}
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')

Submission status: Runtime Error

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

G = [[] for _ in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
    
ans = [-1 for _ in range(N)]
ans[0] = 1
count = 1

stack = [0]

while stack:
    if count == N:
        break
    j = stack.pop(0)
    for i in G[j]:
        if ans[i] == -1:
            ans[i] = j
            stack.append(i)
            count += 1
            
if count != N:
    print("No")
        
else:
    print("Yes")            
    for i in range(1, N):
        print(ans[i] + 1)

Submission status: Runtime Error

Solution code:
import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}

while queue:
    cost, cur = queue.pop()
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.append((next_cost, next_cur))

del results[0]
print(results)

is_no = False
for result in results:
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for result in results:
        print(result[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_ = []
            nogo = np.nonzero(room)[0]
            if len(nogo)==0:
                break
                
            for c in check:
                connect = np.nonzero(edge[c])[0]
                
                for con in connect:
                    if con in nogo:
                        room[con] = 0
                        check_.append(con)
                        sign[con-1] = int(c+1)
                        
                n_check += len(connect)
                if n_check>=2*M:
                    flag = 0
            if len(check_) == 0:
                break
            check = copy.deepcopy(check_)
        else:
            break
    if len(np.nonzero(sign)[0]) == N-1:
        print('Yes')
        for s in sign:
            print(s)
    else:
        print('No')

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]+1)
    return d

################################
n,m = 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(m):
    x,y = map(int,input().split())
print(dijkstra(0,n,w,1))

Submission status: Runtime Error

Solution code:
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]
done = {}
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, sep='\n')
else:
  print('No')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ans=[0]*m
route={}
for i in range(m):
  a,b=map(int,input().split())
  if a in route:
    li=route[a]
    li.append(b)
    route[a]=li
  else:
    route[a]=[b]
  if b in route:
    li=route[b]
    li.append(a)
    route[b]=li
  else:
    route[b]=[a]
que=[1]
clear=[0]*n
while len(que)>0:
  x=que.pop(0)
  if clear[x-1]==0:
    que.extend(route[x])
    for k in route[x]:
      if ans[k-1]==0:
        ans[k-1]=x
    clear[x-1]=1
ans.pop(0)
if sorted(ans)[0]==0:
  print("No")
else:
  print("Yes")
  for k in ans:
    print(k)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A, B = list(), list()
for _ in range(M):
    line = list(map(int, input().split()))
    A.append(line[0]-1)
    B.append(line[1]-1)

cave = [set() for _ in range(M)]
for i in range(M):
    cave[A[i]].add(B[i])
    cave[B[i]].add(A[i])

visited = [False] * M
guide = [-1] * N
queue = [0]
while len(queue):
    current = queue.pop(0)
    visited[current] = True
    for nextRoom in cave[current]:
        if not visited[nextRoom]:
            if nextRoom in guide:
                exit('No')
            queue.append(nextRoom)
            if guide[nextRoom] == -1:
                guide[nextRoom] = current
else:
    print('Yes')
    for g in guide[1:]:
        print(g+1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
path = []
for i in range(M):
  path.append(list(map(int,input().split())))
count = [10000]*N
ans = [0]*N

def room(n):
  for i in range(M):
    if path[i][0]-1 == n:
      if count[path[i][1]-1] > count[n]:
        count[path[i][1]-1] = count[n]+1
        ans[path[i][1]-1] = n
        room(path[i][1]-1)
    if path[i][1]-1 == n:
      if count[path[i][0]-1] > count[n]:
        count[path[i][0]-1] = count[n]+1
        room(path[i][0]-1)
        ans[path[i][0]-1] = n
count[0]=0
room(0)

judge= "Yes"
for i in range(N):
  if ans[i] == 10000:
    judge = "No"
print(judge)
if judge == "Yes":
  for i in range(1,N):
    print(ans[i]+1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
PATHS = list([tuple(map(lambda t: int(t) - 1, input().split())) for i in range(M)])

def follow_guide(start, guides):
    next_room = guides[start]

    depth = 1

    while next_room != 0:
        depth += 1
        next_room = guides[next_room]
    
    return depth


def find_shortest(start, paths, tracks, depth, known):
    if start in known:
        return known[start]

    ls_in = []
    ls_ex = []

    for r1, r2 in paths:
        if r1 == start:
            if r2 == 0: return depth, tracks + [0]

            ls_in.append((r1, r2))

        elif r2 == start:
            if r1 == 0: return depth, tracks + [0]

            ls_in.append((r2, r1))

        else:
            ls_ex.append((r1, r2))
    
    #print(ls_in, start, tracks, depth)

    result = min([find_shortest(r2, ls_ex, tracks + [r2], depth + 1, known) for r1, r2 in ls_in], key=lambda t:t[0])
    
    known[start] = result

    return result

guides = [1]
depths = [0]

for i in range(1, N):
    depth, tracks = find_shortest(i, PATHS, [], 1, {})
    guide = tracks[0]

    guides.append(guide)
    depths.append(depth)

if not all([follow_guide(i, guides) == depths[i] for i in range(1, N)]):
    print("No")

else:
    print("Yes")

    for guide in guides[1:]:
        print(guide + 1)

Submission status: Runtime Error

Solution code:
n,m= map(int,input().split())
roadA= []*m
roadB= []*m
for i in range(0,m):
    a,b= map(int,input().split())
    roadA.append([a,b])
    roadB.append([b,a])
    
road= roadA + roadB
road.sort()
ans=[[-1, 200002] for i in range(m+1)]
ans[1]=[0,1] # parent depth
for i in range(0,len(road)):
    if ans[road[i][1]][1] > ans[road[i][0]][1]+1:
        ans[road[i][1]][1] = ans[road[i][0]][1]+1
        ans[road[i][1]][0] = road[i][0]

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

Submission status: Runtime Error

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

N, M = map(int, input().split())
edge = np.array([input().split() + ['1'] for _ in range(M)], dtype=np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))

path = list(shortest_path(graph, method='D', directed=False)[0][1:])
judge = 'Yes' if all([p > 0 for p in path]) else 'No'

if judge == 'Yes':
    print(judge)
    for p in path:
        print(int(p))
else:
    print(judge)

Submission status: Runtime Error

Solution code:
import sys
import  math
from heapq import *
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

    
N,M=nm()
INF=10**18
def bfs(start,edge):
    d=[INF]*(M+1)
    ans=[0]*(M+1)
    d[start]=0
    q=[(0,start)]
    while(len(q)!=0):
        ci,i=heappop(q)
        for j in edge[i]:
            if(d[j]>d[i]+1):
                d[j]=d[i]+1
                heappush(q,(d[j],j))
                ans[j]=i

    return ans




edge=[[]for _ in range(M+1)]
for i in range(M):
    A,B=nm()
    edge[A].append(B)
    edge[B].append(A)

ans=bfs(1,edge)

for i in range(2,M+1):
    if(ans[i]==0):
        print('No')
        sys.exit(0)

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

Submission status: Runtime Error

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

answer_list = [0] * (n-1)
done_list = [1]
already_list = [1]
before_list = [1]
while len(root_list) > 0 and 0 in answer_list:
    if len(done_list) == 0:
        break
    tmp_list = []
    copy_root_list = root_list.copy()
    for num in done_list:
        for l in root_list:
            if l[1] == num:
                if answer_list[int(l[0]-2)] == 0:
                    answer_list[int(l[0]-2)] = num
                    tmp_list.append(l[0])
                    already_list.append(l[1])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
            elif  l[0] == num:
                if answer_list[int(l[1]-2)] == 0:
                    answer_list[int(l[1]-2)] = num
                    tmp_list.append(l[1])
                    already_list.append(l[1])
                    if l in copy_root_list:
                        copy_root_list.remove(l)
                else:
                    if l in copy_root_list:
                        copy_root_list.remove(l)
    copy_root_list = [i for i in copy_root_list if (i[0] not in already_list or i[1] not in already_list)]
    root_list = copy_root_list
    done_list = tmp_list

if 0 not in answer_list:
    print("Yes")
    for i in answer_list:
        print(int(i))
else:
    print("No")