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())
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 = [-1] * (N + 1)
c = [-1] * (N + 1)
c[1] = 0


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


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:
n, m = map(int, input().split())

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import 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にする．
    # print( "calc " + str(a) )
    # print( "unvisited " + str(unvisited) )
    for b in unvisited:
        if connect[a][b] == 1 and path[a] + 1 < path[b]:
            # print( "update " + str(b) )
            path[b] = path[a] + 1
            guide[b] = a
            next_unvisited = copy.deepcopy( unvisited )
            next_unvisited.remove( a )
            # print( next_unvisited )
            solve( b, list( next_unvisited)  )

solve( 1, list( unvisited ) )

# print( guide, path )
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:
6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import copy

def input():
    return sys.stdin.readline()[:-1]

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

"""
MAP = np.zeros(N*N).reshape(N, N)

for ab in AB:
	MAP[ab[0]-1, ab[1]-1] = 1

print(MAP)
"""

ans = [[i, 0] for i in range(1, N+1)]


temae = []
rm = []
count = 0
for i, [a, b] in enumerate(AB):

	if a == 1:
		ans[b-1][1] = 1
		temae.append(b)
		rm.append(i)
		count += 1
	elif b == 1:
		ans[a-1][1] = 1
		temae.append(a)
		rm.append(i)
		count += 1

for i in sorted(rm, reverse=True):
	AB.pop(i)

while count < N-1:
	temae2 = []
	rm = []
	#print("AB", AB)
	#print("temae", temae)
	#print("ans", ans)
	for i, [a, b] in enumerate(AB):
		if a in temae:
			if ans[b-1][1] == 0:
				ans[b-1][1] = a
				temae2.append(b)
				rm.append(i)
				count += 1
			else:
				pass
		elif b in temae:
			if ans[a-1][1] == 0:
				ans[a-1][1] = b
				temae2.append(a)
				rm.append(i)
				count += 1
			else:
				pass

	if len(temae2) == 0:
		break
	else:
		for i in sorted(rm, reverse=True):
			AB.pop(i-1)
		temae = copy.copy(temae2)

print(*np.array(ans)[1:,1])

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys


def loop(num, cnt):
    if num == 1:
        if len(ans[path[0]-1]) != 0 and ans[path[0]-1][0] > len(path):
            ans[path[0]-1][0] = len(path)
            ans[path[0]-1][1] = path[1]
        elif len(ans[path[0]-1]) == 0:
            # print(path, path[0]-1)
            ans[path[0]-1].append(len(path))
            ans[path[0]-1].append(path[1])
        # ans[path[0]] = ans.get(path[0], [len(path), path[1]])
        # print(path)
        return
    else:
        for i in range(len(temp[num-1])):
            if temp[num-1][i] not in path:
                path.append(temp[num-1][i])
                # print(path)
                loop(temp[num-1][i], cnt+1)
                for j in range(cnt, len(path)-1):
                    path.pop()
                # print(path)


N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = []
B = []
temp = [[] for x in range(N)]

for i in range(M):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    temp[a-1].append(b)
    temp[b-1].append(a)
# print(temp)
ans = [[] for x in range(N)]
for k in range(2, N+1):
    cnt = 0
    path = [k]
    # print(k)
    loop(k, cnt)
print(temp)
# print(ans)
ans.remove([])
print(ans)
if len(temp)-1 == len(ans):
    print('Yes')
    for i in range(len(ans)):
        print(ans[i][1])
else:
    print('No')

Submission status: Runtime Error

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

if __name__ == '__main__':    
    N, M = map(int, input().split())
    p = np.zeros((N, N))
    for m in range(M):
        A, B = map(int, input().split())
        p[A-1, B-1] = 1
        p[B-1, A-1] = 1
    csr = csr_matrix(p)
    mat, predecessors = dijkstra(csr, directed=False, indices=0, return_predecessors=True)
    if -9999 in predecessors[1:]:
        print('No')
    else:
        print('Yes')
        for n in range(N-1):
            print(int(predecessors[n+1]+1))

Submission status: Runtime Error

Solution code:
MAX_INT = 10**6
N, M = map(int, input().split())
room = dict()
for i in range(1, N+1):
    room[i] = set()
for i in range(M):
    a, b = map(int, input().split())
    room[a].add(b)
    room[b].add(a)

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

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=list(map(int,input().split()))

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

guideposts_cost=np.array([float("inf")]*N*N).reshape(N,N)
guideposts=[0]*N

for i,g in enumerate (guideposts_cost):
    g[i]=0

# print(guideposts_cost)

for ab in AB:
    old_guideposts_cost=guideposts_cost.copy()
    guideposts_cost[ab[0]-1]=np.minimum(guideposts_cost[ab[0]-1],guideposts_cost[ab[1]-1]+1)
    guideposts_cost[ab[1]-1]=np.minimum(guideposts_cost[ab[1]-1],guideposts_cost[ab[0]-1]+1)
    if guideposts_cost[ab[0]-1][0]!=old_guideposts_cost[ab[0]-1][0]:
        guideposts[ab[0]-1]=ab[1]
    if guideposts_cost[ab[1]-1][0]!=old_guideposts_cost[ab[1]-1][0]:
        guideposts[ab[1]-1]=ab[0]
    # print(guideposts_cost)
    # print(old_guideposts_cost)

for ab in AB:
    old_guideposts_cost=guideposts_cost.copy()
    guideposts_cost[ab[0]-1]=np.minimum(guideposts_cost[ab[0]-1],guideposts_cost[ab[1]-1]+1)
    guideposts_cost[ab[1]-1]=np.minimum(guideposts_cost[ab[1]-1],guideposts_cost[ab[0]-1]+1)
    if guideposts_cost[ab[0]-1][0]!=old_guideposts_cost[ab[0]-1][0]:
        guideposts[ab[0]-1]=ab[1]
    if guideposts_cost[ab[1]-1][0]!=old_guideposts_cost[ab[1]-1][0]:
        guideposts[ab[1]-1]=ab[0]
    # print(guideposts_cost)

# print(guideposts_cost)
# print(guideposts)

if 0 in guideposts[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1,len(guideposts)):
        print(int(guideposts[i]))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**10)
N,M = map(int,input().split())
R = [[] for _ in range(N)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for _ in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(que):
    if que==[]:
        return
    i = que[0]
    for j in R[i-1]:
        if ans[j-1]==0:
            ans[j-1]=i
            que.append(j)
    que.pop(0)
    bfs(que)
    
bfs(queue)
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')
        return
    else:
        print('Yes')
    for v in visit[1:]:
        print(v)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import os
import bisect, collections, copy, itertools, math, string
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int, input().split()))
def LS(): return list(input().split())

def solve():
	n, m = LI()
	a = []
	for i in range(m):
		c, d = LI()
		a.append((c-1, d-1))

	# 隣接行列の作成
	l = np.zeros((n,n))
	for _a in a:
		l[_a[0]][_a[1]] = 1
		l[_a[1]][_a[0]] = 1

	d, p = shortest_path(l, return_predecessors=True)

	def get_path(start, goal, pred):
		return get_path_row(start, goal, pred[start])

	def get_path_row(start, goal, pred_row):
		path = []
		i = goal
		while i != start and i >= 0:
			path.append(i)
			i = pred_row[i]
		if i < 0:
			return []
		path.append(i)
		return path[::-1]

	dic = {}
	flag = True
	for i in range(1, n):
		path = get_path(0, i, p)
		path.reverse()
		for j in range(len(path)-1):
			dic.setdefault(path[j]+1, path[j+1]+1)
			if not dic[path[j]+1] == path[j+1]+1:
				print('No')
				return
	print('Yes')
	for i in range(2, n+1):
		print(dic[i])







if __name__ == '__main__':
	solve()

Submission status: Runtime Error

Solution code:
import math
import numpy as np

N, M = list(map(int, input().split()))
route_list = np.ones((N, N))*10000000
for i in range(M):
    Ai, Bi = list(map(int, input().split()))
    route_list[Ai-1, Bi-1] = 1

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [math.inf] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

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

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

print("Yes")
for i in range(N-1):
    print(previous_nodes[i+1] + 1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

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

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



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

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

tf = kamban_okude(1, i)

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(200000)
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]
            road_dict[kiten].remove(i)
            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 search(rooms, li, anss, count):
    count += 1
    for l in li:
        if anss[l] == 0:
            anss[l] = count
            search(rooms, rooms[l], anss, count)
    return anss


def main():
    n, m = map(int, input().split())
    rooms = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        rooms[b].append(a) 
        rooms[a].append(b)
    anss = [0]*(n+1)
    li = rooms[1]
    count = 0
    anss = search(rooms, li, anss, count)
    if 0 in anss[1:]:
        print("No")
    else:
        print("Yes")
        for ans in anss[1:]:
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math

N, M = list(map(int, input().split()))
route_list = np.ones((N, N))*10000000
for i in range(M):
    Ai, Bi = list(map(int, input().split()))
    route_list[Ai-1, Bi-1] = 1

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [math.inf] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

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

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

print("Yes")
for i in range(N-1):
    print(previous_nodes[i+1] + 1)

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()

	for to in G[fm]:
		if (X[to][1] > X[fm][1]+1):
			X[to][0] = fm
			X[to][1] = X[fm][1] + 1
			Q.append(to)
			continue
		
		if (X[to][1]+1 < X[fm][1]):
			X[fm][0] = to
			X[fm][1] = X[to][1] + 1
			Q.append(fm)
			continue


#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)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main(int argc, char const *argv[]) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> path(n);
    int ans[n] = {-1}; // 距離を格納するリスト
    REP(i,n)
        ans[i] = -1;
    
    queue<int> que;
    
    REP(i,m) 
    {
        int a,b;
        cin >> a >> b;
        path[a-1].PB(b-1);
        path[b-1].PB(a-1);
    }
    que.push(0);

    // cout << endl;
    // REP(i,SIZE(path))
    // {   
    //     cout << i << " ";
    //     REP(j,SIZE(path[i]))
    //     {
    //         cout << path[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    ans[0] = 0;
    while (!que.empty())
    {
        int now = que.front(); //現在の場所
        que.pop();
        // cout << "here is top of roop" << endl;
        // cout << "que size" << que.size() << endl; 
        // cout << "now" << now  << endl;
        

        // if (que.size() > 100)
        //     break;

        REP(i,SIZE(path[now]))
        {
            int tmp = path[now][i];
            if (tmp == now) continue;
            if (ans[tmp] != -1)
                continue;
            else
            {
                ans[tmp] = now;
                que.push(tmp);
            }
            // 個々提出前に米
            // cout << "This is test " << now << " " << tmp << endl;
            // REP(i,n)
            //     cout << ans[i] << " ";
            // cout << endl;
        }
    }

    REP(i,n)
    {
        if (ans[i] == -1)
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    
    FOR(i,1,n-1)
        cout << ans[i]+1 << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=list(map(int,input().split()))

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

guideposts_cost=np.array([float("inf")]*N*N).reshape(N,N)
guideposts=[0]*N

for i,g in enumerate (guideposts_cost):
    g[i]=0

# print(guideposts_cost)

for ab in AB:
    old_guideposts_cost=guideposts_cost.copy()
    guideposts_cost[ab[0]-1]=np.minimum(guideposts_cost[ab[0]-1],guideposts_cost[ab[1]-1]+1)
    guideposts_cost[ab[1]-1]=np.minimum(guideposts_cost[ab[1]-1],guideposts_cost[ab[0]-1]+1)
    if guideposts_cost[ab[0]-1][0]!=old_guideposts_cost[ab[0]-1][0]:
        guideposts[ab[0]-1]=ab[1]
    if guideposts_cost[ab[1]-1][0]!=old_guideposts_cost[ab[1]-1][0]:
        guideposts[ab[1]-1]=ab[0]
    # print(guideposts_cost)
    # print(old_guideposts_cost)

for ab in AB:
    old_guideposts_cost=guideposts_cost.copy()
    guideposts_cost[ab[0]-1]=np.minimum(guideposts_cost[ab[0]-1],guideposts_cost[ab[1]-1]+1)
    guideposts_cost[ab[1]-1]=np.minimum(guideposts_cost[ab[1]-1],guideposts_cost[ab[0]-1]+1)
    if guideposts_cost[ab[0]-1][0]!=old_guideposts_cost[ab[0]-1][0]:
        guideposts[ab[0]-1]=ab[1]
    if guideposts_cost[ab[1]-1][0]!=old_guideposts_cost[ab[1]-1][0]:
        guideposts[ab[1]-1]=ab[0]
    # print(guideposts_cost)

print(guideposts_cost)
print(guideposts)

if 0 in guideposts[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1,len(guideposts)):
        print(int(guideposts[i]))

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)]
  done = {}
  next_ = [1]
  #cost[1] = 0

  while next_:
    now_pos = next_.pop(0)
    for next_pos in root[now_pos]:
      try:
        a = done[next_pos]
      except KeyError:
        #cost[next_pos] = cost[now_pos] + 1
        mitisurube[next_pos] = now_pos
        next_.append(next_pos)
        done[next_pos] = 1
  #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())

li = []
for i in range(M):
    li.append(list(map(int,input().split())))
ans = [0] * (N+1)
#print(ans)
que = [1]
#print(li)
def saiki ():
    global que
    global li
    global ans
    #print(que)
    q = que.pop(0)
    count = 0
    while True:
        
        if count == len(li):
            break
        #print(li)
        #print(count)
        if li[count][0] == q and ans[li[count][1]] == 0:
            que.append(li[count][1])
            ans[li[count][1]] = q
            li.pop(count)
        elif li[count][1] == q and ans[li[count][0]] == 0:
            que.append(li[count][0])
            ans[li[count][0]] = q
            li.pop(count)
        else:
            count += 1
    if len(que) == 0:
        print("Yes")
        for ai in ans:
            if ai != 0:
                print(ai)
    else:
        saiki()






saiki()

Submission status: Runtime Error

Solution code:
import math
import numpy as np
N, M = (int(i) for i in input().split())  

arr = np.array([[0] * N] * N)

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

lis = [-1] * (N-1)
def recur(bef, visit_list):
  all_visited = True
  #print(bef, visit_list)
  for i, x in enumerate(arr[bef-1]):
    if x and i+1 not in visit_list:
      recur(i+1, visit_list + [bef])
      lis[i+1 - 2] = bef
      all_visited = False
      
  if all_visited:
    return
  
recur(1, [])
if -1 in lis:
  print('No')
else:
  print('Yes')
  for x in lis:
    print(x)

Submission status: Runtime Error

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

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

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


goal = 1
rets = []
road = {i:[] for i in range(1, N+1)}

for A, B in AB:
    road[A] += [B]
    road[B] += [A]

ret, retind = [], []

def dfs(ind, inds, dis):

    global goal, ret, retind

    if ind == goal:
        ret += [dis]
        retind += [inds]
    
    if ind in inds:
        return

    inds += [ind]
    dis += 1
    for i in road[ind]:
        dfs(i, copy.copy(inds), dis)

for start in range(2, N+1):
    ret, retind = [], []
    dfs(start, [], 0)
    rets += [retind[ret.index(min(ret))][1]]

if not rets:
    print("No")
else:
    print("Yes")
    for i in rets:
        print(i)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
L = [[] for _ in range(N+1)]
for _ in range(N):
    a, b = map(int, input().split())
    L[a].append(b)
    L[b].append(a)

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

while len(now):
    for x in now:
        for y in L[x]:
            if (y not in now) and (ans[y] == 0):
                ans[y] = x
                next.append(y)
    now = next.copy()
    next = []

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

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]
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 and l[0] != l[1]:
                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])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
    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")

Submission status: Runtime Error

Solution code:
from collections import deque

R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = 'Yes' + [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = deque([0])
while q:
  u = q.popleft()
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v] = u + 1
      q.append(v)

print(*(['No'], r)[all(r)], sep='\n')