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 = [int(x) for x in input().split()]


route = {}

for i in range(M):
    A, B = [int(x) for x in input().split()]

    if A in route:
        route[A].append(B)
        #step[A] = -1
    else:
        route[A] = [B]    

    if B in route:
        route[B].append(A)
    else:
        route[B] = [A]  

step = {}
stepcount = 0
mark = {1: 0}
r = 1

def check(stepcount, r, mark):
    stepcount += 1
    if r in route:
        for nextr in route[r]:
            # print(nextr)
            # print(route[nextr])
            if nextr in step:
                # 既存のルートが有る
                if step[nextr] > stepcount:
                    # 今回のルートのほうが近い
                    step[nextr] = stepcount
                    mark[nextr] = r

            else:
                # ルートが無い
                step[nextr] = stepcount
                mark[nextr] = r
                check(stepcount, nextr, mark)
import time
time.sleep(2)
check(0, 1, mark)

# print(step)
# print(route)
# print(mark)

if len(mark) == N:
    print('Yes')
    for i in range(2, N + 1):
        print(mark[i])
else:
    print('No')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0]
b = [0]
for i in range(1, m+1):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)
dir = [[] for _ in range(m+1)]
for i in range(1, m+1):
    dir[a[i]].append(b[i])
    dir[b[i]].append(a[i])
ans = [0 for i in range(n+1)]
flag = [0 for i in range(n+1)]
flag[1] = 1
que = [1]
while len(que) != 0:
    #print('que: ', len(que), que)
    now = que.pop()
    flag[now] = 1
    for to in dir[now]:
        if flag[to] != 1 or not (to in que):
            que.append(to)
            flag[to] != 1
            ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

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

V = [[] for _ in range(M)]

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

from collections import deque

q = deque([0])

ans = [-1]*N
ans[0] = 0

while q:
    v = q.popleft()
    for nv in V[v]:
        if ans[nv] == -1:
            ans[nv] = v + 1
            q.append(nv)

print("Yes")
print(*ans[1:],sep="\n")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[[] for x in range(n)]
for c in range(M):
    a,b= map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

ans_list=[-1]*n

queue=[0]

while queue:
    qi=queue.pop(0)
    for gi in g[qi]:
        if ans_list[gi]==-1:
            queue.append(gi)
            ans_list[gi]=qi

print("Yes")
for ans in ans_list[1:]:
    print(ans+1)

Submission status: Runtime Error

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def g(i):
    for j in graph[i]:
        next = []
        if 1 in graph[j]:
            return j
            break
            #print(j)
        else:
            next.append(j)
    if next != []:
        next = set(next)
        for k in next:
            g(k)

N,M = LI()
#print(N,M)
AB = list(LI() for _ in range(M))
#print(AB)

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

for i in AB:
    a = i[0]
    b = i[1]
    graph[a] += [b]
    graph[b] += [a]

#print(graph)
print("Yes")
for i in range(2,N+1):
    #print(i)
    if 1 in graph[i]:
        print(1)
    else:
        print(g(i))

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
n,m=list(map(int,input().split()))
A=[0]*m
B=[0]*m
ans=[0]*n
for i in range(m):
  A[i],B[i]=list(map(int,input().split()))
C=A.copy()
C.extend(B)
root=1
R=[]
for room in range(1,n+1):
  L= [j for j,k in enumerate(B) if k==root]
  if L==[]:
    exit()
  for l in L:
    if ans[B[l]]0=0:
      ans[B[l]]=root
 	  R.append(B[l])
    
print(A,B)

Submission status: Runtime Error

Solution code:
# coding: utf-8
INF = float('inf')
#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []
#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)
#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True
#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [INF for _ in range(N)]

#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if depth == N - 1:
        return 1
    visited[now] = min(visited[now], depth)
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)
    return total_paths

# 複数経路の記録完了
dfs(0, 0)

if INF in visited:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(visited[i])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0]
b = [0]
for i in range(1, m+1):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)
dir = [[] for _ in range(m+1)]
for i in range(1, m+1):
    dir[a[i]].append(b[i])
    dir[b[i]].append(a[i])
ans = [0 for i in range(n+1)]
flag = [0 for i in range(n+1)]
flag[1] = 1
que = [1]
while len(que) != 0:
    #print('que: ', len(que), que)
    now = que.pop()
    flag[now] = 1
    for to in dir[now]:
        if flag[to] != 1 and not (to in que):
            que.append(to)
            flag[to] != 1
            ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int,input().split())
adj = [[] for i in range(M)]

for _ in range(M):
    temp = list(map(int,input().split()))
    temp[0]-=1
    temp[1]-=1
    adj[temp[0]].append(temp[1])
    adj[temp[1]].append(temp[0])
INF = N*N
visited = [0]*N
sirube = [-1]*N
sirube
d = deque()
d.append(0)
def bfs():
    tmp = d.pop()
    for node in adj[tmp]:
        if visited[node] !=1:
            d.append(node)
            visited[node] = 1
            sirube[node] = tmp
                    
for _ in range(N):
    bfs()
if -1 in sirube[1:N]:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(sirube[i]+1)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# ab = [list(map(int, input().split())) for i in range(n)]
# n = int(input())
# n, m = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
room = [[] for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    room[a-1].append(b-1)
    room[b-1].append(a-1)


def search(i):
    q = deque()
    q.append(i)
    while q:
        x = q.popleft()
        if 0 in room[x]:
            return x
        else:
            for i in range(len(room[x])):
                q.append(room[x][i])


print("Yes")
for i in range(1, n):
    if 0 in room[i]:
        print(1)
    else:
        a = search(i)
        print(a+1)

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 = [-1] * N
S[0] = 0
A = np.zeros([N,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(N):
            if A[x[i], j] == 1 and S[j] == -1:
                S[j] = x[i]
                y.append(j)
    x = y

flag = 0
for i in range(1, len(S)):
    if S[i] == -1:
        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:
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, 0) for i in range(n)]
def trace(no, lv):
    lst = d[no]
    for c in lst:
        if c != 1:
            dig = (r[c-1][0] == 0 and c != 1)
            if r[c-1][0] == 0 or r[c-1][1] > lv:
                r[c-1] = (no, lv)
                if dig:
                    trace(c, lv + 1)
trace(1, 1)

if 0 in r[1:]:
    print('No')
else:
    print('Yes')
    for s,_ in r[1:]:
        print(s)

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

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]

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)
flag = 0
ans = []
for i in range(1, n):
    michi = get_path(0, i, p)
    if len(michi) == 0:
        print('No')
        flag = 1
        break
    else:
        ans.append(michi[-2]+1)
        print(ans)
if flag == 0:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int,input().split())
adj = [[] for i in range(M)]

for _ in range(M):
    temp = list(map(int,input().split()))
    temp[0]-=1
    temp[1]-=1
    adj[temp[0]].append(temp[1])
    adj[temp[1]].append(temp[0])
INF = N*N
visited = [0]*N
sirube = [-1]*N
sirube
d = deque()
d.append(0)
def bfs():
    tmp = d.pop()
    for node in adj[tmp]:
        if visited[node] !=1:
            d.append(node)
            visited[node] = 1
            sirube[node] = tmp
                    
while len(list(d)) != 0:
    bfs()
if -1 in sirube[1:N]:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(sirube[i]+1)

Submission status: Runtime Error

Solution code:
import sys

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

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

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

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

dfs(tree, 0)

for i in range(1, N):
  print('Yes')
  print(sign_list[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
    self.dire = 0
  def add(self, con):
    self.connected.append(con)
  def showinfo(self):
    #print('[Room.showinfo]')
    print(str(self.num)+' '+str(self.connected)+' : '+str(self.first)) 

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(ma[s-1]==1):
    return
  ma[s-1]+=1
  
  if(Rl[s-1].num == 1):
    Rl[0].dire = 0
    
  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)
    if(Rl[ Rl[s-1].connected[i]-1 ].first == Rl[s-1].first+1):
      Rl[ Rl[s-1].connected[i]-1 ].dire = Rl[s-1].num
  for i in range(leng):
    dijkstra(Rl[s-1].connected[i])

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

Submission status: Runtime Error

Solution code:
import sys

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

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

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

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

dfs(tree, 0)

for i in range(1, N):
  	print('Yes')
    print(sign_list[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 reversed(list(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=map(int,input().split())
AB = []
for i in range(M):
    AB.append(list(map(int,input().split())))
ans=[0]*(N+1)
count=[0]*(N+1)
for j in range(N):
    if 1 in AB[j]:
        AB[j].remove(1)
        ans[AB[j][0]]=1
        count[AB[j][0]]=1
        AB[j].append(1)
for n in range(2,N+1):
    for c in ([ii for ii, x in enumerate(ans) if x==n-1]):
        for jj in range(M):
            if c in AB[jj]:
                AB[jj].remove(c)
                if ans[AB[jj][0]]==0:
                    ans[AB[jj][0]] = n
                    count[AB[jj][0]]=c
                AB[jj].append(c)
if ans.count(0)<=2:
    print("Yes")
    for aaa in range(2,N+1):
        print(count[aaa])
else:
    print("No")

Submission status: Runtime Error

Solution code:
def check(room_checked):
    for i in room_checked:
        if not i:
            return True
    return False


raw_input = list(map(int, input().strip().split()))
n = raw_input[0]
m = raw_input[1]
# lines = [[False for _ in range(m)] for __ in range(m)]
lines = {i: [] for i in range(m)}
for i in range(m):
    line = list(map(int, input().strip().split()))
    a = line[0] - 1
    b = line[1] - 1
    lines[a].append(b)
    lines[b].append(a)
is_checked_room = [False for _ in range(n)]
sign = [0 for _ in range(n)]
queue = [0]
while check(is_checked_room):
    target = queue[0]
    queue.pop(0)
    is_checked_room[target] = True
    line = lines[target]
    for l in line:
        if not is_checked_room[l]:
            is_checked_room[l] = True
            sign[l] = target
            queue.append(l)
    if not queue:
        print('No')
        break
else:
    print('Yes')
    for i in range(1, n):
        print(sign[i] + 1)

Submission status: Runtime Error

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

def makesign(room, rw_lst, sign_lst, check_lst):
    check_lst[room] = True
    newways = []
    for way in rw_lst[room]:
        if sign_lst[way] == -1:
            newways.append(way)
            sign_lst[way] = room
    rw_lst[room] = newways

    for way in rw_lst[room]:
        makesign(way, rw_lst, sign_lst, check_lst)

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

    sign_lst = [-1] * (n+1)
    sign_lst[1] = 0
    check_lst = [False for _ in range(n+1)]
    check_lst[0] = True

    makesign(1, rw_lst, sign_lst, check_lst)

    check = True
    for i in range(1, n+1):
        check = check and check_lst[i]

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def check(room_checked):
    for i in room_checked:
        if not i:
            return True
    return False


raw_input = list(map(int, input().strip().split()))
n = raw_input[0]
m = raw_input[1]
# lines = [[False for _ in range(m)] for __ in range(m)]
lines: dict = {i: [] for i in range(m)}
for i in range(m):
    line = list(map(int, input().strip().split()))
    a = line[0] - 1
    b = line[1] - 1
    lines[a].append(b)
    lines[b].append(a)
is_checked_room = [False for _ in range(n)]
sign = [0 for _ in range(n)]
queue = [0]
while check(is_checked_room):
    target = queue[0]
    queue.pop(0)
    is_checked_room[target] = True
    line = lines[target]
    for l in line:
        if not is_checked_room[l]:
            is_checked_room[l] = True
            sign[l] = target
            queue.append(l)
    if not queue:
        print('No')
        break
else:
    print('Yes')
    for i in range(1, n):
        print(sign[i] + 1)

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)]
  next_ = [1]

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

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
def search_min_path(current_point, num_count, ns, ps, pl):
    if ns[current_point] <= num_count + 1:
        return

    if len(pl[current_point]) <= 0:
        return
        
    for next_point in pl[current_point]:
        next_count = ns[next_point] + num_count + 1
        if next_count < ns[current_point]:
            ps[current_point] = next_point
            ns[current_point] = next_count
            #return

        search_min_path(next_point, num_count + 1, ns, ps, pl)


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

ns = [N+1] * N #num to start
ps = [-1] * N  #next path to start
pl = []  #path list

for i in range(N):
    pl.append([])

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

    if A == 0:
        ns[B] = 1
        ps[B] = 0
    elif B == 0:
        ns[A] = 1
        ps[A] = 0

for i in range(1,N):
    search_min_path(i, 0, ns, ps, pl)

ok_flag = True
for i in range(1, N):
    if ps[i] == -1:
        ok_flag = False
        break

if ok_flag:
    print('Yes')
    for i in range(1, N):
        print(ps[i] + 1)

else:
    print('No')

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = []
B = []
for i in range(M):
	A.append(P[i][0])
	B.append(P[i][1])

def find_connect(A,B,C,D,room,number):
    for i in range(N):
        if A[i] == room and C[B[i]-1] == 0:
            C[B[i]-1] = A[i]
            D[B[i]-1] = number
        elif B[i] == room and C[A[i]-1] == 0:
            C[A[i]-1] = B[i]
            D[A[i]-1] = number
    return
  
C = [0]*(N)
C[0] = 1
D = [0]*(N)
D[0] = 1
near = [1]
for i in range(N):
    for j in near:
        find_connect(A,B,C,D,j,i)
#    print(C)
    if all(C[1:]) != 0:
        print("yes")
        for k in range(1,N):
            print(C[k])
        sys.exit()
    near = []

    for k in range(N):
        if D[k] == i:
            near.append(k+1)
print("no")

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n, m = tuple(map(int, input().split()))
    d = {3: 0}
    d.clear()
    d2 = {1: 0}

    for i in range(0, m):
        t1, t2 = tuple(map(int, input().split()))
        if t1 in d.keys():
            d[t1].append(t2)
        else:
            d[t1] = [t2, ]
        if t2 in d.keys():
            d[t2].append(t1)
        else:
            d[t2] = [t1, ]


    def sig(dest, start):
        temp = []
        for i in start:
            if not (i in d2.keys()):
                d2[i] = dest
                temp.append(i)
        for j in temp:
            sig(j, d[j])


    sig(1, d[1])
    if len(d) < n:
        print("No")
    else:
        print("Yes")
        for i in range(2, n + 1):
            print(d2[i])

Submission status: Runtime Error

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

def makesign(room, rw_lst, sign_lst, check_lst):
    check_lst[room] = True
    newways = []
    for way in rw_lst[room]:
        if sign_lst[way] == -1:
            newways.append(way)
            sign_lst[way] = room
    rw_lst[room] = newways

    for way in rw_lst[room]:
        makesign(way, rw_lst, sign_lst, check_lst)

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

    print(rw_lst)

    sign_lst = [-1] * (n+1)
    sign_lst[1] = 0
    check_lst = [False for _ in range(n+1)]
    check_lst[0] = True

    makesign(1, rw_lst, sign_lst, check_lst)

    check = True
    for i in range(1, n+1):
        check = check and check_lst[i]

    if check:
        print("Yes")
        for i in range(2, n+1):
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
L=[set() for i in range(n)]
for i in range(m):
    a, b =  map(int, input().split())
    L[a-1] |= {b}
    L[b-1] |= {a}
Y = {range(1, n+1)}
Z = [0]*(n-1) 
S = {1}
def f(X):
    global S, Z
    X_next = set()
    for j in X:
        R = L[j-1]-S
        S |= L[j-1]
        X_next |= R
        for k in R:
            Z[k-2] += j
    if X_next == set():
        print("Yes")
        print(Z[i] for i in range(n-1))
    else:
        return  f(X_next)
f({1})

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n, m = tuple(map(int, input().split()))
    d = {3: 0}
    d.clear()
    d2 = {1: 0}

    for i in range(0, m):
        t1, t2 = tuple(map(int, input().split()))
        if t1 in d.keys():
            d[t1].append(t2)
        else:
            d[t1] = [t2, ]
        if t2 in d.keys():
            d[t2].append(t1)
        else:
            d[t2] = [t1, ]


    def sig(dest, start):
        temp = []
        for i in start:
            if not (i in d2.keys()):
                d2[i] = dest
                temp.append(i)
        for j in temp:
            sig(j, d[j])


    sig(1, d[1])
    if len(d) < n:
        print("no")
    else:
        for i in range(2, n + 1):
            print(d2[i])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split( ))
all_ = set([i for i in range(1,N)])
child = [[] for _ in range(N)]
ans = [[] for _ in range(N)]
for _ in range(M):
    ab = list(map(int,input().split( )))
    child[ab[0]-1].append(ab[1]-1)
    child[ab[1]-1].append(ab[0]-1)
child = list(map(set,child))
check = [0]
while len(all_ ) != 0:
    checkk = {-1}
    for c in check:
        a = child[c] & all_
        for b in list(a):
            ans[b] = c
        checkk = checkk | set(a)
        all_ = all_ - child[c]
    check = checkk - {-1}
print('Yes')
for a in anss[1:]:
    print(a + 1)

Submission status: Runtime Error

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

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

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

INF = 10 ** 10

def dijkstra_travel(edges):
    paths = [ None for _ in range(n) ]
    paths[0] = 0

    def travel_adjacent(n):
        adjacent_nodes = list(
            map(
                lambda x: paths[x],
                edges[n],
            )
        )

        next_travel = []

        for i, node in enumerate(adjacent_nodes):
            if node is None:
                paths[edges[n][i]] = n
                next_travel.append(edges[n][i])

        for x in next_travel:
            travel_adjacent(x)

    travel_adjacent(0)

    return paths[1:]

result = dijkstra_travel(edges)

if all(map(lambda x: x is not None, result)):
    print('Yes')

    for x in result:
        print(x + 1)

else:
    print('No')

Submission status: Runtime Error

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

step = {}
route = {}

for i in range(M):
    A, B = [int(x) for x in input().split()]

    # if A == 1:
    #     step[B] = 1
    # elif B == 1:
    #     step[A] = 1

    #step[B] = -1
    if A in route:
        route[A].append(B)
        #step[A] = -1
    else:
        route[A] = [B]    
    # elif step[A] != 1:
    #     route[A] = [B]
    #     #step[A] = -1

    
    if B in route:
        route[B].append(A)
    else:
        route[B] = [A]  
    # elif step[B] != 1:
    #     route[B] = [A]

stepcount = 0
mark = {1: 0}
r = 1

def check(stepcount, r, mark):
    stepcount += 1
    if r in route:
        for nextr in route[r]:
            # print(nextr)
            # print(route[nextr])
            if nextr in step:
                if step[nextr] > stepcount:
                    step[nextr] = stepcount
                    mark[nextr] = r
                else:
                    pass
            else:
                step[nextr] = stepcount
                mark[nextr] = r
                check(stepcount, nextr, mark)

check(0, 1, mark)

# print(step)
# print(route)
# print(mark)

if len(mark) == N:
    print('Yes')
    for i in range(2, N + 1):
        print(mark[i])
else:
    print('No')

Submission status: Runtime Error

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

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:
        if not next_doko(element, imano_room, i):
            next_room.remove(element)
    for next in nextroom:
        kamban_okude(next, 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 True
    else:
        return False

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:
# -*- coding: utf-8 -*-

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

def input_multiple_number_as_list():
    return list(map(int, input().split()))



N,M = input_multiple_number()

ans = [0]*(N)
ans[0] = 1
michi = [[] for i in range(N+1)]
isVisit = [False]*N
isVisit[0] = True

for i in range(M):
	a,b = input_multiple_number()
	michi[a].append(b)
	michi[b].append(a)

def DFS(K):
	for heya in michi[K]:
		if ans[heya-1] == 0:
			ans[heya-1] = K

	for heya in michi[K]:
		if not isVisit[heya-1]:
			isVisit[heya-1] = True
			DFS(heya)

DFS(1)
print("Yes")
for i in ans[1:]:
	print(i)

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 = [-1] * N
A = np.zeros([N,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(N):
            if A[x[i], j] == 1 and S[j] == -1:
                S[j] = x[i]
                y.append(j)
    x = y

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