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
import heapq

def dijkstra_heapq(graph,node_count,start_index):
    #INF = np.sum(graph) + 1
    INF = 10**9+7
    node = [[INF,i] for i in range(node_count)]
    const_node = [[INF,-1] for i in range(node_count)]

    node[start_index][0] = 0
    heapq.heapify(node)

    print(const_node)

    while len(node) > 0:
        sub_dist,min_node_dex = heapq.heappop(node)
        const_node[min_node_dex][0] = sub_dist

        for i in range(len(node)):
            if g[min_node_dex][node[i][1]] > 0:
                    new_dist = sub_dist + g[min_node_dex][node[i][1]]
                    if new_dist < node[i][0]:
                        node[i][0] = new_dist
                        const_node[node[i][1]][1] = min_node_dex

        print(const_node)

    return const_node

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

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

        change = False

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

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

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

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
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)

  while q.qsize() > 0:
    current = q.get()
    for nxt in edges[current]:
      if nxt not in visited:
        visited[nxt] = current
        q.put(nxt)

  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:
def saiki(visited, inv, path, nows):
  buf = []
  for now in nows:
    for p in path[now]:
      if p not in visited:
        buf.append(p)
        visited.append(p)
        inv[p].append(now)
  if len(buf)==0:
    return
  saiki(visited, inv, path, buf)
  
N, M = map(int, input().split())

inv = {i :[] for i in range(2, N+1)}
visited = [1]

path = {i :[] for i in range(1, N+1)}
for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
saiki(visited, inv, path, [1])
print("yes")
for _,i in inv.items():
  print(i[0])

Submission status: Runtime Error

Solution code:
inf = 10**5+1
n,m = map(int,input().split())
p = [inf]*n
for _ in range(n):
  a,b = map(int,input().split())
  A = max(a,b)
  B = min(a,b)
  if p[A-1] > B:
    p[A-1] = B
  if p[B-1] > A:
    p[B-1] = A
p[0] = 'Yes'
if max(p[1:]) == 10**5+1:
  print('No')
else:
  for i in range(len(p)):
    print(p[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_ = []
                
            for c in check:
                connect = np.nonzero(edge[c])[0]
                nogo = np.nonzero(room)[0]
                if len(nogo)==0:
                    flag = 0
                    break
                
                for con in list(set(connect)&set(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:
                flag = 0
                break
            else:
                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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

n,m=getNM()
a=[]
b=[]
c=[0]*(n+1)
x=[]
for i in range(m):
    a1,b1=getNM()
    a.append(a1)
    b.append(b1)
    if a1==1:
        c[b1]=1
        x.append(b1)
    elif b1==1:
        c[a1]=1
        x.append(a1)


for i in range(1,n):
    xxx=c
    for j in range(m):
        print(i,j)
        if c[a[j]]==i and c[b[j]]==0:
            c[b[j]]=a[j]
        elif c[b[j]]==i and c[a[j]]==0:
            c[a[j]]=b[j]
        print(c)
    if xxx[2:]==c[2:]:
        break

if 0 in c[2:]:
    print('No')
    exit()
print('Yes')
for i in range(n-1):
    print(c[2:][i])

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]

    def dfs(self,i,rank):
        for r in self.route[i]:
            if rank<self.dp[r][1] and rank<self.N:
                self.dp[r] = [i,rank]
                self.dfs(r,rank+1)
        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:
n,m = map(int,input().split())
R =[]
r = []
for i in range(m):
    s = list(map(int,input().split()))
    r.append([s])
N = [0 for i in range(n)]
for i in range(m):
    if 1 in r[i]:
        a = r.index(1)
        N[1-a] = 1
        R.append(i)
for i in range (len(R)):
    r.pop(r[R[i]])
    R = []
while True:
    if r == []:
        if 0 in N:
            print ('No')
            break
        else:
            print('Yes')
            for i in range (n):
                print(r[i])
            break
    else:
        for i in range (len(r)):
            if N[r[i][0]]!=0 and N[r[i][0]]==0:
                N[r[i][1]] = N[r[i][0]]+1
                R.append(i)
            elif N[r[i][1]]!=0 and N[r[i][0]]==0:
                N[r[i][0]] = N[r[i][1]]+1
                R.append(i)
            elif N[r[i][1]]!=0 and N[r[i][0]]!=0:
                R.append(i)
        for i in range (len(R)):
            r.pop(r[R[i]])
            R = []

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = [int(i) for i in input().split()]

e = np.zeros([n,n])



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

ans = np.ones(n-1)
next_cand = [0]
cout = 0
check = np.zeros(n-1)
for next_ in next_cand:
    connec = np.array([j for j in e[next_,:] if j !=0])
    for i in connec:
        i = int(i)
        if check[i-1] == 0:
            check[i-1] = 1
            cout +=1
            ans[i-1] = next_ +1
            next_cand.append(i)
            e[next_,:] = 0
            e[:,next_] = 0


print('Yes')

for i in ans:
    print(int(i))

Submission status: Runtime Error

Solution code:
import math
import sys

def rec(rooms, num, distance):
    f = False
    for roomnum in rooms[num]:
        if roomnum not in shirube or distance + 1 < shirube[roomnum][1]:
            shirube[roomnum] = (num, distance + 1)
            f = True
    
    if f:
        for roomnum in rooms[num]:
            rec(rooms, roomnum, distance + 1)


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

rooms = {}

for cor in [tuple(map(int,input().split())) for i in range(M)]:
    rooms.setdefault(cor[0], set())
    rooms[cor[0]].add(cor[1])
    rooms.setdefault(cor[1], set())
    rooms[cor[1]].add(cor[0])

shirube = {}
shirube[1] = (0, 0)

rec(rooms, 1, 0)

if any([i not in shirube for i in range(2, N+1)]):
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(shirube[i][0])

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,return_predecessors=True)[1][0]
print('Yes')

sp+=1
for i in range(1,len(sp)):
    print(sp[i])

Submission status: Runtime Error

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

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

from collections import deque
def bfs(u):
    
    q = deque()
    q.append(u)
    while q:
        r = q.pop()
        for v in R[r]:
            if V[v]:
                V[v] = False
                S[v] = r
                q.append(v)

bfs(0)
print("Yes")
for i in range(1,N):
    print(S[i]+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)

from collections import deque

Q = deque()

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

while Q:
	fm = Q.popleft()
	for to in G[fm]:
	
		if X[to]==0:
			X[to] = fm
			Q.append(to)

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

Y = X[2:]
if min(Y)==0:
	print("No")
else:
	print("Yes")
	for y in Y:
		print(y)

Submission status: Runtime Error

Solution code:
import math

N, M = map(int, input().split())
route = [[] for _ in range(N)]
mark = [(None, math.inf) for _ in range(N)]
mark[0] = (-1, 0)

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


def mark_to_the_other(current, route, mark):
    current_cost = mark[current][1]
    for to in route[current]:
        if mark[to][1] > current_cost + 1:
            mark[to] = (current, current_cost + 1)
            mark = mark_to_the_other(to, route, mark)
    return mark


mark = mark_to_the_other(0, route, mark)

if any(map(lambda x: x[0] is None, mark)):
    print("No")
else:
    print("Yes")
    [print(m[0] + 1) for m in mark[1:]]

Submission status: Runtime Error

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

road = {k:[] for k in range(1,n+1)}
for _ in range(m):
  a,b = map(int,input().split())
  road[a].append(b)
  road[b].append(a)

def check_num(road_set):
  num = 0
  for i in list(road_set.keys()):
    visited = [i]
    next_room = road_set[i]
    num += 1
    while True:
      
      if next_room in visited:
        return -1
      
      if next_room == 1:
        break
        
      visited.append(next_room)
      next_room = road_set[next_room]
      num += 1
  return num


def rec(i,road_set):
  if i == n+1:
    num = check_num(road_set)
    global min_num,min_road
    if num > 0 and (min_num == None or min_num>num):
      min_num = num
      min_road = road_set.copy()
    return
     
  if 1 in road[1]:
    road_set[i] = 1
    rec(i+1,road_set)
  else:
    for r in road[i]:
      road_set[i] = r
      rec(i+1,road_set)
    
min_num = None
min_road = None

rec(2,{})
if min_num == None:
  print('No')
else:
  print('Yes')
  for v in min_road.values():
    print(v)

Submission status: Runtime Error

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

n, m = map(int, input().split())
paths = []

while True:
    try:
        paths.append(list(map(int, input().split())))
    except EOFError:
        break


aj_matrix = np.zeros((n, n), dtype=int)
for path in paths:
    aj_matrix[path[0] - 1][path[1] - 1] = 1
    aj_matrix[path[1] - 1][path[0] - 1] = 1
d, p = shortest_path(aj_matrix, indices=0, return_predecessors=True)

if np.isinf(d).sum() == 0:
    result = [i + 1 for i in p.astype(int)]
    print('Yes')
    print(*result[1:], sep='\n')
else:
    print('No')

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ans = {i:0 for i in range(1,N+1)}
ans[1] = 10000000
route = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
x = [1]
for _ in range(M):
    for i in x:
        tmp = []
        for j in route[i]:
            #print(j)
            count = 0
            if ans[j] == 0:
                ans[j] = i
                count += 1
            tmp.append(j)
    x = tmp
    #print(ans,x)
    if count = 0:
        break
print('Yes')
for i in ans.keys():
    if i != 1:
        print(ans[i])

Submission status: Runtime Error

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

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

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

def write_result(marks, N):
    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')

import numpy


N, M, d = get_input()

marks = {0:0}
try:
    marks = func(0, d, {0: 0})
    write_result(marks, N)
except:
    pass

Submission status: Runtime Error

Solution code:
import sys
N,M = list(map(int, sys.stdin.readline().rstrip().split())) 

path = [0] * (N)
dist = [10**6] * (N)
C=[]
for n in range(N):
  A,B = list(map(int, sys.stdin.readline().rstrip().split())) 
  A, B = min(A,B), max(A,B)
  if A == 1:
    path[B-1] = 1
    dist[B-1] = 1
  elif path[A-1]  != 0:
    dist2 = dist[A-1] +1
    if dist2 < dist[B-1]:
      path[B-1] = A
      dist[B-1] = dist2
  elif path[B-1]  != 0:
    dist2 = dist[B-1] +1
    if dist2 < dist[A-1]:
      path[A-1] = B
      dist[A-1] = dist2
  else:
    C.append([A,B])
#print(C)
L = len(C)
while C:
  A,B = C.pop()
  A, B = min(A,B), max(A,B)
  if path[A-1]  != 0:
    dist2 = dist[A-1] +1
    if dist2 < dist[B-1]:
      path[B-1] = A
      dist[B-1] = dist2
  elif path[B-1]  != 0:
    dist2 = dist[B-1] +1
    if dist2 < dist[A-1]:
      path[A-1] = B
      dist[A-1] = dist2
  else:
    C.append([A,B])

print('Yes')
for p in path[1:]:
  print(p)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

import queue

def main():
    N, M = map(int, input().split())

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

    answer_list = [ -1 for i in range(N)]
    answer_list[0] = 0

    next_rooms_queue = queue.Queue()
    next_rooms_queue.put(0)
    now_room = int()
    while not next_rooms_queue.empty():
        now_room = next_rooms_queue.get()
        for i in connedted_room_list[now_room]:
            if answer_list[i] == -1:
                answer_list[i] = now_room
                next_rooms_queue.put(i)

    is_escapable = True
    for i in range(1, N):
        if answer_list[i] == -1:
            is_escapable = False
            break
    
    if is_escapable:
        print("Yes")
        for i in range(1, N):
            print(answer_list[i]+1)
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

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

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

Submission status: Runtime Error

Solution code:
from collections import deque
    
def bfs(graph,start): #def bfs(graph,start,limit): 
    dist = [-1] * (N)
    ans = [-1] *(N)
    dist[start]= 0
    q = deque([start])
    cnt = 0
    while q:
        x = q.popleft()
        for i in graph[x]:
            #if dist[x] >= limit:
            #    break
            if dist[i] == -1:
                dist[i] = dist[x] + 1
                ans[i] = x+1
                q.append(i)
    return dist, ans

N,M  = map(int,input().split())# 頂点数
X = [[] for i in range(M)] #辺リスト
P = [[] for i in range(M)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

dist,ans = bfs(X,0)
#print(dist,ans)
if -1 in dist:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(ans[i])

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.extend(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:

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

def get_input():
    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
    return N, M, d

def write_result(marks, N):
    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')

import numpy


N, M, d = get_input()

marks = {0:0}
try:
    marks = func(0, d, {0: 0})
    write_result(marks, N)
except:
    pass

Submission status: Runtime Error

Solution code:
import math

S = input().split()
A=float(S[0])
B=float(S[1])
H=float(S[2])
M=float(S[3])
siita=(H*60+M)/2-M*6;
if(siita>180):
    siita=360-siita
ans=math.sqrt(A*A+B*B-2*A*B*math.cos(siita*3.141592653589793238462643383279/180))
print(ans)

Submission status: Runtime Error

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

road = {k:[] for k in range(1,n+1)}
for _ in range(m):
  a,b = map(int,input().split())
  road[a].append(b)
  road[b].append(a)
  


def check_num(road_set):
  num = 0
  for i in list(road_set.keys()):
    visited = [i]
    next_room = road_set[i]
    num += 1
    while True:
      
      if next_room in visited:
        return -1
      
      if next_room == 1:
        break
        
      visited.append(next_room)
      next_room = road_set[next_room]
      num += 1
  return num


def rec(i,road_set):
  if i == n+1:
    num = check_num(road_set)
    global min_num,min_road
    if num > 0 and (min_num == None or min_num>num):
      min_num = num
      min_road = road_set.copy()
    return
      
  for r in road[i]:
    road_set[i] = r
    rec(i+1,road_set)
    
min_num = None
min_road = None

rec(2,{})
if min_num == None:
  print('No')
else:
  print('Yes')
  for v in min_road.values():
    print(v)

Submission status: Runtime Error

Solution code:
visited = [False for _ in range(N)]
que = [1]
visited[0] = True
sign = [-1 for _ in range(N)]

while True:
    next_que = []
    if not que:
        break
#     for q in que:
#         probable_room = path[q-1]
#         for p in probable_room:
    else:
        for q in que:
            probable_room = path[q-1]
            for p in probable_room:
#                 if p == q:
#                     continue
                if visited[p-1]:
                    continue
                else:
#                 print(1111)
                    visited[p-1] = True
                    sign[p-1] = q
                    next_que.append(p)
    que = next_que
if all(visited):
    print("Yes")
    for i in range(1,N):
        print(sign[i])
else:
    print("No")

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
l = {}
for i in range(M):
    a,b = [int(j) for j in input().split()]
    a -= 1
    b -= 1
    if a in l:
        l[a].append(b)
    else:
        l[a] = [b]
    if b in l:
        l[b].append(a)
    else:
        l[b] = [a]
ans = [10**8] * N
def search(idx, num):
    if ans[idx] > num:
        ans[idx] = num
    for i in l[idx]:
        if ans[i] < num + 1:
            continue 
        search(i, num+1)

search(0, 0)
ret = []
for i in range(1,N):
    for j in l[i]:
        if ans[j] == ans[i] - 1:
            ret.append(j+1)
            break

if len(ret) == N - 1:
    print("Yes")
    for i in ret:
        print(i)
else:
    print("No")

Submission status: Runtime Error

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



r=list()
for i in range(m):
    a=list()
    r.append(a)
a=list()
for i in range(n):
    a.append(-1)
for i in range(m):
    x=0;y=0
    x,y=map(int,input().split())
    x-=1
    y-=1
    r[x].append(y)
    r[y].append(x)
    

a[0]=0
now=[0]
while len(now)!=0:
    nex=list()
    for i in now:
        for j in r[i]:
            if a[j]==-1:
                a[j]=i
                nex.append(j)
    now=nex


if -1 in a:
    print('No')
else:
    print('Yes')
    for item in a[1:]:
        print(item+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]
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:
# セル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

def get_input():
    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
    return N, M, d

def write_result(marks, N):
    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')

import numpy


N, M, d = get_input()

marks = {0:0}
try:
    marks = func(0, d, {0: 0})
except:
    pass

write_result(marks, N)

Submission status: Runtime Error

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

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    print(YES)
    met = [[] for _ in range(N)]
    for i in range(N+1):
        met[A[i]-1].append(B[i]-1)
        met[B[i]-1].append(A[i]-1)
    finished = {0}
    q = [0]
    ans = [[] for _ in range(N)]

    while q:
        next_q = []
        while q:
            qq = q.pop()
            while met[qq]:
                qqq = met[qq].pop()
                if qqq in finished:
                    continue
                next_q.append(qqq)
                ans[qqq] = qq
                finished.add(qqq)
            
        q = next_q

    for i in range(1, N):
        print(ans[i] + 1)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
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())
AB = [list(map(int,input().split())) for i in range(M)]

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