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.

Solution (Python):
from collections import deque
N, M = map(int, input().split())
route = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  route[A-1].append(B-1)
  route[B-1].append(A-1)
ans = [-1]*(N)

def bfs():
  tmp = 0
  prv = 0
  visited = [False]*N
  kouho = deque()


  for room in route[0]:
    kouho.append([room,0])
  while True:
    visited[tmp] = True
    ans[tmp] = prv
    for room in route[tmp]:
      if not visited[room]:
        kouho.append([room,tmp])
    if len(kouho) == 0:
      return
    while True:
      tmp_ = kouho.popleft()
      tmp = tmp_[0]
      prv = tmp_[1]
      if not visited[tmp]:
        break
      if len(kouho) == 0:
        return
bfs()
print("Yes")
for n in range(1,N):
  print(ans[n]+1)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
adjacent=[set() for x in range(N)]
for m in range(M):
    A,B=map(int,input().split())
    adjacent[A-1].add(B-1)
    adjacent[B-1].add(A-1)
ans=[0]*N
deque1=deque()
already=set()
already.add(0)
num_already=1
for j in adjacent[0]:
    deque1.append(j)
    already.add(j)
    num_already+=1
    ans[j]=1
while(num_already!=N):
    now=deque1.popleft()
    for k in adjacent[now]:
        if k not in already:
            num_already+=1
            already.add(k)
            ans[k]=now+1
            deque1.append(k)
print("Yes")
for i in range(1,N):
    print(ans[i])

Solution (Python):
from collections import deque


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


def input_array():
	return list(map(int,input().split()))
  
n,m=input2()
g=[[] for _ in range(n+1)] 
for i in range(m):
	a,b=input2()
	g[a].append(b)
	g[b].append(a)

q=deque() 
q.append(1) 

check=[0]*(n+1) 
check[1]=1

ans=[0]*(n+1) 
ans[1]=1
for _ in range(10**5+1):
	if len(q)==0:
		break
	v=q.popleft() 
	for u in g[v]: 
		if check[u]==0: 
			check[u]=1 
			ans[u]=v 
			q.append(u)
print("Yes")
for i in range(2,n+1):
	print(ans[i])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect


import numpy as np
from scipy.sparse.csgraph import breadth_first_order, depth_first_order, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

import sys

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

N, M = na()
edge = np.array([na() + [1] for _ in range(M)], dtype=np.int64).T
g = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
d, root = breadth_first_order(g, directed=False, return_predecessors=True, i_start = 0)
if -9999 not in d[1:]:
    print('Yes')
    for i in range(1, N):
        print(root[i] + 1)
else:
    print('No')

Solution (Python):
from collections import deque
N,M=map(int,input().split())
C=[[] for i in range(N+1)]
for i in range(M):
  A,B=sorted(list(map(int,input().split())))
  C[A].append(B)
  C[B].append(A)

d=[-1]*(N+1)
d[0]=0
d[1]=0

queue=deque([1])
while queue:
  now = queue.popleft()
  for i in C[now]:
    if d[i]!=-1:continue
    d[i]=now
    queue.append(i)

if d.count(0)>2:print('No');exit
print('Yes')
for i in range(2,N+1):
  print(d[i])

Solution (Python):
from collections import deque
N,M=map(int,input().split())
A=[0]*M;B=[0]*M
C=[[] for i in range(N+1)]

for i in range(M):
  A[i],B[i]=sorted(list(map(int,input().split())))
  C[A[i]].append(B[i])
  C[B[i]].append(A[i])

d=[-1]*(N+1)
d[0]=0
d[1]=0

queue=deque([1])
while queue:
  now = queue.popleft()
  for i in C[now]:
    if d[i]!=-1:continue
    d[i]=now
    queue.append(i)

if d.count(0)>2:print('No');exit
print('Yes')
for i in range(2,N+1):
  print(d[i])

Solution (Python):
from collections import deque
N,M=map(int,input().split())
A=[0]*M;B=[0]*M
C=[[] for i in range(N+1)]

for i in range(M):
  A[i],B[i]=sorted(list(map(int,input().split())))
  C[A[i]].append(B[i])
  C[B[i]].append(A[i])

d=[-1]*(N+1)
d[0]=0
d[1]=0

queue=deque([1])
while queue:
  now = queue.popleft()
  for i in C[now]:
    if d[i]!=-1:continue
    if d[i]==-1:d[i]=now

    queue.append(i)






if d.count(0)>2:print('No');exit
print('Yes')
for i in range(2,N+1):
  print(d[i])

Solution (Python):
from collections import deque
N,M=map(int,input().split())
A=[0]*M;B=[0]*M
C=[[] for i in range(N+1)]

for i in range(M):
  A[i],B[i]=sorted(list(map(int,input().split())))
  C[A[i]].append(B[i])
  C[B[i]].append(A[i])

d=[-1]*(N+1)
d[0]=0
d[1]=0

queue=deque()
queue.append(1)

while queue:
  now = queue.popleft()
  for i in C[now]:
    if d[i]!=-1:continue
    d[i]=d[now]+1
    queue.append(i)

E=[0]*(N+1)
for i in range(M):

  if d[B[i]]-d[A[i]]==1 and E[B[i]]==0:E[B[i]]=A[i]
  elif d[A[i]]-d[B[i]]==1 and E[A[i]]==0:E[A[i]]=B[i]
if E.count(0)>2:print('No');exit
print('Yes')
for i in range(2,N+1):
  print(E[i])

Solution (Python):
from collections import deque

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

d = deque([1])

while d:
  v = d.popleft()
  for i in g[v]:
    if yet[i] == -1:
      yet[i] = v
      d.append(i)
      
ans = yet[2:]
print("Yes")
print(*ans, sep="\n")

Solution (Python):
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))

from collections import deque
 
n, m =MI()
 
ans = [-1 for _ in range(n+1)]


ans[0] = 0
ans[1] = 0
 
V = [[] for _ in range(n+1)]
 
for _ in range(m):
    x, y = MI()
    V[x].append(y)
    V[y].append(x)
 
d = deque([1])
 
while d:
    l = d.popleft()
    for v in V[l]:
        if ans[v] != -1:
            continue
        ans[v] = l
        d.append(v)
        
 
    
if ans.count(-1) > 0:
    print('No')
else :
    print('Yes')
    for i in ans[2:]:
        print(i)

Solution (Python):
def main(sample_file = ''):

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product, combinations_with_replacement 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):   
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    
    from operator import itemgetter 
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd
    def gcd(a,b):
        
        
        if a<b:
            a, b = b, a
        while a%b !=0 :
            a, b = b, a%b
        return b

    
    
    
    
    
    

    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)
    def make_divisors(n, reversed=False):
        """create list of divisors
        
        Args:
            number (int): number from which list of divisors is created
            reversed (bool, optional): ascending order if False. Defaults to False.
        
        Returns:
            list: list of divisors
        """
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(list(divisors),reverse=reversed)

    
    def sieve_of_eratosthenes(end, typecode="L"):
        
        

        
        import array
        import textwrap
        assert end > 1
        
        
        
        is_prime = array.array("B", (True for i in range(end)))
        
        is_prime[0] = False
        is_prime[1] = False
        
        primes = array.array(typecode)
        
        for i in range(2, end):
            if is_prime[i]:
                primes.append(i)
                for j in range(2 * i, end, i):
                    is_prime[j] = False  
        return primes

    class PrimeFactorization:
        '''初期化にO(NloglogN)/ 因数分解クエリをO(log(k))/ 素数判定クエリをO(1)
        >>> pf = PrimeFactorization(100)
        >>> pf.query(100)
        ((2, 2), (5, 2))
        
        '''
        
        
        
        
        
        
        
        def __init__(self, Num=10**6):
            from collections import defaultdict
            from math import floor
            self.Num = Num
            self.D = [-1] * (Num+1)
            for i in range(2, Num+1):
                if self.D[i] != -1:
                    continue
                self.D[i] = i
                for j in range(1, floor(Num/i)+1):
                    if self.D[j*i] != -1:
                        continue
                    else:
                        self.D[j*i] = i
        
        def query(self, k):
            ans = defaultdict(int)
            tmp = k
            while self.D[tmp] != -1:
                div = self.D[tmp]
                ans[div] += 1
                tmp = tmp//div
            return tuple(ans.items())
        
        def is_prime(self, k):
            return k == self.D[k]

    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    AtoZ = list('abcdefghijklmnopqrstuvwxyz') 
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something like:
        >>      pass
        >>  else:
        >>      do something like:
        >>      L[find_root(a)] = L[find_root(a)] + L[find_root(b)]
        >>      L[find_root(b)] = L[find_root(a)]
        >>      
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    
    
    
    class SegTree:
        """
        ref: https://qiita.com/takayg1/items/c811bd07c21923d7ec69
        init(init_val, ide_ele): 配列init_valで初期化 O(N)
        update(k, x): k番目の値をxに更新 O(logN)
        query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
        
        操作	    segfunc	        単位元
        最小値	    min(x, y)	    float('inf')
        最大値	    max(x, y)	    -float('inf')
        区間和	    x + y	        0
        区間積	    x * y	        1
        最大公約数	math.gcd(x, y)	0
        
        ex: seg = SegTree([14, 5, 9, 13], min, float('inf'))
        """
        def __init__(self, init_val, segfunc, ide_ele):
            """
            init_val: 配列の初期値
            segfunc: 区間にしたい操作
            ide_ele: 単位元
            n: 要素数
            num: n以上の最小の2のべき乗
            tree: セグメント木(1-index)
            """
            n = len(init_val)
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.num = 1 << (n - 1).bit_length()
            self.tree = [ide_ele] * 2 * self.num
            
            for i in range(n):
                self.tree[self.num + i] = init_val[i]
            
            for i in range(self.num - 1, 0, -1):
                self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

        def update(self, k, x):
            """
            k番目の値をxに更新
            k: index(0-index)
            x: update value
            """
            k += self.num
            self.tree[k] = x
            while k > 1:
                self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
                k >>= 1

        def query(self, l, r):
            """
            [l, r)のsegfuncしたものを得る
            l: index(0-index)
            r: index(0-index)
            """
            res = self.ide_ele
            l += self.num
            r += self.num
            while l < r:
                if l & 1:
                    res = self.segfunc(res, self.tree[l])
                    l += 1
                if r & 1:
                    res = self.segfunc(res, self.tree[r - 1])
                l >>= 1
                r >>= 1
            return res

    
    
    
    
    
    
    
    

    def BellmanFord(N, M, ABC, vertex_start, vertex_end, value_if_inf = -1, find_shortest = False):
        """to calculate furthest or shortest length between vertex_start and vertex_end using BellmanFord algorithm
        
        Args:
            N (int): number of vertices
            M (int): number of edges
            ABC (list): [(ai, bi, ci) for _ in range(N)] where i-th edge is directed from vertex ai to vertex bi and the length is ci 
            vertex_start (int): start vertex. usually use 0.
            vertex_end (int): end vertex. usually use N-1.
            value_if_inf (int or string as you like, optional): value you want when the furthest (or shortest) distance is infinite (or -infinite). Defaults to -1.
            find_shortest (bool, optional): choose False to find furthest path. Defaults to False.
        
        Returns:
            int or string: normally int (but can be str if you set value_if_inf to str)
            
        Example:
                N, M, P = R()
                ABC = [R() for _ in range(M)]
                ABC = [(a-1, b-1, c-P) for a, b, c in ABC]
                print(BellmanFord(N, M, ABC, 0, N-1, value_if_inf = 'inf'))

        """

        def make_reachable_list(N, M, ABC, vertex_start, vertex_end):
            reachable_to_direct = defaultdict(list)
            reachable_from_direct = defaultdict(list)
            reachable_from_start = [False] * N
            reachable_to_end = [False] * N
            reachable_from_start[vertex_start] = True
            reachable_to_end[vertex_end] = True
            reachable_from_both_sides = [False] * N
            dfs_from_start = []
            dfs_to_end = []
            for a, b, c in ABC:
                reachable_to_direct[a].append(b)
                reachable_from_direct[b].append(a)
                if a == vertex_start:
                    dfs_from_start.append(b)
                    reachable_from_start[b] = True
                if b == vertex_end:
                    dfs_to_end.append(a)
                    reachable_to_end[a] = True
            while dfs_from_start:
                v = dfs_from_start.pop()
                for i in reachable_to_direct[v]:
                    if not reachable_from_start[i]:
                        reachable_from_start[i] = True
                        dfs_from_start.append(i)
            while dfs_to_end:
                v = dfs_to_end.pop()
                for i in reachable_from_direct[v]:
                    if not reachable_to_end[i]:
                        reachable_to_end[i] = True
                        dfs_to_end.append(i)
            for i in range(N):
                reachable_from_both_sides[i] = reachable_from_start[i] and reachable_to_end[i]
            return reachable_from_both_sides
        
        reachable_from_both_sides = make_reachable_list(N, M, ABC, vertex_start, vertex_end)
        
        if find_shortest:
            dist = [INF for i in range(N)]
        else:
            dist = [-INF for i in range(N)]
        
        dist[vertex_start] = 0
        for i in range(N):
            updated = False
            for a, b, c in ABC:
                if not reachable_from_both_sides[a]:
                    continue
                elif find_shortest:
                    update_condition = dist[a] + c < dist[b]
                else:
                    update_condition = dist[a] + c > dist[b]
                if dist[a] != INF and update_condition:
                    dist[b] = dist[a] + c
                    updated = True
                    if i == N-1:
                        return value_if_inf
            if not updated:
                break
        return dist[vertex_end]

    
    def warshall_floyd(number_vertex, XYD, shift_one_for_vertex=False):
        
        
        
        
        
        d = [[float("inf")]*number_vertex for i in range(number_vertex)]
        for x, y, dist in XYD:
            if shift_one_for_vertex:
                x = x - 1
                y = y - 1
            d[x][y] = dist
            d[y][x] = dist
        for i in range(number_vertex):
            d[i][i] = 0 
        for k in range(number_vertex):
            for i in range(number_vertex):
                for j in range(number_vertex):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d


    """ initialize variables and set inputs
    
        
        
            
            
    
        
        
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    r_float = lambda: float(r())
    R = lambda: list(map(int, r().split()))
    
    R_map = lambda: map(int, r().split())
    R_float = lambda: list(map(float, r().split()))
    R_tuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    
    if sample_file:
        sys.stdin = open(sample_file)
    
    
    import random
    
    
    
    
    N, M = R()
    AB = [R() for _ in range(M)]
    C = [[] for _ in range(N)]
    for a, b in AB:
        C[a-1].append(b-1)
        C[b-1].append(a-1)
    task = deque([0])
    arrived = [0] * N
    ans = [0] * (N-1)
    arrived[0] = True
    while task:
        c = task.popleft()
        for d in C[c]:
            if arrived[d]:
                pass
            else:
                task.append(d)
                ans[d-1] = c + 1
                arrived[d] = True
    print('Yes')
    print(*ans)
    
    
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    https://atcoder.jp/contests/abc173/submissions/14966961
    for i in range(1<<h):
	    if (i >> x) & 1:
            hoge
    (1 >> x) & 1 でNビット目のビット値を取得している
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def show_2d_array(array):
    [print(a) for a in array]


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

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





def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))
    depth = [0] * N
    depth[p] = 0
    current_depth = depth[p]
    while len(queue) > 0:
        
        q = queue.popleft()
        seen[q] = True
        
        for v in tree[q]:
            if not seen[v]:
                depth[v] = depth[q] + 1
                queue.append(v)
                seen[v] = True


    return depth


depth = bfs(cave, 0)



sign = [0] * N
ans = "Yes"
for i in range(1, N):
    this_depth = depth[i]
    found = False
    for j in cave[i]:
        if depth[j] == this_depth - 1:
            sign[i] = j
            found = True
            break
    if not found:
        ans = "No"
        break

"""
for i in range(1, N):
    current = i
    found = False
    while not found:
        next = -1
        for j in cave[current]:
            if depth[j] == depth[current]-1:
                if sign[current] <= 0:
                    next = j
                    sign[current] = next
                    break
                else:
                    next = sign[current]
                    break
        if next < 0:
            ans = "No"
            break

        current = next
        if current == 0:
            found = True
"""

print(ans)
if ans == "Yes":
    [print(s+1) for s in sign[1:]]

Solution (Python):
from collections import deque
n,m=map(int,input().split())
data=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  data[a].append(b)
  data[b].append(a)
que=deque()
que.append(1)
cnt=[0]*(n+1)
while que:
  h=que.popleft()
  for u in data[h]:
    if cnt[u]!=0:
      continue
    cnt[u]=h
    que.append(u)
print('Yes')
for i in range(2,n+1):
  print(cnt[i])

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline

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

    distances = [-1] * N
    instructions = [-1] * N
    distances[0] = 0
    d = deque([0])
    while d:
        current_room = d.popleft()
        for next_room in graph[current_room]:
            if distances[next_room] == -1 or distances[current_room] + 1 < distances[next_room]:
                distances[next_room] = distances[current_room] + 1
                instructions[next_room] = current_room
                d.append(next_room)
    print('Yes')
    for v in instructions[1:]:
        print(v+1)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = list(map(int, input().split()))
rooms = [list() for _ in range(N+1)]

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

from collections import deque

INF = 10**9+1
steps = [INF] * (N+1)
mk = [0] * (N+1)
ck = deque([1])
steps[1] = 0

while len(ck)>0:
    i = ck.popleft()
    current = steps[i]
    for j in rooms[i]:
        if steps[j] > current+1:
            ck.append(j)
            steps[j] = current+1
            mk[j] = i

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

Solution (Python):
from sys import stdin
from collections import deque
import numpy as np
class edge(object):
    def __init__(self, to, rev):
        self.to = to
        self.rev = rev
def add_edge(from_, to_, G):
    G[from_].append(edge(to_, len(G[to_])))
    G[to_].append(edge(from_, len(G[from_])-1))

def bfs(src, level, li, li_from):
    que = deque([src])
    level[src] = 0
    while len(que)!=0:
        v = que.popleft()
        for i in range(len(li[v])):
            e = li[v][i]
            if level[e.to]<0:
                level[e.to] = level[v]+1
                li_from[e.to] = v
                que.append(e.to)

n,m = map(int, input().split())
li = []
for i in range(n):
    li.append([])
for i in range(m):
    a, b = map(int,  stdin.readline().split())
    if a > b:
        a, b = b, a
    add_edge(a-1, b-1, li)


if len(li[0])==0:
    print("No")
else:
    print("Yes")
    level = np.full(n, -1, dtype=np.int)
    li_from = np.full(n, -1, dtype=np.int)
    bfs(0,level,li, li_from)
    for i in li_from:
        if i==-1:
            continue
        print(i+1)

Solution (Python):
from collections import deque
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

q = deque()
q.append(0)
ans = [0]*N
while q:
    par = q.popleft()
    for e in E[par]:
        if ans[e] > 0:
            continue
        ans[e] = par+1
        q.append(e)

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                queue.append(i)
    return d


d = bfs(0)
print('Yes')
for i in range(1,n):
    for j in g[i]:
        if d[j]<d[i]:
            print(j+1)
            break