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())
r={}
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if a not in r: r[a]=[]
  r[a].append(b)
  if b not in r: r[b]=[]
  r[b].append(a)

ans = {0:0}
steps = [-1]*n
steps[0]=0
def setroot(i,step):
  newroom = [v for v in r[i] if steps[v]<0 or steps[v]>step]
  #print(i,newroom)
  if len(newroom)>0:
    for v in newroom:ans[v]=i;steps[v]=step
    for v in newroom:setroot(v,step+1)
setroot(0,0)
#print(r)
#print(steps)
if len(ans) == n:
  print('Yes')
  for i in range(1,n):
    if i in ans:
      print(ans[i]+1)
else:
  print('No')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = []
d1 = {}
d2 = {}
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        d1[b] = 1
        d2[b] = 1
    elif b == 1:
        d1[a] = 1
        d2[a] = 1
    else:
        p.append(tuple([b, a]))
for i in range(len(p)):
    if p[i][0] in d1 and p[i][1] not in d1:
        d1[p[i][1]] = p[i][0]
        d2[p[i][1]] = d2[p[i][0]] + 1
    elif p[i][1] in d1 and p[i][0] not in d1:
        d1[p[i][0]] = p[i][1]
        d2[p[i][0]] = d2[p[i][1]] + 1
    elif p[i][0] in d1 and p[i][1] in d1:
        if d2[p[i][0]] > d2[p[i][1]] + 1:
            d1[p[i][0]] = p[i][1]
            d2[p[i][0]] = d2[p[i][1]] + 1
        elif d2[p[i][1]] > d2[p[i][0]] + 1:
            d1[p[i][1]] = p[i][0]
            d2[p[i][1]] = d2[p[i][0]] + 1
print("Yes")
for i in range(2, n + 1):
    print(d1[i])

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)
        else:
            continue


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())
r={}
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if a not in r: r[a]=[]
  r[a].append(b)
  if b not in r: r[b]=[]
  r[b].append(a)

ans = {0:0}
steps = [-1]*n
steps[0]=0
def setroot(i,step):
  newroom = [v for v in r[i] if steps[v]<0 or steps[v]>step]
  #print(i,newroom)
  if len(newroom)>0:
    for v in newroom:ans[v]=i;steps[v]=step
    for v in newroom:setroot(v,step+1)
setroot(0,0)
#print(r)
#print(steps)
if len(ans) == n:
  print('Yes')
  for i in range(1,n):
    if i in ans:
      print(ans[i]+1)
else:
  print('No')
    
mod = 1000000007

n = int(input())
fishes = {}
for _ in range(n):
  a,b=map(int,input().split())
  if b == 0: r = 10**10
  else:
    r = round(a/b,10)
  if r not in fishes:fishes[r]=0
  fishes[r]+=1
for 
  if

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)

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

Submission status: Runtime Error

Solution code:
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')
  if mitisurube.count(-1) < 3:
    print('Yes')
    print(*mitisurube[2:], sep='\n')
  else:
    print('No')

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import math

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]

hist= []
visited_pos = [-1] * n

#初期情報
#print(ab)
ts = {}
for el in ab:
  wk = ts.get(el[0]) 
  if wk is None:
    sss  = set()
    ts[el[0]] = sss
  ts[el[0]].add(el[1])
  wk = ts.get(el[1]) 
  if wk is None:
    sss  = set()
    ts[el[1]] = sss
  ts[el[1]].add(el[0])
#print(ts)


#幅優先探索
def tsk(pos):
  wk = ts.get(pos)
  if ts.get(pos) is None:
    return
  else:
    #print(pos,wk)
    for e in wk:
      if visited_pos[e-1] < 0:
        visited_pos[e-1] = pos
        hist.append(e-1)

idx = 1
hist.append(1)
while True:
  if idx > len(hist):
    break
  else:
    tsk(hist[idx])
    idx += 1
#print(hist)
#print(visited_pos)
ans = 'Yes'
for i in range(n):
  if visited_pos[i] == -1:
    ans = 'No'
    break

print(ans)
if ans == 'Yes':
  for i in range(1,n):
    print(visited_pos[i])

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)

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

Submission status: Runtime Error

Solution code:
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 sign(dest, start):
        for i in start:
            temp = []
            if not (i in d2.keys()):
                d2[i] = dest
                temp.append(i)
        for i in temp:
          sign(i, d[i])


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

Submission status: Runtime Error

Solution code:
def cape(iri):
    ima = set()
    for i in iri:
        for j in root[i]:
            if ans[j] == 0:
                ans[j] = i
                root[j] -= iri #ここが重そう
                ima.add(j) #ここも重そう
    if len(ima) > 0:
        cape(ima)

N, M = map(int, input().split())
root = [set() for i in range(N + 1)]
ans = [0 for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    root[a].add(b)
    root[b].add(a)
cape({1})
print("Yes")
for i in range(2, N + 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

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


n, m = [int(i) for i in input().split()]
V_ds = [None, 0] + [10**10] * (n-1)
V_prevs = [None] * (n+1)
class V:
    def __init__(self, idx):
        self.idx = idx
        # self.d = 10**10 if idx != 1 else 0
        # self.prev = None

    def __lt__(self, other):
        return V_ds[self.idx] < V_ds[other.idx]
    
    def __eq__(self, other):
        return self.idx == other.idx

raw_edges = [[int(i) for i in input().split()] for i in range(m)]
edges = {i: [] for i in range(1, n+1)}
for i, j in raw_edges:
    edges[i].append(j)
    edges[j].append(i)

Q = PriorityQueue()

for i in range(1, n+1):
    Q.push(V(i))
while len(Q):
    
    u = Q.pop()

    for d in edges[u.idx]:
        if V_ds[d] > V_ds[u.idx] + 1:
            V_ds[d] = V_ds[u.idx]+ 1
            V_prevs[d] = u.idx
            Q.heap.remove(V(d))
            Q.push(V(d))

ans = V_prevs[2:]
if None in ans:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Runtime Error

Solution code:
from sys import stdin
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a,b = map(int,stdin.readline().split())
    ab.append([a,b])
whole = [1]
check = whole
ans = [0 for i in range(n)]
while len(whole) < n:
    part = []
    dellist = []
    for i in check:
        for j in range(len(ab)):
            c = 0
            k = ab[j]
            if k[0] == i:
                if (k[1] not in whole) and (k[1] not in part):
                    part.append(k[1])
                    ans[k[1]-1] = i
                    c += 1
            if k[1] == i:
                if (k[0] not in whole) and (k[0] not in part):
                    part.append(k[0])
                    ans[k[0]-1] = i
                    c += 1
            if c > 0:
                dellist.append(j)
    check = part[:]
    for i in part:
        whole.append(i)
    for i in dellist:
        del ab[i]
print("yes")
for i in range(1,n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
r={}
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if a not in r: r[a]=[]
  r[a].append(b)
  if b not in r: r[b]=[]
  r[b].append(a)

ans = {0:0}
steps = [-1]*n
steps[0]=0
def setroot(i,step):
  newroom = [v for v in r[i] if steps[v]<0 or steps[v]>step]
  #print(i,newroom)
  if len(newroom)>0:
    for v in newroom:ans[v]=i;steps[v]=step
    for v in newroom:setroot(v,step+1)
setroot(0,0)
#print(r)
#print(steps)
if len(ans) == n:
  print('Yes')
  for i in range(1,n):
    print(ans[i]+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
    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:
from collections import deque

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = [[-1] * n for i in range(n)]
lead = [0] * n
i_n = [0] * n
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    c[b[i]][i_n[b[i]]] = a[i]
    c[a[i]][i_n[a[i]]] = b[i]
    i_n[b[i]] += 1
    i_n[a[i]] += 1

d = deque()
d.append(0)

while len(d):
    k = len(d)
    for i in range(k):
        p = d[0]
        for j in range(n):
            if c[p][j] == -1:
                break
            if lead[c[p][j]] == 0:
                lead[c[p][j]] = p + 1
                d.append(c[p][j])
        d.popleft()

print('Yes')
for i in range(n - 1):
    print(lead[i + 1])

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()
    if visited[tmp] != 1 :
        visited[tmp] = 1
        for node in adj[tmp]:
            if visited[node] !=1:
                d.append(node)
                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
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)

if count >= N-1:
	print("Yes")
	for i in ans[1:]:
		print(i[1])
else:
	print("No")

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.eye(N)
for i in range(M):
    A[K[i][0]-1,K[i][1]-1] = 1
    A[K[i][1]-1,K[i][0]-1] = 1

x = [0]
while len(x) != 0:
    y = []
    for i in range(len(x)):
        for j in range(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 = map(int, input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
ans=[[] for i in range(M-1)]
ans2={}
for i in range(M):
    A[i],B[i] = map(int, input().split())
for i in range(M):
    if A[i]==1 and B[i] not in ans2:
        ans2[B[i]]=1
        ans[1-1].append(B[i])
    elif B[i]==1 and A[i] not in ans2:
        ans2[A[i]]=1
        ans[1-1].append(A[i])
for z in range(M-1):
    for i in range(M):
        for j in range(len(ans[z])):
            if A[i]==ans[z][j] and B[i] not in ans2:
                ans2[B[i]]=ans[z][j]
                ans[z+2-1].append(B[i])
            elif B[i]==ans[z][j] and A[i] not in ans2:
                ans2[A[i]]=ans[z][j]
                ans[z+2-1].append(A[i])
ans3="No"
for i in range(1,N+1):
    if not i in ans2:
        break
    elif i==N:
        ans3="Yes"
print(ans3)
if ans3=="Yes":
    for i in range(2,N+1):
        print(ans2[i])

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys


def loop(num, cnt):
    if num == N:
        # print(path)
        for i in range(1, len(path)):
            if ans[path[i]][0] > i:
                ans[path[i]][0] = i
                ans[path[i]][1] = path[i-1]
        return
    else:
        if temp[num-1] in path:
            # print(path)
            for i in range(1, len(path)):
                if ans[path[i]][0] > i:
                    ans[path[i]][0] = i
                    ans[path[i]][1] = path[i-1]
            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 = [[10**9, 0] for x in range(N+1)]
# print(ans)
cnt = 0
path = [1]
# print(k)
loop(1, cnt)
# print(temp)

# print(ans)
print('Yes')
for i in range(2, N+1):
    print(ans[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)]

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:
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():
    if len(list(d)) != 0:
        tmp = d.pop()
        if visited[tmp] != 1 :
            visited[tmp] = 1
            for node in adj[tmp]:
                if visited[node] !=1:
                    d.append(node)
                    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:
nm = [int(x) for x in input().split()]

n = nm[0]
m = nm[1]

listt = {}

data = {}
cleared = 0

for i in range(0,m):
    
    x = [int(x) for x in input().split()]

    if x[0] in listt:
        listt[x[0]].append(x[1])
    else:
        listt[x[0]] = [x[1]]

    if x[1] in listt:
        listt[x[1]].append(x[0])
    else:
        listt[x[1]] = [x[0]]

def do(x):
    global cleared
    for e in listt[x]:
        if e not in data:
            cleared = cleared + 1
            if x == 1:
                data[e] = [x,1]
            else:
                data[e] = [x,data[x][1]+1]
            do(e)
        else:
            if data[x][1]+1 < data[e][1]:
                data[e] = [x,data[x][1]+1]

do(1)


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

Submission status: Runtime Error

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

  root = [[] for i in range(M+1)]
  for i in range(M):
    A, B = list(map(int, input().split(' ')))
    root[A].append(B)
    root[B].append(A)

  mitisurube = [-1 for i in range(N+1)]
  cost = [True for i in range(N+1)]
  next_ = [1]
  cost[1] = False

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

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edge = [[] for i in range(n+1)]
reached = [0 for _ in range(n+1)]
guide = [0 for i in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

print("Yes")
queue = [(e, 1) for e in edge[1]]
counter = 0
while counter < n:
    # print(queue)
    e, now = queue.pop(0)
    if reached[e] == 0:
        counter += 1
        reached[e] = 1
        guide[e] = now
        # edge[e].remove(now)
        for next in edge[e]:
            if next != 1 and reached[next] == 0:
                queue.append((next, e))

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

Submission status: Runtime Error

Solution code:
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() )
#    print( a[ i ], b[ i ] )


def search( x ):
    for ai, bi in zip( a, b ):
        if ai == x and l[ bi-1 ] > l[ ai-1 ]:
            l[ bi-1 ] = l[ ai-1 ] + 1
            s[ bi-1 ] = ai
            search( bi )
        elif bi == x and l[ ai-1 ] > l[ bi-1 ]:
            l[ ai-1 ] = l[ bi-1 ] + 1
            s[ ai-1 ] = bi
            search( ai )



l = [ 10000000000 ] * n
l[ 0 ] = 0
s = [ 0 ] * n
search( 1 )

print( "Yes" )
for i in range( n-1 ):
#    print( l[ i ], s[ i ] )
    print( s[ i+1 ] )

Submission status: Runtime Error

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

dic = {i:set() for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    dic[a].add(b)
    dic[b].add(a)


l1 = [float('inf')]*N
l1[0] = 0
ans = [0] * N
x = {1}

k1 = 1
rooms = dic[k1]

def search(k1, dic, l1, ans, x):

    if x == {i for i in range(1, N)}:
        return

    rooms = dic[k1]
    for room in rooms:
        x.add(room)
        
        if l1[k1-1] + 1 < l1[room-1]:
            l1[room-1] = l1[k1-1] + 1
            ans[room-1] = k1
            search(room, dic, l1, ans, x)



search(k1, dic, l1, ans, x)

if float('inf') in l1:
    print('No')
else:
    print('Yes')
    for n in ans[1:]:
        print(n)

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 = [[0 for _ in range(m)] for __ 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][b] = 1
    lines[b][a] = 1
is_checked_all_room = [False for _ in range(n)]
sign = [0 for _ in range(n)]
queue = [0]
while check(is_checked_all_room):
    target = queue[0]
    queue.pop(0)
    is_checked_all_room[target] = True
    line = lines[target]
    for i, l in enumerate(line):
        if l:
            if not is_checked_all_room[i]:
                is_checked_all_room[i] = True
                sign[i] = target
                queue.append(i)
    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:
#1<=A     A sench (hour)
#B<=1000  B sench (min)
#0<=H<=11 hour
#0<=M<59  minute

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

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

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

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

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

  
Rl[0].first = 0

ma = [0]*N

def dijkstra(s):
  
  if(ma[s-1]==1):
    return
  ma[s-1]+=1
  
  if(Rl[s-1].num == 1):
    Rl[s-1].first = 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)
  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(2,N+1):
    print(Rl[i-1].first)

Submission status: Runtime Error

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

dic = {i:set() for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    dic[a].add(b)
    dic[b].add(a)


l1 = [float('inf')]*N
l1[0] = 0
ans = [0] * N
x = {1}

k1 = 1
rooms = dic[k1]

def search(k1, dic, l1, ans, x):

    if x == {i for i in range(1, N)}:
        return

    rooms = dic[k1]
    for room in rooms:
        x.add(room)
        print(room)
        if l1[k1-1] + 1 < l1[room-1]:
            l1[room-1] = l1[k1-1] + 1
            ans[room-1] = k1
            search(room, dic, l1, ans, x)



search(k1, dic, l1, ans, x)

if float('inf') in l1:
    print('No')
else:
    print('Yes')
    for n in ans[1:]:
        print(n)

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    
dist = [-1] * N
dist[0] = 0
    
queue = deque([0])

while queue:
    v = queue.popleft()
    for nv in graph[v]:
        if (dist[nv] != -1):
            continue
        dist[nv] = v
        queue.append(nv)

print("Yes")
for i in dist[1:]:
    print(i+1)

Submission status: Runtime Error

Solution code:
from collections import deque


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

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

ab_count = {key:[] for key in range(1,n+1)}

for i in range(m):
    ab_count[ab_list[i][0]].append(ab_list[i][1])
    ab_count[ab_list[i][1]].append(ab_list[i][0])

for i in range(m):
    if len(ab_count[i]) == 0:
        print("No")
        exit()

#print(ab_count)

que = deque()

#始点は1、階層は0からスタート
que.append([1,0])

checked_dict = {key:[] for key in range(1,n+1)}
temp_dict = {key:[] for key in range(1,n+1)}
where = 0

while que:
    x_pop = que.popleft()
    x = x_pop[0]
    if where != x_pop[1]:
        #階層が代わったから、temp_dictをchecked_dictへ反映させる処理
        for k in range(1,n+1):
            if len(checked_dict[k]) == 0:
                checked_dict[k] = temp_dict[k]
            else:
                aaa = set(checked_dict[k]) & set(temp_dict[k])
                if aaa != set():
                    checked_dict[k] = list(aaa)

    where = x_pop[1]

    for j in ab_count[x]:
        if len(checked_dict[j]) == 0:
            #OK,temp_dictに入れて、queに入れる。
            temp_dict[j].append(x)
            que.append([j,where+1])
        else:
            continue

    

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

Submission status: Runtime Error

Solution code:
import sys 
from collections import defaultdict 
 
class Graph: 
 
    def __init__(self): 
        global n
        self.graph = defaultdict(list) 
        self.parent = [None for i in range(0,n) ]
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
    def BFS(self, s): 
        visited = [False] * (len(self.graph)) 
  
        queue = [] 
        queue.append(s) 
        visited[s] = True
  
        while queue: 
            s = queue.pop(0) 
            # print (s, end = " ") 
            for i in self.graph[s]: 
                
                if visited[i] == False: 
                    self.parent[i]=s+1
                    queue.append(i) 
                    visited[i] = True


[n,m]=[int(i) for i in input().split(' ')]
g = Graph() 
for i in range(0,m):
    [a,b]=[int(i)-1 for i in input().split(' ')]
    g.addEdge(a,b)
g.BFS(0)
flag=0
for i in range(1,n):
    if g.parent[i]==None:
        print('NO')
        flag=1
        break
if flag==0:
    print('YES')
    for i in range(1,n):
        print(g.parent[i])
        # 7