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:
from sys import stdin


class DFS():
    def __init__(self,A_B_arr,N,M):
        self.N = N
        self.M = M
        self.route = {i:[] for i in range(N+1)}
        for A, B in A_B_arr:
            self.route[A].append(B)
            self.route[B].append(A)

        self.dp = [[None,self.N] for i in range(N+1)]
        self.dp[1] = [1,0]

    def dfs(self,i,rank):
        for r in self.route[i]:
            if rank<self.dp[r][1]:
                self.dp[r] = [i,rank]
                self.dfs(r,rank+1)
        return


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dfs = DFS(A_B_arr,N,M)
    dfs.dfs(1,1)

    #ans = []
    #TF = 'Yes'
    #for (i,_) in enumerate(dfs.dp):
    #    if i>1:
    #        if _[0] == None:
    #            TF = 'No'
    #            break
    #        else:
    #            ans.append(_[0])
    ## ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    #if TF == 'Yes':
    #    print(TF)
    #    for _ in ans:
    #        print(_)
    #else:
    #    print(TF)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    graph = [[] for _ in range(M)]
    for _ in range(M):
        A, B = map(int, readline().split())
        A -= 1; B -= 1
        graph[A].append(B)
        graph[B].append(A)
    trace = [-1]*N
    trace[0] = 0

    que = deque([0])
    while True:
        fr = que.popleft()
        for to in graph[fr]:
            if trace[to] != -1:
                continue
            trace[to] = fr
            que.append(to)
        if len(que) == 0:
            break

    if -1 in trace:
        print('No')
        return

    for t in trace[1:]:
        print(t+1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = map(int,input().split())
visited = [-1 for _ in range(n)]
g = [[] for _ in range(m)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
pos = 0
que = deque([])
if g[0]:
    visited[0] = 0
    for nx in g[0]:
        que.append((nx, 0))
while que:
    to, now = que.popleft()
    if visited[to] != -1:
        continue
    else:
        visited[to] = now
        for nx in g[to]:
            que.append((nx, to))
visited = visited[1:]
if -1 in visited:
    print('No')
else:
    print('Yes')
    for k in visited:
        print(k+1)

Submission status: Runtime Error

Solution code:
import sys
import  math
from heapq import *
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

    
N,M=nm()
INF=10**18
def bfs(start,edge):
    d=[INF]*(M+1)
    ans=[0]*(M+1)
    d[start]=0
    q=[(0,start)]
    while(len(q)!=0):
        ci,i=heappop(q)
        for j in edge[i]:
            if(d[j]>d[i]+1):
                d[j]=d[i]+1
                heappush(q,(d[j],j))
                ans[j]=i

    return ans




edge=[[]for _ in range(M+1)]
for i in range(M):
    A,B=nm()
    edge[A].append(B)
    edge[B].append(A)

ans=bfs(1,edge)

for i in range(2,M+1):
    if(ans[i]==0):
        print('No')
        sys.exit(0)

print('Yes')
for i in range(2,M+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
import math
def solution():
    n,m=map(int,input().split())
    a=[]
    b=[]
    con=[]
    for i in range(m):
        a1,b1=map(int,input().split())
        if(a1==1):
            con.append(b1)
        if(b1==1):
            con.append(a1)
        a.append(a1)
        b.append(b1)
    res=[]
    if(not con):
        print("No")
    else:
        count=0
        for _ in range(len(con)):
            res.append(1)
        for i in range(len(a)):
            if(a[i] in con and b[i] in con):
                count+=1
            if(a[i] in con):
                res.append(a[i])
            elif(b[i] in con):
                res.append(b[i])
        for x in con:
            res.remove(x)
        for i in range(count):
            for x in con:
                res.remove(x)
        print("Yes")
        for x in res:
            print(x)
if __name__ == "__main__":
    solution()

Submission status: Runtime Error

Solution code:
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 vector<vector<int>>g(100000);
 bool vis[100000] ;
 int parent[100000] ;
void solve()
{
	int n ,  m ; 
	cin>>n>>m;

	rep(i , m){
		int u , v; 
		cin>>u>>v ; 
		u--;
		v-- ;
		g[u].pb(v) ; 
		g[v].pb(u) ;
	}
	memset(vis,false,sizeof(vis));
	memset(parent , -1 , sizeof(parent));
	queue<int>q;

	q.push(0);
	vis[0] = true;
	while(!q.empty()){
		int tnode = q.front() ;
		q.pop() ;
		for(int temp : g[tnode]){
			if(!vis[temp]){
				vis[temp] = true;
				parent[temp]  = tnode ;
				q.push(temp);
			}
		}
	}
	rep(i , n){
		if(!vis[i]){
			cout<<"No";
			return;
		}
	}
	cout<<"Yes\n";
	repu(i,1 , n-1){
		cout<<parent[i]+1<<endl;
	}


}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    // cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Submission status: Runtime Error

Solution code:

def func(i, d, marks):
    rooms = numpy.nonzero(d[i])
    new_room = []
    for j in rooms[0]:
        room_idx = j
        if room_idx in marks:
            continue
        marks[room_idx] = i
        new_room.append(room_idx)
    for j in new_room:
        marks = func(j, d, marks)
    return marks

import numpy

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

marks = func(0, d, {0: 0})

flag = True
output_str = ''
for i in range(1, N):
    if i not in marks:
        flag = False
        break
    output_str += f'{marks[i]+1}\n'
if flag:
    print('Yes')    
    print(output_str)
else:
    print('No')

Submission status: Runtime Error

Solution code:
from sys import stdin


class DFS():
    def __init__(self,A_B_arr,N,M):
        self.N = N
        self.M = M
        self.route = {i:[] for i in range(N+1)}
        for A, B in A_B_arr:
            self.route[A].append(B)
            self.route[B].append(A)

        self.dp = [[None,self.N] for i in range(N+1)]
        self.dp[1] = [1,0]

    def dfs(self,i,rank):
        for r in self.route[i]:
            if rank<self.dp[r][1]:
                self.dp[r] = [i,rank]
                self.dfs(r,rank+1)
        return


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dfs = DFS(A_B_arr,N,M)
    dfs.dfs(1,1)

    ans = []
    TF = 'Yes'
    for (i,_) in enumerate(dfs.dp):
        if i>1:
            if _[0] == None:
                TF = 'No'
                break
            else:
                ans.append(_[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if TF == 'Yes':
        print(TF)
        for _ in ans:
            print(_)
    else:
        print(TF)

Submission status: Runtime Error

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

out = [0 for _ in range(n)]
out[0] = -1
import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    for j in graf[i]:
        if out[j] == 0:
            out[j] = i+1
            next_visit.put(j)
cnt = 1
for i in range(1, n):
    if out[i] == 0:
        cnt = 0
        break
if cnt:
    print("Yes")
    for i in out[1:]:
        print(i)
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import deque

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

seen = [0 for _ in range(N)]
seen[0] = 1
shirube = [-1 for _ in range(N-1)]

stack = deque([0])
while stack:
  now = stack.popleft()
  for i in G[now]:
    if seen[i] == 0:
      seen[i] = 1
      stack.append(i)
      shirube[i-1] = now
    
for i in range(N):
  if seen[i] == 0:
    print('No')
    break
else:
  print('Yes')
  for j in range(N-1):
    print(shirube[j]+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N,M = map(int,input().split())
    shirube = [None]*(N+1)
    shirube[1] = (1,0)
    mmap = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int,input().split())
        mmap[a].append(b)
        mmap[b].append(a)
    queue = deque()
    queue.appendleft((1,0))
    while queue:
        current_node, distance = queue.pop()
        for next_node in mmap[current_node]:
            new_distance = distance+1
            if shirube[next_node] is None:
                shirube[next_node] = (current_node, new_distance)
                queue.appendleft((next_node, new_distance))
            elif shirube[next_node][1] > new_distance:
                shirube[next_node] = (current_node, new_distance)
                queue.appendleft((next_node, new_distance))
    shirube = shirube[1::]
    if None in shirube:
        print("No")
        return
    print("Yes")
    for s in shirube[1::]:
        print(s[0])


if __name__ == '__main__':
    main()
ç

Submission status: Runtime Error

Solution code:

def saiki(i, abli, flag):

    ans = 1000
    iki = []
    ret = 0

    if i == 1:
        return 1

    for w in abli:
        if w[0] == i and flag[w[1]-1]:
            iki.append(w[1])

    for w in iki:
        flag[w-1] = False
        count = saiki(w, abli, flag)
        flag[w-1] = True
        if count == 100:
            return 100

        else:
            if ans >= count:
                ans = count
                ret = w

        #親まで帰ってきたときに深さを知りたい and 親側から最初の値を知りたい

    return ret

def d168(n, m, abli):

    ablirev = []
    ans = []
    for i in abli:
        ablirev.append([i[1],i[0]])
    abli = abli+ablirev

    for i in range(2, n+1):
        flag = [True]*n
        ff = saiki(i, abli, flag)

        if ff == 100:
            return "No"

        else:
            ans.append(ff)

    return ans

def main():
    n, m = map(int, input().split())
    abli = [list(map(int, input().split()))for i in range(m)]
    ans = d168(n, m, abli)
    print("Yes")
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

n,m = LI()
p = [[] for i in range(n)]
r = [-1]*n

def check(pp,rr,x):
    for i in pp[x]:
        if(rr[i] == -1 or rr[i] >= rr[x] + 1):
            rr[i] = rr[x] + 1
            check(pp,rr,i)

for _ in range(m):
    a,b = LI()
    p[a-1].append(b-1)
    p[b-1].append(a-1)

r[0] = 0
check(p,r,0)

flg = True
for i in range(n):
    if(r[i] == -1):
        flg = False
        break

if(flg):
    print("Yes")
    for i in range(1,n):
        print(r[i])
else:
    print("No")

Submission status: Runtime Error

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

for _ in range( n+1 ):
    connect.append( [ 0 ] * ( n+1 ) )

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

guide = [ 0 ] * ( n+1 )
path = [ 0, 0 ] + [ m+1 ] * ( n-1 )

def solve( a ): # aに隣接したやつのguideをaにする．またそれのpathをpath[a]+1にする．
    #print( "calc " + str(a) )
    for b in range( 1, n+1 ):
        if connect[a][b] == 1 and path[a] + 1 < path[b]:
            #print( "update " + str(b) )
            path[b] = path[a] + 1
            guide[b] = a
            solve(b)

solve( 1 )

#print( guide, path )
if 0 not in guide[2:]:
    print( "Yes" )
    for i in range( 2, n+1 ):
        print( guide[i] )
else:
    print( "No" )

Submission status: Runtime Error

Solution code:
import numpy as np
import copy

N,M = (int(x) for x in input().split())

edge = np.zeros([N,N])
for i in range(M):
    e = [int(x) for x in input().split()]
    edge[e[0]-1,e[1]-1] = 1
    edge[e[1]-1,e[0]-1] = 1

sign = np.zeros(N-1)
room = np.ones(N)
room[0] = 0
n_check = 0

# edge luck
if M<N-1:
    print('No')
else:
    check = [0]
    flag = 1
    
    for i in range(N):
        if flag:
            check_ = []
            for c in check:
                nogo = np.nonzero(room)[0]
                connect = np.nonzero(edge[c])[0]
                
                for con in connect:
                    if con in nogo:
                        room[con] = 0
                        check_.append(con)
                        sign[con-1] = int(c+1)
                        
                n_check += len(connect)
                if len(nogo)==0 or n_check>=2*M or len(check_)==0:
                    flag = 0
            check = copy.deepcopy(check_)
        else:
            break
if len(np.nonzero(sign)[0]) == N-1:
    print('Yes')
    for s in sign:
        print(s)
else:
    print('No')

Submission status: Runtime Error

Solution code:
#from collections import deque
n,m=map(int,input().split())
root=[[] for _ in range(m)]
for i in range(m):
	a,b=map(int,input().split())
	root[a-1].append(b-1)
	root[b-1].append(a-1)
times=[0]*n
sign=[-1]*n
sign[0]=0
#q=deque(root[0])
flag=0
a=root[0]
b=[]
f=False
while True:
	for i in a:
		if sign[i]==-1:
			sign[i]=flag
			b.extend(root[i])
			f=True
	flag=i
	a=b
	b=[]
	if f==False:
		break
	f=False
for i in range(n-1):
	print(sign[i+1]+1)

Submission status: Runtime Error

Solution code:
import math
import sys

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


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

corridorlist = [tuple(map(int,input().split())) for i in range(M)]

rooms = [set() for _ in range(N + 1)]
shirube = [(-1, M) for _ in range(N + 1)]
shirube[1] = (0, 0)

for cor in corridorlist:
    rooms[cor[0]].add(cor[1])
    rooms[cor[1]].add(cor[0])

rec(rooms, 1, 0)

if any([s[0] == -1 for s in shirube[1:]]):
    print('No')
else:
    print('Yes')
    for s in shirube[2:]:
        print(s[0])

Submission status: Runtime Error

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

n, m = map(int, input().split())
e = np.zeros((n, n))
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    e[a][b] = 1
    e[b][a] = 1
dist, predecessor = dijkstra(e, directed=False, return_predecessors=True)

if all(type(v) == np.int32 for v in predecessor[0][1:]):
    print("Yes")
    for v in predecessor[0][1:]:
        print(v + 1)
else:
    print("No")

Submission status: Runtime Error

Solution code:
# D - .. (Double Dots)

from collections import deque
N, M = map(int, input().split())
tree = [[] for _ in range(M)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    tree[A].append(B)
    tree[B].append(A)

ans_arr = [-1] * (N)
q = deque()
ans_arr[0] = 0 
q.append(0)

while len(q)>0:
    n = q.popleft()
    for i in tree[n]:
        if ans_arr[i] == -1:
            ans_arr[i] = n+1
            q.append(i)

ans = 'Yes'
for i in ans_arr[1:]:
    if i == -1:
        ans = 'No'
        break

if ans == 'No':
    print(ans)
else:
    print(ans)
    for i in ans_arr[1:]:
        print(i)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
root_list = []
for _ in range(m):
    root_list.append(list(map(int, input().split())))

answer_list = [0] * (n-1)
done_list = [1]
already_list = [1]
while len(root_list) > 0 and 0 in answer_list:
    tmp_list = []
    copy_root_list = root_list.copy()
    for num in done_list:
        for l in root_list:
            if l[1] == num:
                if answer_list[int(l[0]-2)] == 0:
                    answer_list[int(l[0]-2)] = num
                    tmp_list.append(l[0])
                    already_list.append(l[1])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
            elif  l[0] == num:
                if answer_list[int(l[1]-2)] == 0:
                    answer_list[int(l[1]-2)] = num
                    tmp_list.append(l[1])
                    already_list.append(l[1])
                    if l in copy_root_list:
                        copy_root_list.remove(l)
                else:
                    if l in copy_root_list:
                        copy_root_list.remove(l)
    copy_root_list = [i for i in copy_root_list if (i[0] not in already_list or i[1] not in already_list)]
    root_list = copy_root_list
    done_list = tmp_list

if 0 not in answer_list:
    print("Yes")
    for i in answer_list:
        print(int(i))
else:
    print("No")

Submission status: Runtime Error

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

for _ in range( n+1 ):
    connect.append( [ 0 ] * ( n+1 ) )

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

guide = [ 0 ] * ( n+1 )
path = [ 0, 0 ] + [ m+1 ] * ( n-1 )

def solve( a ): # aに隣接したやつのguideをaにする．またそれのpathをpath[a]+1にする．
    print( "calc " + str(a) )
    for b in range( 1, n+1 ):
        if connect[a][b] == 1 and path[a] + 1 < path[b]:
            print( "update " + str(b) )
            path[b] = path[a] + 1
            guide[b] = a
            solve(b)

solve( 1 )

print( guide, path )
if 0 not in guide[2:]:
    print( "Yes" )
    for i in range( 2, n+1 ):
        print( guide[i] )
else:
    print( "No" )

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
a = []
b = []
for i in range(M):
    aa, bb = list(map(int, input().split()))
    a.append(aa-1)
    b.append(bb-1)
    
table = [0] * N
ans = [0] * N

table[0] = 1


#start
q = [0]

while(q):
    
    x = q[0]
    
    for i in range(len(a)):
        if a[i] == x:
            if table[b[i]]==0:
                table[b[i]]=1
                ans[b[i]]=a[i]+1
                q.append(b[i])
                a.pop(i)
                b.pop(i)
            else:
                a.pop(i)
                b.pop(i)
                
        if b[i] == x:
            if table[a[i]]==0:
                table[a[i]]=1
                ans[a[i]]=b[i]+1
                q.append(a[i])  
                a.pop(i)
                b.pop(i)
            else:
                a.pop(i)
                b.pop(i)
    
    q.pop(0)

if sum(table)==N:
    print("Yes")
    for i in range(1,N):
        print(ans[i])
else:
    print("No")

Submission status: Runtime Error

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

seen = [False for i in range(n)]
que = deque()
def bfn(i,j):
    if seen[i-1]==False:
        seen[i-1]=j
    for x in pas[i]:
        if seen[x-1]!=False:
            continue
        que.append([x,i])
    if que:
        now,pre =que.popleft()
        bfn(now,pre)
    else:
        return

bfn(1,1)

if False in seen:
    print("No")
else:
    print("Yes")
    for i in range(n-1):
        print(seen[i+1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

root = np.zeros((n,n), dtype = int)

for ab in AB:
    root[ab[0]-1][ab[1]-1]=1
    root[ab[1]-1][ab[0]-1]=1

sign = [0]*n
sign[0]=-1
list = [0]

while True:
    x = list.pop(0)

    for y, bool in enumerate(root[x]):
        if sign[y]==0 and bool==1:
            sign[y]=x+1
            list.append(y)

    if len(list)==0:
        break

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

lis=[[] for i in range(n)]

for i in range(m):
    aa,bb=list(map(int,input().split()))
    lis[aa-1].append(bb-1)
    lis[bb-1].append(aa-1)

ok=set()
ok.add(0)
# tugi=deque()
mic=[None for i in range(n)]
def search(x):
    for i in lis[x]:
        if i in ok:
            continue
        ok.add(i)
        search(i)
        mic[i]=x
        # if mic[i]==None:
        #     mic[i] = x
        # else:
        #     print('No')
        #     exit()
    return


search(0)
mic.pop(0)

if None in mic:
    print('No')
else:
    print('Yes')
    for i in range(n-1):
        print(mic[i]+1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
PATHS = list([tuple(map(lambda t: int(t) - 1, input().split())) for i in range(M)])

def follow_guide(start, guides):
    next_room = guides[start]

    depth = 1

    while next_room != 0:
        depth += 1
        next_room = guides[next_room]
    
    return depth


def find_shortest(start, paths, tracks, depth):
    ls_in = []
    ls_ex = []

    for r1, r2 in paths:
        if r1 == start:
            if r2 == 0: return depth, tracks + [0]

            ls_in.append((r1, r2))

        elif r2 == start:
            if r1 == 0: return depth, tracks + [0]

            ls_in.append((r2, r1))

        else:
            ls_ex.append((r1, r2))
    
    #print(ls_in, start, tracks, depth)
    
    return min([find_shortest(r2, ls_ex, tracks + [r2], depth + 1) for r1, r2 in ls_in], key=lambda t:t[0])

guides = [1]
depths = [0]

for i in range(1, N):
    depth, tracks = find_shortest(i, PATHS, [], 1)
    guide = tracks[0]

    guides.append(guide)
    depths.append(depth)

if not all([follow_guide(i, guides) == depths[i] for i in range(1, N)]):
    print("No")

else:
    print("Yes")

    for guide in guides[1:]:
        print(guide + 1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
path_list = []
for i in range(M):
    z = []
    path_list.append(z)
for i in range(M):
    A,B = map(int,input().split())
    path_list[A-1].append(B)
    path_list[B-1].append(A)
chk = [0] * N

def bfs(a,chk,path):
    queue = [a]
    while queue:
        b = queue.pop(0)
        for i in range(len(path[b-1])):
            if chk[path[b-1][i]-1] == 0:
                queue.append(path[b-1][i])
                chk[path[b-1][i]-1] =b
    return chk
bfs(1,chk,path_list)
print("Yes")
for i in range(N):
    if i == 0:
        continue
    else:
        print(chk[i])

Submission status: Runtime Error

Solution code:
#!python3

import sys
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, M = iim()
    it = map(int, sys.stdin.read().split())

    d1 = defaultdict(list)

    for i, j in zip(it, it):
        d1[i].append(j)
        d1[j].append(i)

    ans = [0] * (N+1)
    dq = [1]
    visited = set([1])
    cnt = 0

    while True:
        dq2 = []
        for i in dq:
            for j in d1[i]:
                if j in visited:
                    continue
                dq2.append(j)
                ans[j] = i
            visited.update(dq2)
            cnt += 1

        if not dq2:
            break

        dq = dq2

    if cnt == N:
        print("Yes", *ans[2:], sep="\n")
    else:
        printi("No")





if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from collections import deque
def search(l,dic1,dic2):
    if not l:
        return(dic2)
    else:
        x=l.pop()
        for y in dic1[x]:
            if dic2[y]==0:
                l.appendleft(y)
                dic2[y]=x
        return search(l,dic1,dic2)

n,m=map(int,input().split())
l=[i+1 for i in range(n)]
dic1={i:[] for i in l}
dic2={i:0 for i in l}
for _ in range(m):
    a, b = map(int, input().split())
    dic1[a].append(b)
    dic1[b].append(a)
l=deque(dic1[1])
for z in l:
    dic2[z]=1

d=search(l,dic1,dic2)
print('Yes')
for k in range(2,n+1):
    print(dic2[k])

Submission status: Runtime Error

Solution code:
from sys import stdin


class DFS():
    def __init__(self,A_B_arr,N,M):
        self.N = N
        self.M = M
        self.route = {i:[] for i in range(N+1)}
        for A, B in A_B_arr:
            self.route[A].append(B)
            self.route[B].append(A)

        self.dp = [[None,float('inf')] for i in range(N+1)]
        self.dp[1] = [1,0]

    def dfs(self,i,rank):
        if rank>self.N:
            return
        else:
            for r in self.route[i]:
                if rank<self.dp[r][1]:
                    self.dp[r] = [i,rank]
                    self.dfs(r,rank+1)
            return


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        A_B_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dfs = DFS(A_B_arr,N,M)
    dfs.dfs(1,1)

    ans = []
    for (i,_) in enumerate(dfs.dp):
        if i>1 and _[0] == None:
            TF = 'No'
            break
        else:
            ans.append(_[0])
    else:
        TF = 'Yes'
        ans = ans[2:]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if TF == 'Yes':
        print(TF)
        for _ in ans:
            print(_)
    else:
        print(TF)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
data=[]
ans=[n]*n
ans[0]=0
for i in  range(m):
    data.append(sorted(list(map(int,input().split()))))

print("yes")

for i in range(n):#距離がi
    for j in range(n):#j番目の部屋から
        if(ans[j]==i):
            for k in range(n):#dataを参照
                if(data[k][0]==j+1):
                    ans[data[k][1]-1]=min(i+1,ans[data[k][1]-1])
                    

for i in range(1,n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import queue

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

ans = [-1 for _ in range(n)]
ans[0] = 0
q = queue.Queue()
q.put(0)
while not q.empty():
    start = q.get()
    for end in maze[start]:
        if ans[end] == -1:
            q.put(end)
            ans[end] = start

if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i]+1)