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())
G = [[] for _ in range(n)]
for i in range(m):
    a, b = map(lambda x: x-1, map(int, input().split()))
    G[a].append(b)
    G[b].append(a)

q = deque([0])
visited = [None]+[-1]*(n-1)
while q:
    nx = q.pop()
    for g in G[nx]:
        if visited[g] != -1:
            continue
        visited[g] = nx
        q.appendleft(g)

print('Yes')
print(*[visit+1 for visit in visited[1:]], sep='\n')

Solution (Python):
from collections import deque

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

g = tuple(set() for _ in range(N))
for _ in range(M):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add(b)
    g[b].add(a)

print('Yes')

ret = [-1] * N
ret[0] = 0

dq = deque()
dq.append(0)

while dq:
    v = dq.popleft()
    for u in g[v]:
        if ~ret[u]: continue
        ret[u] = v
        dq.append(u)

print(*(x + 1 for x in ret[1:]), sep='\n')

Solution (Python):

from collections import deque

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

for _ in range(M):
  a, b = map(int, input().split())
  route[a].append(b)
  route[b].append(a)
  
q = deque([1]) 
pre = [None] * (N+1) 
pre[1] = 0 
depth = [None] * (N+1) 
depth[1] = 0 
while len(q) > 0:
  x = q.popleft()
  for r in route[x]:
    if pre[r] is None:
      depth[r] = depth[x] + 1
      pre[r] = x
      q.append(r)

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(n+1)]

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


dist=[-1 for i in range(n+1)]
prev=[-1 for i in range(n+1)]
q=deque([1])
dist[1]=0

while len(q)!=0:
    v=q.popleft()
    for nv in G[v]:
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+1
        prev[nv]=v
        q.append(nv)
print('Yes')
for i in range(2,n+1):
    print(prev[i])

Solution (Python):
from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(n+1)]

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


dist=[-1 for i in range(n+1)]
prev=[-1 for i in range(n+1)]
q=deque([1])
dist[1]=0

while len(q)!=0:
    v=q.popleft()
    for nv in G[v]:
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+1
        prev[nv]=v
        q.append(nv)
print('Yes')
for i in range(2,n+1):
    print(prev[i])

Solution (Python):
N, M = map(int, input().split())
routes = [[] for i in range(N-1)]
ans = [0]*(N-1)
li = []
for i in range(M):
  r = list(map(int, input().split()))
  if r[0] == 1:
    li.append(r[1])
    ans[r[1]-2] = 1
  elif r[1] == 1:
    li.append(r[0])
    ans[r[0]-2] = 1
  else:
    routes[r[0]-2].append(r[1])
    routes[r[1]-2].append(r[0])
    
flag = True
while 0 in ans:
  tmp = []
  if li == []:
    flag = False
    break
  for num in li:
    for route in routes[num-2]:
      if ans[route-2] == 0:
        ans[route-2] = num
        tmp.append(route)
  li = tmp
  
if flag:
  print('Yes')
  for i in range(N-1):
    print(ans[i])
else:
  print('No')

Solution (Python):
from collections import deque

mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n, m = map(int,raw_input().split())
    
    adj_list = [[] for _ in range(n+5)]
    
    q = deque()
    
    ans = [-1] * (n+5)
    
    failed = False
    
    for _ in range(m):
        a, b = map(int,raw_input().split())    
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    q.append(1)
    
    
    
    visited = set()
    
    visited.add(1)
    
    while len(q):
        sz = len(q)
        for _ in range(sz):
            cur = q.popleft()
            for nei in adj_list[cur]:
                if nei not in visited:
                    ans[nei] = cur
                    q.append(nei)
                    visited.add(nei)
    
    
    print('Yes')
    for i in range(2, n+1):
        print(ans[i])
            
            
        
        
    
    

main()

Solution (Python):
def mi(): return map(int,input().split())
def lmi(): return list(map(int,input().split()))
def ii(): return int(input())
def isp(): return input().split()
from collections import deque
n,m=mi()
adjacent_list=[[] for i in range(n+1)]
for i in range(m):
  a,b=mi()
  adjacent_list[a].append(b)
  adjacent_list[b].append(a)


dp=[0]*(n+1)

que=deque()
que.append(1)
while que:
  p=que.popleft()
  for i in adjacent_list[p]:
    if dp[i]==0:
      dp[i]=p
      que.append(i)
      
print('Yes')
for i in range(2,n+1):
  print(dp[i])

Solution (Python):
from collections import deque

N,M = (int(a) for a in input().split())
g = [[] for _ in range(N)]
s = [0]*N
for i in range(M) :
    A,B = (int(a) for a in input().split())
    g[A-1].append(B)
    g[B-1].append(A)
visited = {0}
stack = [0]
for i in stack :
    for j in g[i] :
        if j-1 in visited :
            continue
        stack.append(j-1)
        visited.add(j-1)
        s[j-1] = i + 1
if s.count(0) > 1 :
    print("No")
else :
    print("Yes")
    print(*s[1:])

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

(n, m), g = map(int, input().split()), defaultdict(list)
for i in range(m): a, b = map(int, input().split()); g[a].append(b); g[b].append(a)
s, q = [0, 0] + [-1 for i in range(1, n)], deque([1])
for i in range(2, n + 1):
    x = q.popleft()
    for a in g[x]:
        if s[a] == -1: q.append(a); s[a] = x
if not all([a != -1 for a in s]): print('No')
else:
    print('Yes')
    for i in s[2:]: print(i)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

n, m = l()
g = [[] for i in range(n)]
for i in range(m):
    a, b = l()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([0])
d = [-1] * n
d[0] = 0
while q:
    v = q.popleft()
    for w in g[v]:
        if d[w] != -1:
            continue
        d[w] = v
        q.append(w)
if -1 in d:
    print("No")
else:
    print("Yes")
    for di in d[1:]:
        print(di+1)

Solution (Python):


import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    g = [[] for i in range(n)]
    for i in range(m):
        a, b = na()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    q = deque([0])
    d = [-1] * n
    d[0] = 0
    while q:
        v = q.popleft()
        for w in g[v]:
            if d[w] != -1:
                continue
            d[w] = v
            q.append(w)
    if -1 in d:
        print("No")
    else:
        print("Yes")
        for di in d[1:]:
            print(di+1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for n in graph[current]:
            if dist[n] != -1:
                continue
            else:
                dist[n] = dist[current] + 1
                prev[n] = current
                queue.append(n)

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

bfs(graph, queue, dist, prev)

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

Solution (Python):
import sys



import heapq


from collections import deque

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

    point = [0] *(n+1) 
    d = deque([1])

    while len(d) > 0:
        p = d.popleft()
        for v in room[p]:
            if point[v] ==0:
                d.append(v)
                point[v] =p

    if 0 in point[1:]:
        print('No')
    else:
        print("Yes")
        print("\n".join(map(str,point[2:])))












if __name__ == "__main__":
    main()

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

dist = [float('inf')]*(N)
ans = [0]*N
dist[0] = 0
q = deque([])
q.append((0,0))
while q:
    idx,d = q.popleft()
    for nxt in g[idx]:
        if d + 1 < dist[nxt]:
            ans[nxt] = idx+1
            dist[nxt] = d+1
            q.append((nxt,d+1))
for i in range(N):
    if dist[i]==float('inf'):
        print('No');exit()
print('Yes')
for i in range(1,N):
    print(ans[i])

Solution (Python):
from collections import deque
q=deque()
def MI(): return map(int, input().split())
N,M=MI()
g=[[] for _ in range(N+1)]
for _ in range(M):
  a,b=MI()
  g[a].append(b)
  g[b].append(a)
check=[0]*(N+1)
check[1]=1
ans=[0]*(N+1)
q.append(1)
while len(q)>0:
  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 collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
  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):

from collections import deque

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


edge_dic = {}



visited = [1] + [0]*N


guidepost = [0]*2 + [None]*(N-1)


for a,b in AB_list:
    edge_dic.setdefault(a, [])
    edge_dic[a].append(b)
    
    edge_dic.setdefault(b, [])
    edge_dic[b].append(a)


queue = deque([1])
visited[1] = 1

while queue:
    current = queue.popleft()
    
    for next_room in edge_dic[current]:
        if visited[next_room] == 0:
            guidepost[next_room] = current
            visited[next_room] = 1
            queue.append(next_room)


if (visited.count(0) == 0) and (guidepost.count(None) == 0):
    print("Yes")
    
    for num in guidepost[2:]:
        print(num)
    
else:
    print("No")

Solution (Python):
from collections import deque

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

point = [0 for i in range(n)]
d = deque([0])

while len(d) > 0:
    p = d.popleft()
    for v in room[p]:
        if point[v-1] == 0:
            d.append(v-1)
            point[v-1] = p+1

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

Solution (Python):


from collections import deque

def resolve():
    N,M, *AB = map(int, open(0).read().split())
    graph = [[] for _ in range(N+1)]
    for a,b in zip(*[iter(AB)] * 2):
        graph[a].append(b)
        graph[b].append(a)

    queue = deque([1])
    signposts = [0] * (N+1)
    signposts[1] = 1
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not signposts[v]:
                signposts[v] = u
                queue.append(v)

    if all(signposts[2:]):
        print("Yes")
        print("\n".join(map(str,signposts[2:])))
    else:
        print("No")
resolve()

Solution (Python):
import sys, math

input = sys.stdin.readline

N, M = map(int, input().split())
path = [set() for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1].add(b-1)
    path[b-1].add(a-1)

cost = [[math.inf, -1]]*N
cost[0] = [0, 0]
pre = [0]

for d in range(N):
    next = []
    for i in pre:
        for j in path[i]:
            if cost[j][0] != math.inf:
                continue
            cost[j] = [d, i]
            next.append(j)
    pre = next
    if len(next)==0:
        break

if max(cost)[0] == math.inf:
    print('No')
    sys.exit()

print('Yes')
for d, pre_idx in cost[1:]:
    print(pre_idx+1)

Solution (Python):
import sys, heapq, math

input = sys.stdin.readline

N, M = map(int, input().split())
path = [set() for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1].add(b-1)
    path[b-1].add(a-1)

h = [(0, 0, 0)] 
heapq.heapify(h)
cost = [[math.inf, -1]]*N

while len(h) != 0:
    d, idx, pre_idx = heapq.heappop(h)
    if cost[idx][0] <= d:
        continue
    cost[idx] = [d, pre_idx]
    for next_idx in path[idx]:
        if cost[next_idx] == math.inf:
            continue
        heapq.heappush(h, (d+1, next_idx, idx))

if max(cost)[0] == math.inf:
    print('No')
    sys.exit()

print('Yes')
for d, pre_idx in cost[1:]:
    print(pre_idx+1)

Solution (Python):
n, m = map(int, input().split())
route = [[] for _ in range(n+1)]
ans = [0]*n

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

q = [1]
l = set()

while True:
    if len(q) == 0:
        break
    p = q.pop(0)
    for i in route[p]:
        if i not in l:
            l.add(i)
            ans[i-1] = p
            q.append(i)

if ans.count(0) > 1:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(ans[i])

Solution (Python):
n,m=map(int,input().split())
l=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
queue=[0]
visit=[0]*n
visit[0]=1
ans=[0]*n

while len(queue)>0: 
  now=queue.pop(0)
  for p in l[now]:
    if visit[p]==0:
      visit[p]+=1
      queue.append(p)
      ans[p]=now+1
k=ans[1:]
if not all(kk!=0 for kk in k):
  print('No')
  exit()
print('Yes')
for kk in k:
  print(kk)

Solution (Python):
n,m = map(int, input().split())
root = {}

for i in range(m):
    c,d = map(int, input().split())
    if c not in root:
        root[c] = []
    if d not in root:
        root[d] = []
    root[c].append(d)
    root[d].append(c)
sirusi = [0] *(n+1)
dp = [2*m] * (n+1)
dp[1]=0
before = [1]
while True:
    tmp=[]
    flag=0
    for b in before:
        for r in root[b]:
            if dp[r] > dp[b] +1:
                dp[r] = dp[b] +1
                sirusi[r] = b
                flag += 1
                tmp.append(r)
    before = tmp
    if flag == 0:
        break

if sirusi.count(0)>2:
    print("No")
    exit()

print("Yes")
for i in range(2,n+1):
    print(sirusi[i])

Solution (Python):
from heapq import heapify,heappush,heappop
N, M = map(int, input().split())

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

task = [] 
used = [0 for _ in range(N)]
min_len = [0 for _ in range(N)]
length = [10**20 for _ in range(N)]
prev_points = [0 for _ in range(N)]
heappush(task, (0, 0, -1))
print("Yes")

while task:
  while task:
    l, p, prev = heappop(task)    
    if used[p] == 0:
      break
  
  used[p] = 1
  min_len[p] = l
  prev_points[p] = prev +1 
  
  for j in I[p]:
    if used[j] == 1: continue
    
    if length[j] > l+1:
      length[j] = l+1
      heappush(task, (l+1, j, p))
    
for i in range(1, N):
  print(prev_points[i])

Solution (Python):
N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
start = 0
queue = [start]
pre = [None]*N
pre[0] = 0
while queue:
    v = queue.pop(0)
    for i in adj[v]:
        if pre[i] is None:
            pre[i] = v
            queue.append(i)
if None in pre:
    print("No")
else:
    print("Yes")
    for p in pre[1:]:
        print(p+1)

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)

ans = [0]*(n-1)

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if ans[i-2] != 0 or i == 1:
            continue
        ans[i-2] = v
        d.append(i)
        
print('Yes')
print(*ans, sep='\n')

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

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

	d = deque()
	d.append(1)

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

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


if __name__ == '__main__':
	main()

Solution (Python):
from collections import deque

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

graph = [[] for _ in range(n+1)]

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








ans = [0] * (n-1)

d = deque()
d.append(1)


while d:
 v = d.popleft()
 for i in graph[v]:
   if ans[i-2] != 0 or i == 1:
     continue
   ans[i-2] = v
   d.append(i)

print("Yes")
print(*ans, sep="\n")

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

q = [1]
visited = [-1] * (n + 1)

visited[1] = 0
while q:
    node = q.pop(0)
    for i in path[node]:
        if visited[i] == -1:
            q.append(i)
            visited[i] = node

if any([True for v in visited[2:] if v == -1]):
    print("No")
else:
    print("Yes")
    for v in visited[2:]:
        print(v)

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

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

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

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

const_vary=list()


while True:
  const_vary=const
  const=[]
  
  while len(const_vary):
    get=const_vary.pop()
    
    for n in list_tonari[get]:
      if ans[n] ==0:
        ans[n]=get
        list_tonari[n].remove(get)
        const.append(n)
        
  if len(const)==0:
    break
    
print("Yes")
for n in ans[2:]:
  print(n)

Solution (Python):
from collections import deque

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

way = {}
for i in range(m):
    a, b = map(int, input().split())
    if a not in way:
        way[a] = []
    if b not in way:
        way[b] = []
    way[a].append(b)
    way[b].append(a)

queue = deque([1])
ok = set([1])
ans = [0] * (n+1)

while queue:
    now = queue.popleft()
    for i in way[now]:
        if i in ok:
            continue
        ans[i] = now
        queue.append(i)
        ok.add(i)

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque





def solve():
    N, M = MI()
    E = [[] for _ in range(N)]
    for i in range(M):
        a, b = MI1()
        E[a].append(b)
        E[b].append(a)
    q = deque([0])
    used = [0] * N
    used[0] = 1
    ans = [0] * N
    ans[0] = 'Yes'
    while q:
        v = q.popleft()
        for nv in E[v]:
            if used[nv]: continue
            used[nv] = 1
            ans[nv] = v+1
            q.append(nv)
    printlist(ans, '\n')


if __name__ == '__main__':
    solve()

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


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N, M = na()
node_dic = {}
for _ in range(M):
    A, B = na()
    if B in node_dic:
        node_dic[B].append(A)
    else:
        node_dic[B] = [A]
    if A in node_dic:
        node_dic[A].append(B)
    else:
        node_dic[A] = [B]


edge = deque()
edge.append(1)
d = [-1] * N
d[0] = 0
while len(edge):
    e = edge.popleft()
    for ee in node_dic[e]:
        if d[ee - 1] == -1:
            d[ee - 1] = e
            edge.append(ee)
if -1 in d:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, d[1:])))

Solution (Python):
from collections import deque

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

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

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


while q:
    v = q.popleft()

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

print("Yes")


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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
lndmrk=[-1]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    e[a].append(b)
    e[b].append(a)
q=deque()
lndmrk[1]=0
q.append(1)
while(len(q) !=0):
    v=q.popleft()
    for i in e[v]:
        if lndmrk[i]==-1:
            lndmrk[i]=v
            q.append(i)
f=True
for i in range(2,n+1):
    if lndmrk[i]==-1:
        f=False
        break
if f:
    print('Yes')
    for i in range(2,n+1):
        print(lndmrk[i])
else:
    print('No')

Solution (Python):
import collections

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

route = {}

for i in range(M):
    A, B = map(int, input().split())

    if not A in route:
        route[A] = [B]
    else:
        route[A].append(B)

    if not B in route:
        route[B] = [A]
    else:
        route[B].append(A)

check = {
    1: 0,
}

queue = collections.deque()
queue.append(1)
result = {}

while queue:
    value = queue.popleft()
    for i in route[value]:
        if not i in check:
            queue.append(i)
            check[i] = check[value] + 1
            result[i] = value

if len(result) == N-1:
    print('Yes')
    for i in range(2, N+1):
        print(result[i])
else:
    print('No')

Solution (Python):
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2, cos, pi
from fractions import Fraction

n, m = map(int, stdin.readline().split())
g = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    g[a].append(b)
    g[b].append(a)

signposts = [0]*(n+1)

queue = dq([1])

visited = [0]*(n+1)
visited[1] = 1
while queue:
    parent = queue.popleft()
    for children in g[parent]:
        if not visited[children]:
            
            signposts[children] = parent
            queue.append(children)
            visited[children] = 1

if 0 in signposts[2:]:
    print('No')
else:
    print('Yes')
    print(*signposts[2:], sep='\n')

Solution (Python):
import sys
from collections import defaultdict, deque

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




X = [n + 1] * (n + 1)
Y = [0] * (n + 1)
d = defaultdict(set)
for a, b in L:
    d[a].add(b)
    d[b].add(a)


X0 = X[0]
X[1] = 0
qu = deque([1])
while qu:
  i = qu.popleft()
  cost = X[i]
  for b in d[i]:
    if X[b] == X0:
      X[b] = cost + 1
      qu.append(b)


s = X[0]
try:
    X.index(X[0], 1)
except ValueError:
    print('Yes')
    
    
    for i in range(2, n + 1):
      c = X[i]
      for v in d[i]:
        
        if c - 1 == X[v]:
          Y[i] = v
          break
    for v in Y[2:]:
        print(v)
else:
    print('No')

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

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

Solution (Python):
from collections import deque

N,M = map(int,input().split())
grap = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    grap[a].append(b)
    grap[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 grap[v]:
        if dist[i] != -1:
            continue
        dist[i] = v
        d.append(i)

if -1 in dist:
    print('No')
else:
    print('Yes',*dist[2:],sep='\n')

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


for path in P:
    A[path[1]-1].append(path[0]-1)
    A[path[0]-1].append(path[1]-1)


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

que = deque([0])

while len(que) != 0:
    v = que.popleft()
    for v_i in A[v]:
        if previous[v_i] != -1:
            continue
        else:
            que.append(v_i)
            previous[v_i] = v
for i in range(N):
    if previous[i] == -1:
        print('No')
        exit()
print('Yes')
for i in range(1,N):
    print(previous[i]+1)

Solution (Python):
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())

connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect_dic.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

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

Solution (Python):
from collections import deque

def bfs(s=0):
    que = deque([s])
    visited = [False] * N
    visited[s] = True
    while que:
        v = que.popleft()
        for u in E[v]:
            if not visited[u]:
                par[u] = v
                visited[u] = True
                que.append(u)

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)
par = [-1] * N
bfs()
cnt = len([i for i in par if i == -1])
if cnt > 1:
    print('No')
else:
    print('Yes')
    for p in par[1:]:
        print(p+1)

Solution (Python):
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




from collections import deque

def main():
	n,m=MI()

	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	ans=[0]*(n+1)

	Q=deque([1])
	sumi=set()

	while Q:
		now=Q.popleft()

		for next in G[now]:
			if next in sumi:
				continue
			else:
				Q.append(next)
				ans[next]=now
				sumi.add(next)

	print("Yes")

	print(*ans[2:],sep="\n")






































if __name__ == "__main__":
	main()