Problem:


Score: 400 points

Problem Statement

There is a cave.

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

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

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

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

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

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

One can travel between any two rooms by traversing passages.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

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

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

Sample Input 1

4 4
1 2
2 3
3 4
4 2

Sample Output 1

Yes
1
2
2

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

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

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

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

Thus, the objective is satisfied.

Sample Input 2

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

Sample Output 2

Yes
6
5
5
1
1

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



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


Sample output:
Yes
1
2
2

Submission status: Runtime Error

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

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

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

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

from collections import deque
queue = deque()

def bfs():
    queue.append(0)
    while len(queue) > 0:

        #if all(visited):
            #break
        now = queue.popleft()

        for c in nei_L[now]:

            if not visited[c]:
                ans[c] = now
                queue.append(c)
                visited[c] = 1

bfs()

#if -1 in visited[1:]:
#    print("No")
#else:
for i in range(N):
    if i == 0:
        print("Yes")
    else:
        print(ans[i] + 1)

Submission status: Runtime Error

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

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

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

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

from collections import deque
queue = deque()

def bfs():
    queue.append(0)
    while len(queue) > 0:

        #if all(visited):
            #break
        now = queue.popleft()

        for c in nei_L[now]:

            if not visited[c]:
                ans[c] = now
                queue.append(c)
                visited[c] = 1

bfs()

if -1 in visited[1:]:
    print("No")
else:
    for i in range(N):
        if i == 0:
            print("Yes")
        else:
            print(ans[i] + 1)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = map(int,input().split())

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

    net[a].append(b)
    net[b].append(a)

a = [-1] * (n+1)
d = deque()
d.append(1)
while d:
    u = d.popleft()
    for child in net[u]:
        if a[child] != -1:continue
        a[child] = u
        d.append(child)
print("Yes")
print(*a[2:], seq = " ")

Submission status: Runtime Error

Solution code:
from collections import deque

n, m = map(int, input().split()) #ノード数, エッジ数
x = [] #エッジ
y = {i + 1 for i in range(n)} #未探索ノード
z = deque([1]) #探索用キュー
ans = []

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

while y != set():
    s = set()
    t = z.popleft()
    for u in x:
        if t in u:
            s.add((u - t).pop())
    for v in s & y:
        ans[v - 1] = t
        z.append(v)
    y.remove(t)

print('Yes')
for w in ans[1:]:
    print(w)

Submission status: Runtime Error

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

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

stack=[0]
check = [-1]*n
check[0] = 0

while len(stack)>0:
    v = stack.popleft()
    for i in root[v]:
        if check[i] == -1:
            check[i]=v+1
            stack.append(i)


print('Yes')
for i in range(1,n):
    print(check[i])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
tr = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    tr[a-1].append(b)
    tr[b-1].append(a)
if not tr[0]:
    print('No')
else:
    mark = [10**7]*n
    mark[0] = -1
    cnt = 0
    i=0
    from collections import deque
    que = deque()
    def mk(mark,que,cnt):
        i = que.popleft()-1
        for j in range(len(tr[i])):
            if tr[i][j]!=1:
                mark[tr[i][j]-1] = min(i+1,mark[tr[i][j]-1])
                cnt+=1
                que.append(tr[i][j])
                if cnt == n:
                    return mark
            else:
                continue
        else:
            mark = mk(mark,que,cnt)
            return mark
    que.append(1)
    mark=mk(mark,que,cnt)
    if 10**7 in mark:
        print('No')
    else:
        print('Yes')
        for i in range(1,n):
            print(mark[i])

Submission status: Runtime Error

Solution code:
from collections import deque
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)
task = deque([1])
itta = {1}
while len(task) > 0:
    now = task.pop()
    additional = root[now] - itta
    for i in additional:
        ans[i] = now
        itta.add(i)
    task.append(list(additional))
print("Yes")
for i in range(2, N + 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import queue

n,m = list(map(int, input().split()))
puted = [0]*(n+1)

ab = [[] for i in range(n+1)]
for i in range(m):
	a,b = readInts()
	ab[a].append(b)
	ab[b].append(a)

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while -1 in flg or q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Submission status: Runtime Error

Solution code:
import networkx as nx
import collections

def bfs(G):
    V = [ v for v in G.nodes() ]
    Q = collections.deque([V[0]])
    searched = { v: False for v in G.nodes() }
    searched[V[0]] = True
    n=1
    H={v:None for v in G.nodes()}

    while len(Q) != 0:
        v = Q.popleft()
        edges = [ (v, i ) for (v, i) in G.edges(v) if not searched[i] ]
        for edge in edges:
            v, i = edge
            Q.append(i)
            searched[i] = True

            if H[i]==None:
                H[i]=v
                n+=1
                
    return (H,n)

G=nx.Graph()
N,M=map(int,input().split())
G.add_nodes_from(range(1,N+1))

for i in range(M):
    v,w=map(int,input().split())
    G.add_edge(v,w)

(H,n)=bfs(G)
if n!=N:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(H[i])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split()) #n:頂点数　w:辺の数


way = [[] for i in range(M)]
depth = [float("inf") for i in range(N)]
visited = [False for i in range(N)]
que=[0]

for i in range(M):
    x,y = map(int,input().split())
    way[x-1].append(y-1)
    way[y-1].append(x-1)

for i in que:
  for j in way[i]:
    if visited[j]:
      continue
    que.append(j)
    visited[j]=True
    depth[j] = min(i+1,depth[j])
print("Yes")
for i in range(1,N):
  print(depth[i])

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
d = {1: []}
ans = [None] * (n)
ans[0] = 0
data = {0: [1]}
for i, j in ab:
    if i == 1:
        d[1].append(j)
    elif j == 1:
        d[1].append(i)
    else:
        if i in d:
            if 1 not in d[i]:
                d[i].append(j)
        else:
            d[i] = [j]
        if j in d:
            if 1 not in d[j]:
                d[j].append(i)
        else:
            d[j] = [i]         
i = 0
while None in ans:
    data[i + 1] = []
    for j in data[i]:
        for k in d[j]:
            if ans[k - 1] is None:
                ans[k - 1] = j
            data[i + 1].append(k)
    data[i + 1] = set(data[i+ 1])
    i += 1
print("Yes")
for i in range(1, n):
    print(ans[i])

Submission status: Runtime Error

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

def main():
  N, M = map(int, readline().split())
  dist = {}
  pre = {}
  A = {}
  for i in range(N):
    dist[i+1] = -1
    pre[i+1] = -1
    A[i+1] = []
  dist[1] = 0
  pre[1] = 0
  for i in range(M):
    ai, bi = map(int, readline().split())
      A[ai].append(bi)
      A[bi].append(ai)
  cnt = 1
  depth = 1
  D = [1]
  while cnt < N:
    next = []
    for i in range(len(D)):
      for j in range(len(A[D[i]])):
        if dist[A[D[i]][j]] == -1:
          dist[A[D[i]][j]] = depth
          pre[A[D[i]][j]] = D[i]
          next.append(A[D[i]][j])
          cnt += 1
    D = next
    depth += 1
    if len(next) == 0:
      break
    elif depth > N:
      break
  if cnt == N:
    print('Yes')
    for i in range(1, N):
      print(pre[i+1])
  else:
    print('No')

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
class Room:
  def __init__(self):
    self.routes = []
    self.depth = -1

  def checkRoutes(self,depth):
    self.depth=depth
    for route in self.routes:
      room = rooms[route]
      if room.depth==-1 or (room.depth > depth):
        room.checkRoutes(self.depth+1)
        
  
numRooms,numRoutes= map(int,input().split())

rooms = []*(numRooms+1)
for i in range(numRooms+1):
  rooms.append(Room())

for i in range(numRoutes):
  room1,room2=list(map(int,input().split()))
  rooms[room1].routes.append(room2)
  rooms[room2].routes.append(room1)

rooms[1].checkRoutes(0)

print('Yes')
for i in range(2,numRooms+1):
  print(rooms[i].depth)

Submission status: Runtime Error

Solution code:
def resolve():
    N, M = [int(i) for i in input().split()]
    path = [[] for _ in range(N)]
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        path[A - 1].append(B - 1)
        path[B - 1].append(A - 1)
    visited = [-1] * N
    que = [0]
    visited[0] = 0

    while que:
        v = que.pop(0)
        print(v, path[v], file=sys.stderr)
        for nv in path[v]:
            if visited[nv] != -1:
                continue
            print(nv, visited[v] + 1, file=sys.stderr)
            visited[nv] = v + 1
            que.append(nv)

    if -1 in visited:
        print("No")
    else:
        print("Yes")
        for i in range(N - 1):
            print(visited[i + 1])


resolve()

Submission status: Runtime Error

Solution code:
from collections import deque

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)

todo=deque([0,0])
seen=[-1]*n
seen[0]=0

while todo:
    node,parent=todo.popleft()#現在探索している部屋、その親
    
    for to in edges[node]:
        if seen[to]!=-1:
            continue

        todo.append([to,node])
        seen[to]=node

print('Yes')

for parent in seen[1:]:
    print(parent+1)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
d = {1: []}
data = {1: 0}
ind = [1]
for i, j in ab:
    if i == 1:
        d[1].append(j)
    elif j == 1:
        d[1].append(i)
    else:
        if i in d:
            if 1 not in d[i]:
                d[i].append(j)
        else:
            d[i] = [j]
        if j in d:
            if 1 not in d[j]:
                d[j].append(i)
        else:
            d[j] = [i]   
while len(data) != n:
    for i in ind:
        l = d[i]
        for j in l:
            if j not in data:
                data[j] = i
    ind = l
print("Yes")
for i in range(2, n + 1):
    print(data[i])

Submission status: Runtime Error

Solution code:
from collections import deque

n,m = list(map(int,input().split()))
e = [[] for _ in range(m+1)]

for i in range(m):
    a,b = list(map(int,input().split()))
    e[a].append(b)
    e[b].append(a)
q = deque()
q.append(1)
t = [-1 for _ in range(n+1)]

while len(q):
    node = q.popleft()

    for i in range(len(e[node])):
        nex = e[node][i]
        if t[nex] == -1:
            q.append(nex)
            t[nex] = node
print("Yes")
for i in range(2,n+1):
    print(t[i])

Submission status: Runtime Error

Solution code:
class Room:
  def __init__(self):
    self.routes = []
    self.depth = -1

  def checkRoutes(self,depth):
    self.depth=depth
    for route in self.routes:
      room = rooms[route]
      if room.depth==-1 or (room.depth > depth+1):
        room.checkRoutes(self.depth+1)
        
  
numRooms,numRoutes= list(map(int,input().split()))

rooms = []*(numRooms+1)
for i in range(numRooms+1):
  rooms.append(Room())

for i in range(numRoutes):
  room1,room2=list(map(int,input().split()))
  rooms[room1].routes.append(room2)
  rooms[room2].routes.append(room1)

rooms[1].checkRoutes(0)

print('Yes')
for i in range(2,numRooms+1):
  print(rooms[i].depth)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = list(map(int,input().split()))
e = [[] for _ in range(m+1)]
for i in range(m):
    a,b = list(map(int,input().split()))
    e[a].append(b)
    e[b].append(a)
q = deque()
q.append(1)
s = [float('inf') for _ in range(n+1)]
t = [-1 for _ in range(n+1)]
s[1] = 0
# print(e)
while len(q):
    node = q.popleft()

    for i in range(len(e[node])):
        nex = e[node][i]
        if t[nex] == -1:
            # print(nex,node)
            q.append(nex)
            t[nex] = node
# print(s,t,e)
print("Yes")
for i in range(2,n+1):
    print(t[i])

Submission status: Runtime Error

Solution code:
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, [e[0]+d[v], e[1]])
    return d


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

edge = [[] for i in range(w)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append([1, y])
    edge[y].append([1, x])
d = dijkstra_heap(0)

if float('inf') in d:
    print('No')
else:
    print('Yes')
    for i, j in enumerate(d):
        if i == 0:
            continue
        print(j)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = list(map(int,input().split()))
e = [[] for _ in range(m+1)]
for i in range(m):
    a,b = list(map(int,input().split()))
    e[a].append(b)
    e[b].append(a)
q = deque()
q.append(1)
s = [float('inf') for _ in range(n+1)]
t = [-1 for _ in range(n+1)]
s[1] = 0
while len(q):
    node = q.pop()
    step = s[node]+1
    for i in range(len(e[node])):
        nex = e[node][i]
        if s[nex] > step:
            q.append(nex)
            s[nex] = step
            t[nex] = node
# print(s,t,e)
print("Yes")
for i in range(2,n+1):
    print(t[i])

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = list(map(int,input().split()))
e = [[] for _ in range(m+1)]
for i in range(m):
    a,b = list(map(int,input().split()))
    e[a].append(b)
    e[b].append(a)

q = deque()
q.append(1)

s = [float('inf') for _ in range(n+1)]
t = [-1 for _ in range(n+1)]
s[1] = 0
while len(q):
    node = q.pop()
    step = s[node]+1
    for i in range(len(e[node])):
        nex = e[node][i]
        if s[nex] > step:
            q.append(nex)
            s[nex] = step
            t[nex] = node
# print(s,t,e)
print("Yes")
for i in range(2,n+1):
    print(t[i])

Submission status: Runtime Error

Solution code:
import numpy as np
room, route_count = map(int,input().split())
route = np.array([list(map(int,input().split())) for _ in range(route_count)])
 
object_nums = [1]
ans = np.array([0]*(room-1))
 
def mem_ans(ans, object_num, next_nums):
    mask_array = np.zeros(room-1, dtype=bool)
    mask_array[next_nums-2] = True
    ans[ans=0 & mask_array] = object_num
    return ans
 
for object_num in object_nums:
 
    object_rows = route[np.any(route==object_num, axis=1)]
    route[np.any(route==object_num, axis=1)] = 0
    next_nums = object_rows[object_rows!=object_num]
    if next_nums is not None:
        ans = mem_ans(ans, object_num, next_nums)
        object_nums.extend(next_nums)
    else:
        break
 
if 0 in set(ans):
  print('No')
else:
  print('Yes')
  for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
from collections import deque 
n,m = list(map(int,input().split()))
e = [[] for _ in range(m+1)]
for i in range(m):
    a,b = list(map(int,input().split()))
    e[a].append(b)
    e[b].append(a)

q = deque()
q.append(1)

s = [-1 for _ in range(n+1)]
s[1] = 0
while len(q):
    node = q.pop()
    for i in range(len(e[node])):
        nex = e[node][i]
        if s[nex] == -1:
            q.append(nex)
            s[nex] = node
# print(s,t,e)
print("Yes")
for i in range(2,n+1):
    print(s[i])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
AB = [[] for _ in range(M)]
ans = [0]*N
for _ in range(M):
  a,b = map(int,input().split())
  AB[a-1].append(b-1)
  AB[b-1].append(a-1)

from collections import deque

node = 0
q = deque([0])

check = [0]*N
check[0] = 1
while len(q) > 0:
  node = q.popleft()
  for i in AB[node]:
    if check[i] == 0:
      q.append(i)
      check[i] = 1
      ans[i] = node
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

Submission status: Runtime Error

Solution code:
from collections import deque 
n,m = list(map(int,input().split()))
e = [[] for _ in range(m+1)]
for i in range(m):
    a,b = list(map(int,input().split()))
    e[a].append(b)
    e[b].append(a)

q = deque()
q.append(1)

s = [[(10**5+1) for _ in range(2)] for _ in range(n+1)]
s[1][0] = 0
while len(q):
    node = q.pop()
    step = s[node][0]
    for i in range(len(e[node])):
        nex = e[node][i]

        if s[nex][0] > step +1:
            q.append(nex)
            s[nex][0] = step + 1
            s[nex][1] = node
# print(s,t,e)
print("Yes")
for i in range(2,n+1):
    print(s[i][1])

Submission status: Runtime Error

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

import sys
from collections import defaultdict
from math import gcd
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def formatting(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g

    if a < 0:
        return (-a, -b)

    return a, b


MOD = pow(10, 9) + 7

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

zz = 0
odd = defaultdict(int)
even = defaultdict(int)

for a, b in zip(A, B):
    if a == b == 0:
        zz += 1
        continue
    a, b = formatting(a, b)
    if b <= 0:
        odd[(a, b)] += 1
    else:
        even[(b, -a)] += 1
        odd[(b, -a)] += 0

ans = zz
k = 1

for key, cnt0 in odd.items():
    cnt1 = even[key]
    acc = pow(2, cnt0, MOD) + pow(2, cnt1, MOD)
    k = k * (acc - 1) % MOD

ans += k - 1
print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(2000000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

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

Submission status: Runtime Error

Solution code:
def resolve():
  N, M = map(int, input().split(" "))
  AB_map = [[] for i in range(N)]
  for m in range(M):
    AB = [int(x) - 1 for x in input().split(" ")]
    AB_map[AB[0]].append(AB[1])
    AB_map[AB[1]].append(AB[0])

  not_finished = set(range(1, N+1))
  rooms = [None] * N
  rooms[0] = 0
  room_depths = [0] * N

  def search_and_mark(recent_rooms, depth):
    if len(not_finished) == 0 or len(recent_rooms) == 0 or depth >= N:
      return True

    temp_recent = set()
    for r in recent_rooms:
      for target in AB_map[r]:
        if target in not_finished:
          temp_recent.add(target)
          not_finished.remove(target)
          rooms[target] = r
          room_depths[target] = depth

    return search_and_mark(list(temp_recent), depth+1)

  _ = search_and_mark([0], 0)

  print("Yes")
  for r in rooms[1:]:
    print(r + 1)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
  N, M = map(int, input().split(" "))
  AB_map = [[] for i in range(N)]
  for m in range(M):
    AB = [int(x) - 1 for x in input().split(" ")]
    AB_map[AB[0]].append(AB[1])
    AB_map[AB[1]].append(AB[0])

  not_finished = set(range(1, N+1))
  rooms = [None] * N
  rooms[0] = 0
  room_depths = [0] * N

  def search_and_mark(recent_rooms, depth):
    if len(not_finished) or len(recent_rooms) == 0 or depth >= N:
      return True

    temp_recent = set()
    for r in recent_rooms:
      for target in AB_map[r]:
        if target in not_finished:
          temp_recent.add(target)
          not_finished.remove(target)
          rooms[target] = r
          room_depths[target] = depth

    return search_and_mark(list(temp_recent), depth+1)

  _ = search_and_mark([0], 0)

  print("Yes")
  for r in rooms[1:]:
    print(r + 1)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(20000000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)

Submission status: Runtime Error

Solution code:
print("Yes")
N, M = map(int, input().split())
path = [[] for _ in range(N)]
ind = [0 for _ in range(N)]
lis = []
for o in range(N):
    lis.append(o)
for i in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B-1)
    path[B-1].append(A-1)
que = path[0]
for p in que:
    lis.discard(p)
for l in que:
    U = path[l]
    for m in U:
        if m in lis:
            ind[m] = l
            lis.discard(m)
    que += U
    if lis == {}:
        break
for z in range(1,N):
    ind[z] += 1
    print(ind[z])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
maze = [list(map(int, input().split())) for i in range(M)] #洞窟のマップ
queue = [1] #キュー
dist = [-1] * N #distant 深さ
count = 0

for i in range(M):
  for j in range(2):
    if

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(2000000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)

Submission status: Runtime Error

Solution code:
def resolve():
  N, M = map(int, input().split(" "))
  AB_map = [[] for i in range(N)]
  for m in range(M):
    AB = [int(x) - 1 for x in input().split(" ")]
    AB_map[AB[0]].append(AB[1])
    AB_map[AB[1]].append(AB[0])

  not_finished = set(range(1, N+1))
  rooms = [None] * N
  rooms[0] = 0
  room_depths = [0] * N

  def search_and_mark(recent_rooms, depth):
    if len(recent_rooms) == 0 or depth >= N:
      return True

    temp_recent = set()
    for r in recent_rooms:
      for target in AB_map[r]:
        if target in not_finished:
          temp_recent.add(target)
          not_finished.remove(target)
          rooms[target] = r
          room_depths[target] = depth

    return search_and_mark(list(temp_recent), depth+1)

  _ = search_and_mark([0], 0)

  print("Yes")
  for r in rooms[1:]:
    print(r + 1)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from collections import deque 
n,m = list(map(int,input().split()))
e = [[] for _ in range(m+1)]
for i in range(m):
    a,b = list(map(int,input().split()))
    e[a].append(b)
    e[b].append(a)

q = deque()
q.append(1)

s = [float('inf') for _ in range(n+1)]
t = [float('inf') for _ in range(n+1)]
s[1] = 0
t[1] = 0
while len(q):
    node = q.pop()
    step = s[node]
    for i in range(len(e[node])):
        if s[e[node][i]] > step +1:
            q.append(e[node][i])
            s[e[node][i]] = step + 1
            t[e[node][i]] = node
# print(s,t,e)
for i in range(2,n+1):
    print(t[i])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(16000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)

Submission status: Runtime Error

Solution code:
import queue
N, M = map(int, input().split())
adj = [[] for i in range(N+1)]
parent = [-1] * (N+1)
for m in range(N):
    a, b  = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
q = queue.Queue()
q.put((1,0))
while(not q.empty()):
    x, p = q.get()
    if parent[x] != -1:
        continue
    parent[x] = p
    for next in adj[x]:
        if parent[next] == -1:
            q.put((next, x))
print("Yes")
for p in parent[2:]:
    print(p)