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())

ab=[list(map(int,input().split())) for _ in range(m)]
ans=[0]*n
def dfs():
    deq.append(0)
    finish=set()
    finish.add(0)
    while deq:
        now=deq.popleft()
     
        for ad_i in adlist[now]:
            if ad_i-1 != now and ad_i-1 not in finish:
                if ans[ad_i-1]==0:
                    ans[ad_i-1]=now+1
                deq.append(ad_i-1)
                finish.add(ad_i-1)

adlist=[[] for _ in range(n)]
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)

deq=deque()
dfs()
print("Yes")
for i in range(1,n):
    print(ans[i])

Solution (Python):
import sys
from collections import deque
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int, readline().split())
 
G = [[] for _ in range(N + 1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)
 
par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)
 
print('Yes')
print(*par[2:], sep='\n')

Solution (Python):
INF=9999999
N,M=map(int,input().split())

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

pathlist=[0]
roomsign=[INF]*N
roomsign[0]=1

while pathlist:
    nth=pathlist.pop(0)
    for i in tolist[nth]:
        if roomsign[i]==INF:
            roomsign[i]=nth+1
            pathlist.append(i)

print("Yes")
print(*roomsign[1:N],sep="\n")

Solution (Python):
from collections import deque
n, m = [int(e) for e in input().split()]
AB = [[] for _ in range(n+1)]
for i in range(m):
    A,B = [int(e) for e in input().split()]
    AB[A].append(B)
    AB[B].append(A)

ans = [0]*(n+1)
visited = [0]*(n+1)
root = 1
visited[root] = 1
q = deque([root])

while q:
    v = q.popleft()
    for w in AB[v]:
        if visited[w]==0:
            ans[w]=v
            visited[w] +=1
            q.append(w)
        
print('Yes')
for i in ans[2:]:
    print(i)

Solution (Python):
from scipy.sparse.csgraph import breadth_first_tree, breadth_first_order
from scipy.sparse import csr_matrix, coo_matrix
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
A = []
B = []
for i in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
D = [1] * M
csr = coo_matrix((D, (A, B)), (N, N)).tocsr()
Tcsr = breadth_first_order(csr, 0, False, True)
ans = []
for i in Tcsr[1][1:]+1:
    if i == -9998:
        print("No")
        quit()
    ans.append(i)
print("Yes")
for i in ans:
    print(i)

Solution (Python):
import sys
from collections import deque
INF = float('inf')

input = sys.stdin.readline
n,m = map(int, input().split())
AB = [tuple(map(int,input().split())) for i in range(m)]
G = [[] for _ in range(n)]

for a, b in AB:
    a , b = a-1 , b-1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
dist = [INF]*n
dist[0] = 0
back = [-1] * n
while q:
    v = q.popleft()
    for to in G[v]:
        if dist[v] + 1 >=dist[to]:continue
        dist[to] = dist[v]
        back[to] = v+1
        q.append(to)
print('Yes')
print(*back[1:],sep='\n')

Solution (Python):
from scipy.sparse.csgraph import breadth_first_tree, breadth_first_order
from scipy.sparse import csr_matrix, coo_matrix
N, M = map(int,input().split())
A = []
B = []
for i in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
D = [1] * M
csr = coo_matrix((D, (A, B)), (N, N)).tocsr()
Tcsr = breadth_first_order(csr, 0, False, True)
ans = []
for i in Tcsr[1][1:]+1:
    if i == -9998:
        print("No")
        quit()
    ans.append(i)
print("Yes")
for i in ans:
    print(i)

Solution (Python):
from collections import deque, defaultdict

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

for _ in range(m):
    a,b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
    
q=deque()
q.append(1)
ans={}
while q:
    node=q.popleft()
    for i in d[node]:
        
        if i in ans:
            continue
        q.append(i)
        ans[i]=node
print('Yes')
for k in sorted(ans):
    if k==1:
        continue
    print(ans[k])

Solution (Python):
from collections import deque

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

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

dict = { i:[] for i in range(1,N+1)}

for i in range(M):
  a = List[i][0]
  b = List[i][1]
  
  dict[a].append(b)
  dict[b].append(a)


kouho = deque([1])
sumi = [-1 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi.append(a)

  for t in dict[a]:
    if sumi[t] != -1:
      continue
    else:
      kouho.append(t)
      sumi[t] = a
          
ck = 0

for i in range(2,N+1):
  if sumi[i] == -1:
    ck=1
    
if ck == 1:
  print("No")
else:
  print("Yes")
  
  for i in range(2,N+1):
    print(sumi[i])

Solution (Python):
from  collections  import deque

N, M = map(int, input().split())
AB = [[] for _ in range(N+1)]

for _ in range(M):
  A, B = map(int, input().split())
  AB[A].append(B)
  AB[B].append(A)

ans = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])

while q:
  v = q.popleft()
  for w in AB[v]:
    if visited[w]:
      continue
    visited[w] = 1
    ans[w] = v
    q.append(w)
    
print('Yes')
for i in ans[2:]:
  print(i)

Solution (Python):
def main():
    from sys import stdin
    from collections import deque
    n,m = map(int,stdin.readline().rstrip().split())       
    AB=[]
    for _ in range(m):
        AB.append(list(map(int,stdin.readline().rstrip().split())))
    
    G = [[] for _ in range(n+1)]
    for a,b in AB:
        G[a].append(b)
        G[b].append(a)

    visit = [False]*(n+1)
    visit[0]=True
    path = [-1]*(n+1)

    dq = deque([1])

    while len(dq)>0:
        edge = dq.popleft()

        for i in G[edge]:
            if not visit[i]:
                visit[i] = True
                path[i] = edge
                dq.append(i)
        
    print("Yes")
    for i in path[2:]:
        print(i)
main()

Solution (Python):
import numpy as np
import itertools
from collections import deque

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

class Room:
  def __init__(self, num):
    self.num = num
    self.roots = []
    self.kyori = -1
    self.near = 0
    
  def add_root(self, to):
    self.roots.append(to)
  def set_kyori(self, num, kyori):
    self.kyori = kyori
    self.near = num

r_list = sorted(np.unique(np.array(list(itertools.chain.from_iterable(root)))))
rooms = {i:Room(i) for i in r_list}

for r in root:
  a, b = rooms[r[0]], rooms[r[1]]
  a.add_root(b)
  b.add_root(a)

kyori = 0
near = 0
rooms[1].set_kyori(near, kyori)
rooms[1].near = near
q = deque()
q.append(rooms[1])
while len(q) > 0:
  node = q.popleft()
  kyori+=1
  for r in node.roots:
    if r.kyori != -1:
      continue
    r.set_kyori(node.num, kyori)
    q.append(r)
  
rooms[1].set_kyori(0, 0)
for r in rooms.values():
  if r.kyori == -1:
    print('No')
    break
else:
  print('Yes')
  for r in list(rooms.values())[1:]:
    print(r.near)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)

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

sign = [-1]*n 
sign[0] = -2 
visited = [False]*n 
visited[0] = True

q = deque([0])
while len(q)>0:
	room = q.popleft()
	for nroom in nextroom[room]:
		if visited[nroom] == 0:
			visited[nroom] = 1
			sign[nroom] = room
			q.append(nroom)

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

Solution (Python):

from sys import stdin
from collections import deque


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ipt = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
    MOD = 100100100100100100

    pl = [0] * (N + 1)

    for a, b in ipt:
        if pl[a] == 0:
            pl[a] = [b]
        else:
            pl[a].append(b)
        if pl[b] == 0:
            pl[b] = [a]
        else:
            pl[b].append(a)

    que = deque([1])
    deep = [MOD] * (N + 1)
    deep[1] = 0
    deep[0] = 0
    arrow = [0] * (N + 1)
    cnt = 1

    while not not que:
        q = que.popleft()
        for i in pl[q]:
            if deep[i] != MOD:
                continue
            deep[i] = deep[q] + 1
            arrow[i] = q
            cnt += 1
            que.append(i)

    if N != cnt:
        print("No")
    else:
        print("Yes")
        for i in arrow[2:]:
            print(i)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
N,M = map(int, input().split())
AB_s = [list(map(int, input().split())) for _ in range(M)]

MAP = [[] for _ in range(N)]
for AB in AB_s:
    A, B = map(int, AB)
    MAP[A-1].append(B)
    MAP[B-1].append(A)
answer = [0] * N
queue = deque([1])
answer[0] = N
while len(queue) > 0:
    P = queue.popleft()
    if True:
        for Q in MAP[P-1]:
            if answer[Q-1] == 0:
                answer[Q-1] = P
                queue.append(Q)
if min(answer) == 0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(answer[i])

Solution (Python):
from collections import deque

n, m = map(int, input().split())
rooms = [[] for i in range(n + 1)]

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

q = deque()
q.append(1)
sign = [-1]*(n + 1)
sign[1] = 0

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if sign[i] == -1:
            sign[i] = rnum
            q.append(i)

print("Yes")

for i in sign[2:]:
    print(i)

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

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

dist = [float('inf')]*n
dist[0] = 0
pre = [0]*n
pre[0] = 1

queue = deque([0])
while queue:
  x = queue.popleft()
  for y in l[x]:
    if dist[y] == float('inf') and pre[y] == 0:
      dist[y] = dist[x] + 1
      pre[y] = x
      queue.append(y)

print('Yes')
for i in pre[1:]:
  print(i+1)

Solution (Python):
from collections import deque

def bfs(start, line):
    quene = deque([start])
    d = [None] * len(line) 
    d[start] = 0
    ans = [None] * len(line)
    while quene:
        v = quene.popleft()
        for i in line[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                ans[i] = v
                quene.append(i)
    return ans


def main():
    n,w = map(int,input().split()) 
    checker = [0]
    line = [[] for _ in range(n)]
    for i in range(w):
        x,y= map(int,input().split()) 
        x -= 1
        y -= 1
        line[x].append(y)
        line[y].append(x)
    print("Yes")
    ans = bfs(0,line)
    for i in ans[1:]:
        print(i+1)

 
 
if __name__ == '__main__':
  main()

Solution (Python):
from collections import deque
n, m = map(int, input().split())
bridge = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    bridge[a - 1].append(b - 1)
    bridge[b - 1].append(a - 1)
queue = deque([0])
ans = [[] for i in range(n)]
ans[0].append('god')
while queue:
    now = queue.popleft()
    for factor in bridge[now]:
        if not (ans[factor]):
            ans[factor].append(now)
            queue.append(factor)
print('Yes')
for i in range(1, len(ans)):
    print(ans[i][0]+1)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
N,M = [int(x) for x in input().rstrip().split()]

to = [list() for _ in range(N)]

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

sign = [0]*N
dist = [N]*N
dist[0] = 0

q = deque()
q.append(0)

while q:
    v = q.popleft()

    for x in to[v]:
        if dist[x] > dist[v]+1:
            dist[x] = dist[v]+1
            sign[x] = v+1
            q.append(x)
    
print('Yes')
for i in sign[1:]:
    print(i)

Solution (Python):
from collections import deque
N,M=map(int,input().split())


graph=[[]for _ in range(N+1)]
 
for _ 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]=V
        D.append(i)
 
print('Yes')
for j in dist[2:]:
    print(j)

Solution (Python):
from collections import deque

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

AB = [map(lambda x: int(x) - 1, input().split()) for _ in range(M)]
to_list = [[] for _ in range(N)]

for a, b in AB:
    to_list[a].append(b)
    to_list[b].append(a)

result = [-1] * N
q = deque([0])
while q:
    i = q.popleft()
    for j in to_list[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i + 1) for i in result[1:]))

Solution (Python):



from math import *
from copy import *					
from heapq import *					
from string import *				
from random import *				
from bisect import *				
from sys import stdin				
from sys import maxsize				
from operator import *				
from itertools import *				
from collections import Counter		
from collections import defaultdict 

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

def solve(adj):
	n = len(adj)
	dis = [maxsize]*n
	ans = [0]*n
	q = [0]
	dis[0] = 0
	while(q):
		src = q.pop(0)
		for nn in adj[src]:
			if(dis[nn] == maxsize):
				ans[nn] = src
				dis[nn] = dis[src] + 1
				q.append(nn)
	for i in range(n):
		ans[i] += 1
	if(maxsize in dis[1:]):
		print('No')
	else:
		print('Yes')
		for i in range(1,n):
			print(ans[i])

N,M = list(map(int, stdin.readline().rstrip().split()))
adj = [[] for i in range(N)]
for _ in range(M):
	a,b = list(map(int, stdin.readline().rstrip().split()))
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
solve(adj)

Solution (Python):
from queue import Queue

inp = input
out = print

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

adj = {i:[] for i in range(1, n+1)}

for i in range(m):
    u,v = map(int, inp().split())
    adj[u].append(v)
    adj[v].append(u)

seen = [False for _ in range(n+1)]
par = [0 for _ in range(n+1)]
q = Queue()
q.put(1)
seen[0] = seen[1] = True

while not q.empty():
    u = q.get()
    
    for v in adj[u]:
        if not seen[v]:
            q.put(v)
            seen[v] = True
            par[v] = u

if sum(seen) != n+1:
    out('No')

else:
    out('Yes')
    for i in range(2, n+1):
        out(par[i])

Solution (Python):
import sys

max_int = 1000000001  
min_int = -max_int

n, m = map(int, sys.stdin.readline().split())
G = {}
for _m in range(m):
    a, b = map(int, sys.stdin.readline().split())
    if a not in G:
        G[a] = [[b], -1]
    else:
        G[a][0].append(b)

    if b not in G:
        G[b] = [[a], -1]
    else:
        G[b][0].append(a)

pretends = [1]
L = -1
while pretends:
    L += 1
    new_pretends = []
    for pretend in pretends:
        if G[pretend][1] != -1:
            continue
        G[pretend][1] = L
        for neighbor in G[pretend][0]:
            new_pretends.append(neighbor)
    pretends = new_pretends

for vertex in G:
    if G[vertex][1] == -1:
        print('No')
        exit()

print('Yes')

for i in range(2, n + 1):
    for neighbor in G[i][0]:
        if G[neighbor][1] == G[i][1] - 1:
            print(neighbor)
            break

Solution (Python):
import heapq





















def raw_input():
    return input()


rooms_count, passages_count = map(int, raw_input().split())
adj = []
for i in range(0, rooms_count):
    adj.append([])

for j in range(0, passages_count):
    a, b = map(int, raw_input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

seen = set()
distance = [100000000] * rooms_count
next = [100000000] * rooms_count
h = []
heapq.heappush(h, (0, 0, -1))
while len(h):
    (d, room, parent) = heapq.heappop(h)
    if (distance[room] <= d):
        continue
    distance[room] = d
    next[room] = parent
    seen.add(room)

    for neighbor in adj[room]:
        heapq.heappush(h, (d + 1, neighbor, room))

if len(seen) == rooms_count:
    print('Yes')
    for room in range(1, rooms_count):
        print(next[room] + 1)
else:
    print('No')

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

next_node = [[] for _ in range(n)]
for a, b in edge:
    next_node[a-1].append(b)
    next_node[b-1].append(a)

q = [1]
visit = [1]  + [0] * (n-1)
prev = [0] * n
while q:
    now = q.pop(0)
    for i in next_node[now-1]:
        if visit[i-1] == 0:
            q.append(i)
            visit[i-1] = 1
            prev[i-1] = now
print('Yes')
print(*prev[1:], sep='\n')

Solution (Python):
import queue
import math
q = queue.Queue()
A = []
B = []
N,M = map(int,input().split())
check = [-1]*N
graph = [[] for i in range(N+1)]
flag = [0]*N
for i in range(M):
	lines = list(map(int,input().split()))
	A.append(lines[0])
	B.append(lines[1])
	graph[lines[0]].append(lines[1])
	graph[lines[1]].append(lines[0])

q.put(1)
check[0] = 0
while not q.empty():
	p = q.get()
	for np in graph[p]:
		if check[np-1] == -1:
			check[np-1] = check[p-1] + 1
			q.put(np)

for i in range(M):
	if check[A[i]-1] - check[B[i]-1] == 1:
		flag[A[i]-1] = B[i]
	if check[B[i]-1] - check[A[i]-1] == 1:
		flag[B[i]-1] = A[i]

print('Yes')
for i in range(1,N):
	print(flag[i])

Solution (Python):
N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
prev = [0] * N
to_list = [ [] for _ in range(N)]
for a,b in AB:
 to_list[a - 1].append(b - 1)
 to_list[b - 1].append(a - 1)
marked = {0}
que = [0]
for i in que:
   for j in to_list[i]:
       if j in marked: continue
       que.append(j)
       marked.add(j)
       prev[j] = i+1
print('Yes')
print(*prev[1:], sep='\n')

Solution (Python):
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue



ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    AB = {m + 1: [] for m in range(M+1)}
    for _ in range(M):
        a, b = il()
        AB[a].append(b)
        AB[b].append(a)

    visit = [0] * (N + 1)
    fifoqu = queue.Queue()
    fifoqu.put(1)

    while not fifoqu.empty():
        now = fifoqu.get()
        next = AB[now]
        for n in next:
            if visit[n] != 0:
                continue
            visit[n] = visit[now] + 1
            fifoqu.put(n)
    else:
        if visit[1] == 0:
            print('No')
            exit()
        else:
            visit[1] = 0
            print('Yes')
            for n in range(2, N + 1):
                deep = visit[n]
                rooms = AB[n]
                for room in rooms:
                    if visit[room] == deep - 1:
                        print(room)
                        break


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue



ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    AB = {m + 1: [] for m in range(M+1)}
    for _ in range(M):
        a, b = il()
        AB[a].append(b)
        AB[b].append(a)

    ret = []
    visit = [0] * (N + 1)
    fifoqu = queue.Queue()
    fifoqu.put(1)

    while not fifoqu.empty():
        now = fifoqu.get()
        next = AB[now]
        for n in next:
            if visit[n] != 0:
                continue
            visit[n] = visit[now] + 1
            fifoqu.put(n)
    else:
        if visit[1] == 0:
            print('No')
            exit()
        else:
            visit[1] = 0
            print('Yes')
            for n in range(2, N + 1):
                deep = visit[n]
                rooms = AB[n]
                for room in rooms:
                    if visit[room] == deep - 1:
                        print(room)
                        break


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


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

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


link = [[] for _ in range(N + 1)]
for a, b in AB:
  link[a].append(b)
  link[b].append(a)


dist = [-1] * (N + 1)  
que = deque([1])       


while que:
    v = que.popleft() 

    for i in link[v]:
      
      if dist[i] == -1:
        dist[i] = v
        que.append(i)


print('Yes')
print('\n'.join(str(v) for v in dist[2:]))

Solution (Python):
import sys
import copy
from io import StringIO
import unittest
from collections import deque



def resolve():
    n, m = map(int, input().split())
    ms = [list(map(int, input().split())) for i in range(m)]

    
    roots = [[] for i in range(n + 1)]
    for i in ms:
        roots[i[0]].append(i[1])
        roots[i[1]].append(i[0])

    
    deeps = [99999 for i in range(n + 1)]
    aaa = [False for i in range(n + 1)]

    best_signs = [0 for i in range(n+1)]

    
    

    
    que = deque()
    que.append(1)  
    deeps[1] = 0  

    
    while not len(que) is 0:

        now = que.popleft()

        
        

        
        for target in roots[now]:
            
            if aaa[target] is True:
                continue

            
            deeps[target] = deeps[now] + 1
            que.append(target)
            aaa[target] = True
            
            best_signs[target] = now

    
    

    
    print("Yes")
    for i in range(2, len(best_signs)):
        
        print(best_signs[i])

    


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 4
1 2
2 3
3 4
4 2"""
        output = """Yes
1
2
2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6"""
        output = """Yes
6
5
5
1
1"""
        self.assertIO(input, output)


if __name__ == "__main__":
    
    resolve()

Solution (Python):

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



links=[[] for _ in range(N+1)]



for a,b in AB:

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

from collections import deque
result=[-1]*(N+1)



q=deque([1])

while len(q)>0:
    i=q.popleft()
    for j in links[i]:
        if result[j] ==-1:
            result[j] = i
            
            q.append(j)
print("Yes")
print("\n".join(str(i) for i in result[2:] ))

Solution (Python):
from collections import deque

room_num, path_num = map(int, input().split(" "))
graph = [[] for _ in range(room_num)]
dis = [-1] * room_num
for _ in range(path_num):
    a, b = map(int, input().split(" "))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
dis[0] = 0
q = deque()
q.append(0)
while q:
    pop = q.popleft()
    for n in graph[pop]:
        if dis[n] > 0:
            pass
        else:
            dis[n] = pop+1
            q.append(n)
if -1 in dis:
    print("No")
else:
    del dis[0]
    print("Yes")
    for s in dis:
        print(s)

Solution (Python):

from collections import deque

room_num, path_num = map(int, input().split(" "))
graph = [[] for _ in range(room_num)]
dis = [-1] * room_num
count = [0] * room_num
count[0] = 1
for _ in range(path_num):
    a, b = map(int, input().split(" "))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
dis[0] = 0
q = deque()
q.append(0)
while q:
    pop = q.popleft()
    for n in graph[pop]:
        if count[n] ==1:
            continue
        else:
            count[n] = 1
            dis[n] = pop+1
            q.append(n)
if sum(dis) == room_num:
    print("No")
else:
    del dis[0]
    print("Yes")
    for s in dis:
        print(s)

Solution (Python):
from collections import deque 

N,M = map(int, input().split())
root = [[] for _ in range(N)]

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

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

while len(q) > 0:
	v = q.popleft()
	for ike in root[v - 1]:
		q.append(ike)
		if(ans[ike - 1] == 0):
			ans[ike - 1] = v

	root[v-1].clear()

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

Solution (Python):
from collections import deque 

N,M = map(int, input().split())
root = [[] for _ in range(N)]

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

q = deque()
q.append(1)
ans = [0 for _ in range(N)]

while len(q) > 0:
	v = q.popleft()
	for ike in root[v - 1]:
		q.append(ike)
		if(ans[ike - 1] == 0):
			ans[ike - 1] = v

	root[v-1].clear()

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

Solution (Python):
import queue
import math
def dijkstra(i,n,adj):
  pq=queue.PriorityQueue()
  dist=[float("inf") for i in range(n+1)]
  parent=[0]*(n+1)
  dist[i]=0
  pq.put((dist[i],i))
  while(not pq.empty()):
    (x,y)=pq.get()
    for e in adj[y]:
      if dist[y]+1 < dist[e]:
        dist[e]=dist[y]+1
        parent[e]=y
        pq.put((dist[e],e))
  if float('inf') in dist[1:]:
      print('No')
  else:
      print('Yes')
  for p in parent[2:]:
      print(p)

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

dijkstra(1,n,adj)

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)

next_r = [float('inf')]*(n+1) 
next_r[0] = 0
next_r[1] = 0
seen = [0]*(n+1) 



seen[1] = 1
q = deque()
q.append(1)
while q:
    pos = q.popleft()    
    for next_v in g[pos]:
        if seen[next_v] == 1: continue
    
        seen[next_v] = 1
        next_r[next_v] = pos
        q.append(next_v)

if sum(next_r) == float('inf'):
    print('No')
else:
    print('Yes')
    for i in range(2,n+1):
        print(next_r[i])

Solution (Python):
import networkx as nx
N,M = map(int, input().split())
E = [list(map(int,input().split())) for i in range(M)]

G = nx.Graph() 
G.add_edges_from(E)
di = nx.predecessor(G, source = 1)

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

Solution (Python):
import queue

mod = 998244353
INF = 1<<29
lINF = 1<<35

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


graph = [[] for _ in range(n)]
for i in range(m):
    x,y = list(map(int,input().split()))
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

v = [-1 for _ in range(n)]

v[0] = [0]

q = queue.Queue()
q.put(0)
while not q.empty():
    
    x = q.get()
    
    for y in graph[x]:
        if v[y] != (-1):
            continue
        q.put(y)
        v[y] = x
print('Yes')
for i in range(1,n):
    print(v[i]+1)

Solution (Python):
from collections import deque

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

links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Solution (Python):
from collections import deque
n,m = map(int,input().split())
edge_list = [[] for i in range(n)]
depth_list = [-1 for i in range(n)]
ans_list = [-1 for i in range(n)]
depth_list[0] = 0
ans_list[0] = 0
for m in range(m):
  a,b = map(int,input().split())
  a = a-1
  b = b-1
  edge_list[a].append(b)
  edge_list[b].append(a)
q = deque()
q.append(0)

while len(q) > 0:
  node = q.popleft()
  connects = edge_list[node]
  for c in connects:
    if depth_list[c] == -1:
      depth_list[c] = depth_list[node] + 1
      q.append(c)
      ans_list[c] = node
      
if -1 in ans_list:
  print("No")
else:
  print("Yes")
  for _ in ans_list[1:]:
    print(_ + 1)