Problem:


Score: 400 points

Problem Statement

There is a cave.

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

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

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

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

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

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

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

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

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

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

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

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

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

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

Thus, the objective is satisfied.

Sample Input 2

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

Sample Output 2

Yes
6
5
5
1
1

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



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


Sample output:
Yes
1
2
2

Submission status: Runtime Error

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

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

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

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

print('Yes')
sp+=1
l=[]
for i in range(1,len(sp)):
    if sp[i]<0:
        print('No')
        exit
    l.append(sp[i])

for i in l:
    print(i)

Submission status: Runtime Error

Solution code:
# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph,shortest_path,single_target_shortest_path,astar_path
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(N)]

G.add_edges_from(rows)
# shortestPath = shortest_path(G,target=1)
# shortestPath = single_target_shortest_path(G,target=1)
ans = ["Yes"]
for i in range(2,N+1):
    try:
        shortestPath = astar_path(G,source=i,target=1)
        ans.append(shortestPath[1])
    except:
        print("No")
        exit()

print(*ans,sep="\n")
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def distcascade(dist,link,v,d):
  nextdis = set()
  for s in link[v]:
    if s != 1:
      if s not in dist:
        dist[s] = d
        nextdis.add(s)
      else:
        dist[s] = min(dist[s],d)
  for x in nextdis:
    distcascade(dist,link,x,d+1)

n,m = map(int,input().split())
ab = [[0]*2]*m
for i in range(m):
  ab[i] = list(map(int,input().split()))
linked = dict()
for i in range(m):
  if ab[i][0] not in linked:
    linked[ab[i][0]] = {ab[i][1]}
  else:
    linked[ab[i][0]].add(ab[i][1])
  if ab[i][1] not in linked:
    linked[ab[i][1]] = {ab[i][0]}
  else:
    linked[ab[i][1]].add(ab[i][0])
sol = 1
for i in range(1,n+1):
  if i not in linked:
    sol = 0
if sol == 0:
  print("No")
else:
  dist = {}
  distcascade(dist,linked,1,1)
  signboard = {}
  for i in range(2,n+1):
    if dist[i] == 1:
      signboard[i] = 1
    else:
      for s in linked[i]:
        if dist[s] == dist[i]-1:
          signboard[i] = s
  print("Yes")
  for i in range(2,n+1):
    print(signboard[i])

Submission status: Runtime Error

Solution code:
tmp = input().split()
N = int(tmp[0])
S = [0 for i in range(N)]
T = [0 for i in range(N)]

for n in range(N):
    tmp = input().split()
    S[n] = int(tmp[0])
    T[n] = int(tmp[1])


#total 
mod =  1000000007

dp[0] = 0

for i in range(N+1):
    
    out = 0
    for k in range(i):
        if S[k]*S[i]+T[k]*T[i] == 0:
            ++out
    dp[i+1] = dp[i]*2 - out 
    dp[i+1] = dp[i+1] %mod
print(dp[N])

Submission status: Runtime Error

Solution code:
N,M= map(int, input().split())
A=[]
B=[]
N=1
NL=0
dn=0
ans=[]
ansx=[]
Lall=list()
moji="No"
for i in range(M):
    L=list(map(int, input().split()))
    Lall.append(L)




for j in range(M-1):
    
    for i in range(M):
        if N in Lall[i]:
            ansx.append(N)
            if Lall[i][0]==1:
                NL=1
            else:
                NL=0
        
            del Lall[i]
            dn+=1
            
        
        if i+1>=M-dn:
            break
        if len(Lall)==0:
            break
    if len(Lall)==0:
        moji="Yes"
        break
        
    ans.append(N)
    N=L[NL]
   
print(moji)
for i in range(M-1):
    print(ansx[i])

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
for i in range(m):
    A[i], B[i] = map(int, input().split())

next_queue = deque()
sign = [-1] * n

next_queue.append(1)

while next_queue:
    current_number = next_queue.popleft()
    for i, _ in enumerate(A):
        if A[i] == current_number:
            if sign[B[i] - 1] == -1:
                sign[B[i] - 1] = current_number
                if B[i] != 1:
                    next_queue.append(B[i])
                A.pop(i)
                B.pop(i)
        if B[i] == current_number:
            if sign[A[i] - 1] == -1:
                sign[A[i] - 1] = current_number
                if A[i] != 1:
                    next_queue.append(A[i])
                A.pop(i)
                B.pop(i)
print("Yes")
for i in range(1, n):
    print(sign[i])

Submission status: Runtime Error

Solution code:
N,M =  (int(x) for x in input().split())
A = [[0 for j in range(1)] for i in range(M+1)]
ans = [None]*(M)
num = M - 1
nextnum = []
newnextnum = []
for i in range(M):
    a,b =  (int(x) for x in input().split())
    A[a].append(b)
    A[b].append(a)
if(A[1] == [0]):
    print ("No")
else:
    for i in A[1]:
        if i != 0:
            ans[i-1] = 1
            num -= 1
            nextnum.append(i)
    while(num>0):
        for j in range(len(nextnum)):
            for i in A[nextnum[j]]:
                if i != 0 and i != 1 and ans[i-1] == None:
                    ans[i-1] = nextnum[j]
                    num -= 1
                    newnextnum.append(i)
        if(newnextnum = []):
            break
        nextnum = newnextnum
        nextnum = []
    print("Yes")
    for i in range(1,len(ans)):
        print(ans[i])

Submission status: Runtime Error

Solution code:
n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = [0 for i in range(n)]
def trace(no, lv):
    lst = d[no]
    for c in lst:
        if c == 1:
            continue
        if r[c-1] == 0:
            r[c-1] = no
            trace(c, lv + 1)
        elif r[c-1] != no:
            continue

trace(1, 0)

if len(list(filter(lambda x: x == 0, r))) >1:
    print('No')
else:
    print('Yes')
    for s in r:
        print(s)

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:
        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:
import numpy as np

N, M = map(int, input().split())
ans_list = np.zeros(N-1, dtype=int)
AB = []
flag = 0
ans_num_1 = []
for i in range(M):
    ab = list(map(int, input().split()))
    AB.append(ab)
    if 1 in ab:
        for j in ab:
            if j != 1:
                ans_num_1.append(j)
                ans_list[j-2] = 1
        AB.remove(ab)
if 0 not in ans_list:
    flag = 1
    print("Yes")
# print(ans_list)
while(flag != 1):
    if flag == 0:
        for ab in AB:
            for ans_num in ans_num_1:
                if ans_num in ab:
                    for j in ab:
                        if ans_num != j:
                            ans_list[j-2] = ans_num
                    AB.remove(ab)
            
        if 0 not in ans_list:
            flag = 1
            print("Yes")
if flag == 1:
    for ans in ans_list:
        print(ans)

Submission status: Runtime Error

Solution code:



# print('input >>')
N, M = map(int,(input().split()))
ABs = [map(int,(input().split())) for _ in range(M)]

INF = 10 ** 10
ds = [0] * (N+1)
marks = [0] * (N+1)

nodes = [None] * (N+1)

for AB in ABs:
    A, B = AB
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)

    B, A = A, B
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)

# print(nodes)

checked = [0] * (N+1) 

def dfs(cur, parent, children):
    # print(parent, children)
    if checked[parent] == 1:
        return
    checked[parent] = 1
    for child in children:
        # print(parent, cur, ds)
        if marks[child] == 0 or ds[child] < cur:
            marks[child] = parent
            ds[child] = cur
            # print(marks)
        # if not checked[child] == 0:
        dfs(cur+1, child, nodes[child])

dfs(0, 1, nodes[1])

# print('-----output-----')
print('Yes')
for mark in marks[2:]:
    print(mark)

"""
7 7
1 2
2 5
5 7
3 1
7 3
6 1
2 4
"""

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
K = [list(map(int, input().split()))]
if M > 1:
    for i in range(M - 1):
        K.append(list(map(int, input().split())))

S = [0] * N
A = np.eye(N)
for i in range(M):
    A[K[i][0]-1,K[i][1]-1] = 1
    A[K[i][1]-1,K[i][0]-1] = 1

x = [0]
while len(x) != 0:
    y = []
    for i in range(len(x)):
        for j in range(x[i],N):
            if A[x[i], j] == 1 and S[j] != 0:
                S[j] = 1
                y.append(j)
    x = y

flag = 0
for i in range(1, len(S)):
    if S[i] == 0:
        flag = 1
        print("No")
        break
if flag == 0:
    print("Yes")
    for i in range(1, len(S)):
        print(S[i]-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
n,m = map(int, input().split())
a=[]
b=[]
for i in range(m):
    aa,bb=map(int,input().split())
    a.append(aa)
    b.append(bb)

graph=np.zeros((n,n))

for i in range(m):
    graph[a[i]-1][b[i]-1] = 1
    graph[b[i]-1][a[i]-1] += 1

d,p=shortest_path(graph,return_predecessors=True)
print(d)
print(p)

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]

for i in range(1,m):
    for j in range(i,m):
        if graph[i][j] == np.inf:
            print('No')
            break
        if i == m - 1 and j == m -1:
            print('Yes')
            for i in range(1,n):
                michi= get_path(0,i,p)
                print(michi[-2]+1)

Submission status: Runtime Error

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

def recursive(num, array):
    array = array[:]
    for i in range(m):
        if num == paths[i][0]:
            if array[paths[i][1]-2] == 0:
                array[paths[i][1]-2] = num
                array = recursive(paths[i][1], array)
        if num == paths[i][1]:
            if array[paths[i][0]-2] == 0:
                array[paths[i][0]-2] = num
                array = recursive(paths[i][0], array)
    return array

def main():
    array = [0]*(n-1)
    array = recursive(1,array)
    if 0 in array:
        print('No')
        return
    print('Yes')
    for val in array:
        print(val)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce
from collections import deque

import numpy as np


def is_ok(n, lst):
  flags = [0 for i in range(n)]
  for i in lst:
    flags[i[0]-1] = 1
    flags[i[1]-1] = 1
  if reduce(mul, flags) > 0:
    return True
  return False  


n, m = map(int, input().split())
arr = np.zeros([n, n])
for i in range(m):
  tmp0, tmp1 = map(int, input().split())
  arr[tmp0-1][tmp1-1] = 1
  arr[tmp1-1][tmp0-1] = 1
  

can_solve = is_ok(n, lst)
if can_solve:
  print("Yes")
else:
  print("No")

Submission status: Runtime Error

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
n,m = map(int, input().split())		# 5 7 2

A=[0]
B=[0]
G = [ [] for i in range(m+1) ]

for i in range(m):
	a,b = map(int, input().split())		# 5 7 2
	A.append(a)
	B.append(b)
	G[a].append(b)
	G[b].append(a)

#p("G=", G)

#X = [0]*(n+1)
L_MAX = 100100100
X = [ [0,L_MAX] for i in range(n+1) ]

X[1][0] = 1
X[1][1] = 0

from collections import deque

Q = deque()

fm = 1
to = 1
Q.append(1)

while Q:
	fm = Q.popleft()

	g = G[fm]
	for to in g:
		p("fm,g,to,Q=",fm,g,to,Q)

		if (X[fm][1]+1 < X[to][1]):
			X[to][0] = fm
			X[to][1] = X[fm][1] + 1
			Q.append(to)
		
		if (X[to][1]+1 < X[fm][1]):
			X[fm][0] = to
			X[fm][1] = X[to][1] + 1
			Q.append(fm)


#p("X =",X)
#p("X2=",X[2:])

Y = X[2:]

for a,l in Y:
	if l == L_MAX:
		print("No")
		exit(0)

print("Yes")
for a,l in Y:
	print(a)

p("Y=",Y)

Submission status: Runtime Error

Solution code:
def solve():
    N, M = map(int, input().split()) 
    paths = []
    for _ in range(M):
        paths.append(list(map(int, input().split())))

    rooms = [[0,0] for i in range(N-1)] # 2~N
    levels = [[1]]
    
    i = 0
    while(len(paths)!=0):
        # print(paths)
        # print(levels)
        # print(rooms)
        rmlists = []
        level = []
        for path in paths:
            for r_base in levels[i]:
                # print('path: ',path)
                # print('r_base: ',r_base)
                if r_base in path:
                    # print('flag')
                    r = [i for i in path if i!=r_base][0]
                    level.append(r)
                    rooms[r-2][0] = i+1
                    rooms[r-2][1] = [i for i in path if i==r_base][0]
                    rmlists.append(path)

        for path in paths:
            if len(set(path) & set(level)) == 2:
                rmlists.append(path)
        
        levels.append(level)
        i += 1

        for rmlist in rmlists:
            paths.remove(rmlist)

        # if i == 4:
        #     break

    check = []
    for room in rooms:
        check.append(room[1])
    if not all(check):
        print('No')
    else:
        print('Yes')
        for room in rooms:
             print(room[1])




if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

N, M = map(int, readline().split())
ans = [0 for _ in (N + 1)]
append_ans = ans.append
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)

root = 1
q = [root]
append_q = q.append
checked = [0] * (N + 1)
checked[root] = 1
order = []
append_order = order.append
parent = [-1 for _ in range(N+1)]

while q:
    x = q.pop(0)
    for y in graph[x]:
        if checked[y]:
            continue
        if parent[y] != -1:
            continue
        parent[y] = x
        append_ans(x)
        append_order(y-2)
        checked[y] = 1
        append_q(y)

if len(order) != N - 1:
    print('No')
else:
    print('Yes')
    for i in range(len(order)):
        j = order.index(i)
        print(ans[j])

Submission status: Runtime Error

Solution code:
N,M =  (int(x) for x in input().split())
A = [[0 for j in range(1)] for i in range(M+1)]
ans = [None]*(M)
num = M - 1
nextnum = []
newnextnum = []
for i in range(M):
    a,b =  (int(x) for x in input().split())
    A[a].append(b)
    A[b].append(a)
if(A[1] == [0]):
    print ("No")
else:
    for i in A[1]:
        if i != 0:
            ans[i-1] = 1
            num -= 1
            nextnum.append(i)
    while(num>0):
        for j in range(len(nextnum)):
            for i in A[nextnum[j]]:
                if i != 0 and i != 1 and ans[i-1] == None:
                    ans[i-1] = nextnum[j]
                    num -= 1
                    newnextnum.append(i)
        if(nextnum = []):
            break
        nextnum = newnextnum
        nextnum = []
    print("Yes")
    for i in range(1,len(ans)):
        print(ans[i])

Submission status: Runtime Error

Solution code:
#1<=A     A sench (hour)
#B<=1000  B sench (min)
#0<=H<=11 hour
#0<=M<59  minute

N,M = map(int,input().split())
AB = []
#B = []
while True:
    try:
        AB.append(list(map(int,input().split())))
        #A.append(listA[0])
        #B.append(listA[1])
    except:
        break

#N個 1-N
#M本 1-M

#print(AB)
class Room:
  def __init__(self, num, connected):
    #print('[Room.__init__]')
    self.num = num
    self.connected = connected
    self.first = 10**5
  def add(self, con):
    self.connected.append(con)
  def showinfo(self):
    #print('[Room.showinfo]')
    print(str(self.num)+' '+str(self.connected)) 

Rl = [Room(i,[]) for i in range(1,N+1)]
#Rl[0].showinfo()
#Rl[0].add(2)
#Rl[0].showinfo()
for i in range(M):
  Rl[AB[i][0]-1].add(AB[i][1])
  Rl[AB[i][1]-1].add(AB[i][0])

#for i in range(N):
#  Rl[i].showinfo()

  
Rl[0].first = 0

ma = [0]*N

def dijkstra(s):
  if(Rl[s-1].num == 1):
    Rl[s-1].first = 0
  
  if(ma[s-1]==1):
    return
  ma[s-1]+=1
    
  leng = len(Rl[s-1].connected)
  for i in range(leng):
    Rl[ Rl[s-1].connected[i]-1 ].first = min(Rl[ Rl[s-1].connected[i]-1 ].first, Rl[s-1].first+1)
  for i in range(leng):
    dijkstra(Rl[s-1].connected[i-1])

dijkstra(1)
if(sum(ma) < N):
  print('No')
else:
  print('Yes')
  for i in range(2,N):
    print(Rl[i-1].first)

Submission status: Runtime Error

Solution code:
import itertools

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

path = [[False] * n for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

anspath = [float('inf')] * (n-1)

ans = 0

# 頂点を並び替える順列を生成してループ
for i in itertools.permutations(range(n), n):
  # 頂点1が終点
  if i[-1] == 0:
    # 生成した順列の中をさらにループ
    print(i)
    for j in range(n):
      temppath = [0]*(n-1)
      # n - 1 まで続いたら条件を満たすパスが存在する
      if j == n - 1:
        ans += 1
        for p in range(n-1):
          if temppath[p] <= anspath[p]:
            anspath[p] = temppath[p]
            break
      # i[j] から i[j + 1] に行くパスがなければ終了
      if not path[i[j]][i[j + 1]]:
        break

        temppath[i[j]] = i[j+1]

if ans >= 1:
  print("Yes")
  for i in range(n-1):
    print(anspath[i])
else:
  print("No")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(n)]
b=[[0]* n for j in range(n)] 
bb=[]
for i in range(n-1):
    bb.append(i)
c=[]
d=[0]*n-1
for i in range(n):
    for j in range(n):
        b[a[i][0][a[i][1]] = a[i][1]
        b[a[i][1]][a[i][0]] = a[i][0]
while len(bb)!=0:
    for i in range(n):
        if b[i][j]==1:
            c.append(b[i][j])
            bb.deque(b[i][j])
            d[b[i][j]]=i+1
            print(b[i][j]+1)

Submission status: Runtime Error

Solution code:
import copy
n, m = map( int, input().split() )
connect = []

for _ in range( n+1 ):
    connect.append( [ 0 ] * ( n+1 ) )

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

guide = [ 0 ] * ( n+1 )
path = [ 0, 0 ] + [ m+1 ] * ( n-1 )
unvisited = [ a for a in range( 1, n+1 ) ]

def solve( a, unvisited ): # aに隣接したやつのguideをaにする．またそれのpathをpath[a]+1にする．
    for b in unvisited:
        if connect[a][b] == 1 and path[a] + 1 < path[b]:
            path[b] = path[a] + 1
            guide[b] = a
    next_unvisited = copy.deepcopy( unvisited )
    next_unvisited.remove( a )
    for b in unvisited:
        if connect[a][b] == 1:
            solve( b, next_unvisited )

solve( 1, unvisited )

if 0 not in guide[2:]:
    print( "Yes" )
    for i in range( 2, n+1 ):
        print( guide[i] )
else:
    print( "No" )

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = [int(i) for i in input().split()]
rutes = [[]] * n
visited = [0] + [-1] * (n-1)
q = deque([0])

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

cnt = 0
def visit(x):
    for i in rutes[x-1]:
        if visited[i] == -1:
            q.append(i)
            visited[i-1] = visited[x-1] + 1

while len(q) > 0:
    tmp = q.pop()
    visit(tmp)

for i in range(2,n+1):
    print(visited[i-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import networkx as nx


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

    g = nx.Graph()
    for _ in range(n):
        a, b = map(int, input().split())
        g.add_edge(a, b)
    path = list(nx.bfs_edges(g, 1))

    if len(path) != n - 1:
        print('No')
        return
    print('Yes')
    for i in range(n - 2, 0, -1):
        print(path[i][0])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,M=list(map(int,(input().split())))
sign=[]
for k in range(M):
  A,B=list(map(int,(input().split())))
  sign.append(sorted([A,B]))
len_goal=[[-1,-1] for k in range(N+1)]
len_goal[1][0]=1
len_goal[1][1]=1
sign=sorted(sign)
print(sign)
for room in sign:
  if(len_goal[room[0]][0]>=len_goal[room[1]][0] and len_goal[room[1]][0]>=0):
    len_goal[room[0]][0]=len_goal[room[1]][0]+1
    len_goal[room[0]][1]=room[1]

  elif(len_goal[room[1]][0]>=len_goal[room[0]][0] and len_goal[room[0]][0]>=0):
    len_goal[room[1]][0]=len_goal[room[0]][0]+1
    len_goal[room[1]][1]=room[0]

  elif(len_goal[room[0]][0]<0 and len_goal[room[1]][0]>=0):
    len_goal[room[0]][0]=len_goal[room[1]][0]+1
    len_goal[room[0]][1]=room[1]
  elif(len_goal[room[0]][0]>=0 and len_goal[room[1]][0]<0):
    len_goal[room[1]][1]=len_goal[room[0]][0]+1
    len_goal[room[1]][1]=room[0]
ans=[]
for z in len_goal:
  ans.append(z[2]))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    from collections import deque as d
    N, M = map(int, readline().split())
    m = map(int, read().split())
    AB = zip(m, m)
    graph = [[] for _ in range(N + 1)]
    for a, b in AB:
        graph[a].append(b)
        graph[b].append(a)
    que = [1]
    stack = [1]
    ans = [0]*(N+1)
    while que:
        x = d.popleft(que)
        for i in graph[x]:
            if ans[x] == 0:
                ans[x] = x
            stack.append(i)
    for a in ans[2:]:
        if a == 0:
            print('No')
            break
    else:
        print('Yes')
        print('\n'.join(map(str, ans[2:])

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
I_list = [[0] * M for _ in range(M)]
for _ in range(M):
  A, B = map(int, input().split())
  if A < B:
    I_list[A-1][B-1] = 1
  else:
    I_list[B-1][A-1] = 1
    
ans = [0] * (M-1)
def search(root_index, ref_index):
  ref_index = []
  for i in np.where(I_list[root_index])[0]:
    if not i in ref_index:
      ans[i-1] = root_index + 1
      ref_index.append(i)
      search(i, ref_index)

search(0, [0])
if len(np.where(ans)[0]) == len(ans):
  print('Yes')
  for a in ans:
    print(a)
else:
  print('No')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
d = {}
ans = [0] * (n-1)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)
    if a == 1:
        ans[b-2] = 1
    if b == 1:
        ans[a-2] = 1

def f(c, t, alr):
    global d
    if t in alr:
        return float("INF")
    if t in d[1]:
        return c
    alr.append(t)
    for tt in d[t]:
        return f(c+1, tt, alr)

for i in range(2, n+1):
    a = float("INF")
    s = -1
    for j in d[i]:
        cost = f(1, j, [])
        if not a == min(a, cost):
            a = cost
            s = j
    if a == float("INF"):
        ans['No']
        break
    ans[i-2] = s
    
if ans[0] == 'No':
    print(ans[0])
else:
    print('Yes')
    for an in ans:
        print(an)

Submission status: Runtime Error

Solution code:
s = {1}
d = {}
a = []
b = []
n,m = map(int,input().split())
for i in range(m):
    tmp1,tmp2 = map(int,input().split())
    a.append(tmp1)
    b.append(tmp2)

ans = "Yes"
tmp = 1
while True:
    for i in range(m):
        if a[i] in s:
            s.add(b[i])
            d.setdefault(b[i], a[i])
                
        elif b[i] in s:
            s.add(a[i])
            d.setdefault(a[i], b[i])

    if tmp == len(s):
        ans = "No"
        break

    if len(d) == n-1:
        break
    tmp = len(s)

print(ans)
d2 = sorted(d.items())
for i in range(1,n):
    print(d2[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

n, m = map(int,input().split())
g =Graph()
for _ in range(m):
    x, y = map(int,input().split())
    g.add_edge(x-1,y-1,1)
    g.add_edge(y-1,x-1,1)
d = Dijkstra(g,0)

ans= [float("inf") for i in range(n)]
for i in range(m):
    x = d.shortest_distance(i)
    ans[i] = x
if float("inf") in ans:
    print('No')
else:
    print('Yes')
    for i in range(1,m):
        print(ans[i])

Submission status: Runtime Error

Solution code:
N,M=(int(x) for x in input().split())
num = [input().split() for i in range(M)]
aes = [N]

def ser(tar,num):
   j=0
   ye = []
   for j in range(len(num)):
      if num[j] == tar:
         if j%2 == 0:
           aes[num[j+1]]=tar
           num[j+1] = 0
           ye.append(num[j+1])
         else:
           aes[num[j-1]]=tar
           num[j-1] = 0
           ye.append(num[j-1])
         num[j]
         
   return ye



tu = []
tu=[]
tu[0] = 1
while len(tu) == 0:
   for j in range(len(tu)):
      if j==0:
         tu = ser(ye[j],num)
      tu.append(ser(ye[j],num))
   set(tu)

print(aes)

Submission status: Runtime Error

Solution code:

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

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

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

    ans = pred[1,2:]
    impos = any(ans >=0)
    if impos:
        print("Yes")
        print(*ans, sep="\n")
    else:
        print("No")

if __name__ == "__main__":
    resolve()