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:
def main():
	
	from collections import deque
	n,m = map(int,input().split())
	graph = [[] for _ in range(n+1)]
	
	for i in range(m):
		a,b = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)

	dist = [-1] * (n+1)
	dist[0] = 0
	dist[1] = 0

	d = deque()
	d.append(1)

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

	if graph[1] == '':
		print("No")
	else:
		for i in range(2,n+1):
			print(dist(i))
	


if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

q = deque([1])
dist = [-1] * (n + 1)
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        q.append(u)
        dist[u] = v

print("Yes")
# print(dist)

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

q = deque([0])
dist = [-1] * n
dist[0] = 0
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        dist[u] = v
        q.append(u)

print("Yes")
# print(dist)

for i in range(n):
    if i == 0:
        continue
    print(dist[i] + 1)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

n, m = tuple(map(int, sys.stdin.buffer.readline().split()))
L = tuple(tuple(map(int, sys.stdin.buffer.readline().split())) for _ in range(m))

# print(n, m)
# print(L)

X = [n + 1] * (n + 1)
X[1] = 0
Y = [0] * (n + 1)
d = defaultdict(set)
for a, b in L:
    d[a].add(b)
    d[b].add(a)
# print(d)
def search(i):
    for b in d[i]:
        point = X[i] + 1
        # print(f' {X[i]}')
        if point < X[b]:
            # print(i, b, X)
            X[b] = point
            # Y[b] = i
            search(b)
    
search(1)
# print(X)
s = X[0]
try:
    X.index(X[0], 1)
except ValueError:
    print('Yes')
    # for v in X[2:]:
    #     print(v)
    for i in range(2, n + 1):
      c = X[i]
      for v in d[i]:
        # print(i, c, v, X[v], c - 1== X[v])
        if c - 1 == X[v]:
          Y[i] = v
          break
    for v in Y[2:]:
        print(v)
else:
    print('No')

Submission status: Runtime Error

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

q = deque()
lndmrk[1] = 0
q.append(1)
while(len(q) != 0):
	v = q.popleft()
	for i in e[v]:
		if lndmrk[i] != -1:
			continue
		lndmrk[i] = v
		q.append(i)
f = 1
for i in range(2, n+1):
	if lndmrk[i] == -1:
		f = 0
if f:
	print("Yes")
	for i in range(2, n+1):
		print(lndmrk[i])
else:
	print("No")

Submission status: Runtime Error

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

q = deque()
lndmrk[1] = 0
q.append(1)
while(len(q) != 0):
	v = q.popleft()
	for i in e[v]:
		if lndmrk[i] != -1:
			continue
		lndmrk[i] = v
		q.append(i)
f = 1
for i in range(2, n+1):
	if lndmrk[i] != -1:
		f = 0
if f:
	print("Yes")
	for i in range(2, n+1):
		print(lndmrk[i])
else:
	print("No")

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

n, m = tuple(map(int, sys.stdin.buffer.readline().split()))
L = tuple(tuple(map(int, sys.stdin.buffer.readline().split())) for _ in range(m))

# print(n, m)
# print(L)

X = [n + 1] * (n + 1)
X[1] = 0
Y = [0] * (n + 1)
d = defaultdict(set)
for a, b in L:
    d[a].add(b)
    d[b].add(a)
# print(d)
def search(i):
    for b in d[i]:
        point = X[i] + 1
        # print(f' {X[i]}')
        if point < X[b]:
            # print(i, b, X)
            X[b] = point
            Y[b] = i
            search(b)
    
search(1)
s = X[0]
try:
    X.index(X[0], 1)
except ValueError:
    print('Yes')
    # for v in X[2:]:
    #     print(v)
    for v in Y[2:]:
        print(v)
else:
    print('No')

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

n, m = tuple(map(int, sys.stdin.buffer.readline().split()))
L = tuple(tuple(map(int, sys.stdin.buffer.readline().split())) for _ in range(m))

# print(n, m)
# print(L)

X = [n + 1] * (n + 1)
X[1] = 0
Y = [0] * (n + 1)
d = defaultdict(set)
for a, b in L:
    d[a].add(b)
    d[b].add(a)
print(d)
def search(i):
    for b in d[i]:
        point = X[i] + 1
        # print(f' {X[i]}')
        if point < X[b]:
            print(i, b, X)
            X[b] = point
            Y[b] = i
            search(b)
    
search(1)
s = X[0]
try:
    X.index(X[0], 1)
except ValueError:
    print('Yes')
    # for v in X[2:]:
    #     print(v)
    for v in Y[2:]:
        print(v)
else:
    print('No')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

Submission status: Runtime Error

Solution code:
from collections import deque

n,m,*ab = map(int, open(0).read().split())
to = [[] for _ in range(m+1)]

for i in range(0, m*2, 2):
    a = ab[i]
    b = ab[i+1]
    to[a].append(b)
    to[b].append(a)

ans = [None for _ in range(n+1)]
q = deque([1])
while q:
    p = q.pop()
    for i in to[p]:
        if ans[i] is None:
            ans[i] = p
            q.appendleft(i)

print("Yes")
print("\n".join(map(str, ans[2:])))

Submission status: Runtime Error

Solution code:
n,m,*ab = map(int, open(0).read().split())
to = [[] for _ in range(m+1)]

for i in range(0, m*2, 2):
    a = ab[i]
    b = ab[i+1]
    to[a].append(b)
    to[b].append(a)

checked = set()
ans = [None for _ in range(n+1)]
def fill(k):
    if k in checked:
        return
    checked.add(k)
    for i in to[k]:
        if ans[i] is None:
            ans[i] = k
    for i in to[k]:
        fill(i)
fill(1)

print("Yes")
print("\n".join(map(str, ans[2:])))

Submission status: Runtime Error

Solution code:
from collections import deque
n,m,*ab = map(int, open(0).read().split())

to = [set() for _ in range(n+1)]
ans = [None] * (n+1)
for i in range(0, n*2, 2):
    a = ab[i]
    b = ab[i+1]
    to[a].add(b)
    to[b].add(a)

q = deque([1])
while q:
    p = q.pop()
    children = to[p]
    for child in children:
        if ans[child] is None:
            ans[child] = p
            q.appendleft(child)

print("Yes")
print("\n".join(map(str, ans[2:])))

Submission status: Runtime Error

Solution code:
import math
n,m,*ab = map(int, open(0).read().split())

def calc():
    h = {}
    for i in range(0, n*2, 2):
        a = ab[i]
        b = ab[i+1]
        if a not in h:
            h[a] = set([b])
        else:
            h[a].add(b)
        if b not in h:
            h[b] = set([a])
        else:
            h[b].add(a)

    m = {}
    checked = set()
    def fill(k, d):
        if k in checked:
            return
        checked.add(k)
        if k in m:
            m[k] = min(m[k], d - 1)
        else:
            m[k] = d - 1
        for i in h[k]:
            if i in m:
                m[i] = min(m[i], d)
            else:
                m[i] = d
        for i in h[k]:
            fill(i, d+1)

    fill(1, 1)

    return [m[i] for i in range(2, n+1)]

ans = calc()
if ans is None:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
from collections import deque

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

dist = [-1 for i in range(n)]

G = [[] for i in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
# print(G)

dist[0] = 0
que = deque([0])

while len(que) != 0:
    v = que.popleft()

    for vi in G[v]:
        if dist[vi] != -1:
            continue
        que.append(vi)
        dist[vi] = dist[v] + 1

ans = "Yes"
for i in range(n):
    if dist[i] == -1:
        ans = "No"
        break

if ans == "No":
    print(ans)
else:
    print(ans)
    for i in range(1, n):
        print(dist[i])

Submission status: Runtime Error

Solution code:
import queue
I=lambda:map(int,input().split())
N,M=I()
ls=[[] for _ in range(M+1)]
for _ in[0]*M:
  A,B=I()
  ls[A]+=[B]
  ls[B]+=[A]
q = queue.Queue()
v=[-1]*(N+1)
v[0]=v[1]=0
q.put(1)
while not(q.empty()):
  top=q.get()
  for l in ls[top]:
    if v[l]<0:
      v[l]=top
      q.put(l)
if -1 in v:
  print("No")
else:
  print("Yes")
  [print(k) for k in v[2::]]

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque

    N, M = map(int, input().split())
    connected_rooms = [[] for i in range(N + 1)]
    
    for i in range(M):
        a, b = map(int, input().split())
        connected_rooms[a].append(b)
        connected_rooms[b].append(a)
    
    def Breadth_First_Search(root):
        queue = deque([root]) #calculate distance from the root
        distance = [None] * (N + 1) #initialize distance
        distance[root] = 0
        
        while (queue): #do BFS and calculate distance recursively
            ver = queue.popleft()
            
            for index in connected_rooms[ver]:
                if (distance[index] == None):
                    distance[index] = distance[ver] + 1
                    queue.append(index)
        
        return (distance)
    
    dist = [None] * (N + 1)
    dist[0] = True
    
    Q = deque([1])
    while (Q):
        index = Q.popleft()
        for j in connected_rooms[index]:
            if (dist[j] == None):
                
                # dist[j] = index
                dist[j] = dist[index] + 1
                
                Q.append(j)
    
    if (all(dist)):
        print('Yes')
        for i in dist[2:]:
            print(i)
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
AB = [""] * M

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

AB.sort()

Submission status: Runtime Error

Solution code:
def visit(frm,to,arr,isVisited):
    isVisited[to]=True
    for a in arr[to]:
        if isVisited[a] is True:
            continue
        visit(to,a,arr,isVisited)

N,M=[int(i) for i in input().split()]
rooms=[[] for i in range(N+1)]
for m in range(M):
    A,B=[int(i) for i in input().split()]
    rooms[A]+=[B]
    rooms[B]+=[A]

isVisited=[False]*(N+1)
isVisited[0:1]=[True,True]
visit(0,1,rooms,isVisited)

print("Yes")
for i in rooms[2:]:
    print(min(i))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

N, M = MI()
room = [[] for _ in range(N)]

for _ in range(M):
    A, B = MI()
    room[A - 1].append(B - 1)
    room[B - 1].append(A - 1)

print(room)
print("Yes")

def bfs(G, start, step = 0):
    global visited
    visited[start] = True 
    
    for g in G[start]:
        if g == 0:
            print(step + 1)
            
        elif not visited[g]:
            bfs(G, g, step + 1)

for i in range(1, N):
    visited = [False] * N
    bfs(room, i)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
con=[[] for i in range(m+1)]
check=[0 for i in range(n+1)]
for x in lst: con[x[0]].append(x[1]);con[x[1]].append(x[0])
check[1]=1
dis=[[1]]
i=0
while check.count(0)>1:
    work=[]
    for x in dis[i]:
        for y in con[x]:
            if check[y] : continue
            else : 
                work.append(y)
                check[y]=x
    dis.append(work)
    i+=1
print("Yes")
for j in range(2,n+1):
    print(check[j])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from queue import Queue
g = defaultdict(list)
visted = defaultdict(bool)
N, M = map(int, input().split())
for i in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)

h = {}
h2 = defaultdict(list)
def solve(v):
    height = 0
    visited = set()
    q = Queue()
    visited.add(v)
    h[v] = height
    h2[height].append(v)
    q.put(v)
    while not q.empty():
        v = q.get()
        height += 1
        for c in g[v]:
            if not c in visited:
                visited.add(c)
                h[c] = height
                h2[height].append(c)
                q.put(c)

solve(1)
ans = [0] * (N+1)

print('Yes')
for v in range(2, N+1):
    i = h[v]
    print(h2[i-1][0])

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

n,m = imap()
ab = np.array([iarr() for i in range(m)])
g = adj(n+1)
for i in range(n):
    aa,bb = ab[i][0],ab[i][1]
    g[aa].append(bb)
    g[bb].append(aa)

dep = iarr(n+1)
dep[1] = 1
q = col.deque([1])
route = iarr(n+1)
while q:
    now = q.popleft()
    for next in g[now]:
        if dep[next]: continue
        else:
            q.append(next)
            dep[next] = dep[now]+1
            route[next] = now

print("Yes")
for ans in route[2:]: print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input().split())
A=[set() for _ in range(m)]
for i in range(m):
  a,b=map(int,input().split())
  A[a-1].add(b)
  A[b-1].add(a)
visit=[0]*n
visit[0]=n+1
stack=deque()
stack.append(1)
while stack:
  now=stack.popleft()
  for j in A[now-1]:
    if visit[j-1]==0:
      visit[j-1]=now
      stack.append(j)
if min(visit)>0:
  print('Yes')
  for j in range(1,n):
    print(visit[j])
else:
  print('No')

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

n,m = imap()
ab = np.array([iarr() for i in range(m)])
a,b = ab.T[0]-1, ab.T[1]-1
adj = adj(n)
for i in range(n):
    aa,bb = a[i],b[i]
    adj[aa].append(bb)
    adj[bb].append(aa)

dep = iarr(n)
q = col.deque([0])
route = iarr(n)
while q:
    now = q.popleft()
    for next in adj[now]:
        if dep[next]: continue
        else:
            q.append(next)
            dep[next] = dep[now]+1
            route[next] = now

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>  // include all standard C++ libraries

using namespace std;

// Loops
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define _rrep(i,n) rrepi(i,n,0)
#define rrepi(i,a,b) for(int i=int(a)-1;i>=int(b);--i)

#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(xi, x) for (auto&& xi : x)
// Note: we can use rep(i,N) or rep(i,from,to)


// typedef
using ll = long long;
template <class T> using vec = vector<T>;
using vi   = vector<int>;
using vvi  = vector<vi>;
using vvvi = vector<vvi>;
using pii  = pair<int, int>;


// Constants

// Shorter repr for frequently used terms
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second


// Algorithms
#define all(x) (x).begin(), (x).end()
#define uniq(v) v.erase( unique(all(v)), v.end() )
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<class T> pair<T, size_t> max(vector<T> &x){ auto it = max_element(all(x)); return mp(*it, it-x.begin()); }
template<class T> pair<T, size_t> min(vector<T> &x){ auto it = min_element(all(x)); return mp(*it, it-x.begin()); }

template<class T> inline bool chmax(T &maxval, const T &newval) { if (maxval<newval) { maxval=newval; return 1; } return 0; }
template<class T> inline bool chmin(T &minval, const T &newval) { if (minval>newval) { minval=newval; return 1; } return 0; }

// Utilities
// Grid world utilities
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
#define inside(H,W,y,x) 0<=(x) && (x)<(W) && 0<=(y) && (y)<(H)

inline int in() {int x; cin >> x; return x;} // read int from cin
inline  ll IN() {ll x; cin >> x; return x;}  // read ll from cin



// Debug
#ifdef LOCAL
  #include "dump.hpp"
  #define debug(x) cerr << #x << ": " << x << '\n'
#else
  #define dump(...)
  #define debug(x)
#endif

// Paste snippets here!!
// Dijkstra for a weighted directed graph
//   G => adjlist
struct Dijkstra {
    typedef pair<int,int> pii;
    typedef pii Edge;  // (cost, to)
    vector<vector<Edge>> G; int V;
    Dijkstra(int V) : G(V), V(V) {}
    void add_edge(int from, int to, int cost){ G[from].push_back({cost,to}); }
    
    void solve(int from, vector<int> &d, vector<int>* back=nullptr)
    {   // back => if not nullptr, it will contain backward node id.
        fill(d.begin(), d.end(), numeric_limits<int>::max());
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        if(back) back->at(from) = -1;
        d[from] = 0; pq.push({0, from});
        while(!pq.empty()){
            auto p = pq.top(); pq.pop();
            int v = p.second;
            if(d[v]<p.first) continue;
            for(int i=0;i<G[v].size();++i){
                auto &e = G[v][i]; int c = e.first;
                if(chmin(d[e.second], d[v]+c)){
                    pq.push({d[v]+c, e.second});  // new cost, node
                    if(back) back->at(e.second) = p.second;
                }
            }
        }
    }
};
// 

int main(){
  cin.tie(0); ios::sync_with_stdio(false);    // Magic for faster cin
  int n, m; cin >> n >> m;
  int u, v;
  Dijkstra g(n);
  rep(i,m){
    cin >> u >> v;
    u--; v--;
    g.add_edge(u,v,1); g.add_edge(v,u,1);
  }
  int from = 0;
  vi d(n); vi back(n);
  g.solve(from, d, &back);
  cout << "Yes" << endl;
  rep(i,1,n){
    cout << back[i]+1 << endl;
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
def inbox(i, n):
    i = max(0, i)
    i = min(i, n)
    return(i)

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    a_new = [0 for _ in range(n)]
    for _ in range(k):
        b = [0 for p in range(n)]
        for i in range(n):
            l = inbox(i - a[i], n)
            r = inbox(i + a[i] + 1, n)
            b[l] += 1
            if r != n:
                b[r] -= 1

        a_new[0] = b[0]
        for i in range(1, n):
            a_new[i] = a_new[i-1] + b[i]
        if a_new == a:
            break
        a = a_new[:]

    print(' '.join(map(str, a_new)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = {}
for i in range(N):
  adj[i+1] = []
for i in range(M):
  v1, v2 = map(int, input().split())
  adj[v1].append(v2)
  adj[v2].append(v1)

visited = {1}
parent = {1: None}
frontier = [1]
while frontier:
  nxt = []
  for u in frontier:
    for v in adj[u]:
      if v not in visited:
        parent[v] = u
        nxt.append[v]
        visited.add[v]
  frontier = nxt

if len(visited) < N: print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(parent[i][0])

Submission status: Runtime Error

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

distance = [N] * N
distance[0] = 0
prev = [-1] * N

edges = [list(map(int, input().split())) for i in range(K)]
edge_dict = {i:[] for i in range(N)}
for i, j in edges:
  i -= 1
  j -= 1
  edge_dict[i].append(j)
  edge_dict[j].append(i)
  
def dfs(n = 0):
  for i in edge_dict[n]:
    if distance[i] > distance[n]+1:
      distance[i] = distance[n]+1
      prev[i] = n
      dfs(i)
    
dfs(0)
if len([i for i in prev[1:] if i == -1]) != 0:
  print("No")
else:
  print("Yes")
  for i in prev[1:]:
    print(i+1)

Submission status: Runtime Error

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

distance = [N] * N
distance[0] = 0
prev = [-1] * N

edges = [list(map(int, input().split())) for i in range(K)]
edge_dict = {i:[] for i in range(N)}
for i, j in edges:
  i -= 1
  j -= 1
  edge_dict[i].append(j)
  edge_dict[j].append(i)
  
def dfs(n = 0):
  for i in edge_dict[n]:
    if distance[i] >= distance[n]+1:
      distance[i] = distance[n]+1
      prev[i] = n
      dfs(i)
    
dfs(0)
if len([i for i in prev[1:] if i == -1]) != 0:
  print("No")
else:
  print("Yes")
  for i in prev[1:]:
    print(i+1)

Submission status: Runtime Error

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

from collections import deque

q = deque()

prev = [-1] * n

q.append(0)
while q:
    v = q.popleft()
    for e in edges[v]:
        if prev[e] != -1:
            continue
        prev[e] = v
        q.append(e)

print("Yes")
for val in prev[1:]:
    print(val + 1)

Submission status: Runtime Error

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

from collections import deque

q = deque()

prev = [-1] * n

q.append(0)
while q:
    v = q.pop()
    for e in edges[v]:
        if prev[e] != -1:
            continue
        prev[e] = v
        q.append(e)

print("Yes")
for val in prev[1:]:
    print(val + 1)

Submission status: Runtime Error

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

from collections import deque

q = deque()

prev = [-1] * n

q.append(0)
while q:
    v = q.pop()
    for e in edges[v]:
        if prev[e] != -1:
            continue
        prev[e] = v
        q.append(e)

print("Yes")
for val in prev[1:]:
    print(val + 1)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
G=[]
for i in range(0,M):
    G.append([])

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

q=[]
sign=[-1]*N
sign[0]=0
q.append(0)
while q:
    x=q.pop(0)
    for nv in G[x]:
        if sign[nv]==-1:
            sign[nv]=x
            q.append(nv)

print("Yes")
for i in range(1,N):
    print(sign[i]+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
for v in range(1,N): 
    for ve in [el in G[v] if dist[el] + 1 == dist[v]]:
        ans.append(ve+1)
        count += 1
        break
    if count != v: 
        print("No")
        sys.exit(0)
print("Yes")
for el in ans:
    print(el)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(M):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
step = 0
bfs(0,G,queue,dist)
print("Yes")
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            print(el+1)
            break

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**10)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(M):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
step = 0
bfs(0,G,queue,dist)
print("Yes")
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            print(el+1)
            break

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(M):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
bfs(0,G,queue,dist)
print("Yes")
for v in range(1,N): 
    for el in G[v]:
        if dist[v] == dist[el] + 1:
            print(el+1)
            break

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(M):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
step = 0
bfs(0,G,queue,dist)
for v in range(1,N): 
    for el in G[v]:
        if dist[v] == dist[el] + 1:
            print(el+1)
            break