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

    ans=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    d=deque([1])
    while len(d)>0:
        now=d.popleft()
        v=now
        for u in G[v]:
            if flags[u]==False:
                flags[u]=True
                ans[u]=v
                d.append(u)

    print("Yes")
    for i in range(2,n+1):
        print(ans[i])
        
if __name__=="__main__":
    main()

Solution (Python):
import sys
import os
from collections import deque

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    N,M=map(int, input().split())
    r={}
    for i in range(M):
        A,B=map(int, input().split())
        
        if A not in r:
            r[A]=[B]
        else:
            r[A].append(B)
        if B not in r:
            r[B]=[A]
        else:
            r[B].append(A)
        
    

    q=deque()
    q.append(1)
    visited=set()
    visited.add(1)
    out=[0]*(N-1)
    while len(q)>0:
        
        position=q.popleft()
        
        for des in r[position]: 
            if des not in visited:  
                q.append(des)   
                visited.add(des)   
                out[des-2]=position
                
    



    print('Yes')
    [print(x) for x in out]

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = deque()
q.append(1)
while q:
    p = q.popleft()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.append(c)
print('Yes')
for i in range(2,n+1): print(ans[i])

Solution (Python):
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for a, b in AB:
    graph[a - 1].append(b)
    graph[b - 1].append(a)
    
queue = deque()
visited = [0] * N
sign_list = [0] * N 

queue.append(1)
visited[0] = 1

while queue:
    room = queue.popleft()
    next_rooms = graph[room - 1]
    for r in next_rooms:
        if visited[r - 1] == 0:
            queue.append(r)
            sign_list[r - 1] = room
            visited[r - 1] = 1

yes = True
for s in sign_list[1:]:
    if s == 0:
        yes = False

if yes:
    print("Yes")
    for s in sign_list[1:]:
        print(s)
else:
    print("No")

Solution (Python):
from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n)]
ans = [0] * n
for _ in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)


q = deque([0])
visited = [False] * n
visited[0] = True

while q:
    now = q.popleft()
    
    for i in graph[now]:
        if visited[i]: continue
        
        visited[i] = True
        ans[i] = now
        q.append(i)
        

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

Solution (Python):
from collections import deque
 
def bfs():
  que = deque([])
  que.append(0)
  
  while que:
    now = que.popleft()
    for next in g[now]: 
      if d[next] == 0:
        que.append(next)
        d[next] = now +1
        
n,m = map(int,input().split())
g = [[] for i in range(n)]
d = [0]*n
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)
  
bfs()
print('Yes')
for i in range(1,n):
  print(d[i])

Solution (Python):
from collections import deque
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = deque()
q.append(1)
while len(q):
    p = q.popleft()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.append(c)
print('Yes')
for i in range(2,n+1): print(ans[i])

Solution (Python):
def function():
    N,M = map(int, input().split())
    paths = [[] for _ in range(N+1)]
    for _ in range(M):
        A,B = map(int, input().split())
        paths[A].append(B)
        paths[B].append(A)
    
    depths = [-1]*(N+1)
    depths[1] = 0
    pre = [-1]*(N+1)
    q = [1] 
    while len(q) != 0:
        i = q.pop(0)
        for ne in paths[i]:
            if depths[ne] == -1: 
                depths[ne] = depths[i]+1
                pre[ne] = i
                q.append(ne)
    print('Yes')
    for p in pre[2:]: print(p)

if __name__ == '__main__':
    function()

Solution (Python):

from collections import deque
n, m = map(int, input().split())
x = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    x[a] += [b]
    x[b] += [a]
ans = [0] * (n + 1)
ans[1] = 1
que = deque([1])
while que:
    q = que.popleft()
    for i in x[q]:
        if ans[i] == 0:
            ans[i] = q
            que.append(i)
print("Yes")
print(*ans[2:], sep="\n")

Solution (Python):




import math
import sys
import bisect
import heapq  
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())

ans = [-1 for i in range(n)]  
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.popleft()
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] == False:
                visited[nextnode] = True
                ans[nextnode] = now
                q.append(nextnode)


bfs()
ans[0] = 0
print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Solution (Python):
def function():
    N,M = map(int, input().split())
    paths = []
    for _ in range(N+1):
        paths.append([])
    
    for _m in range(M):
        A,B = map(int, input().split())
        paths[A].append(B)
        paths[B].append(A)
    
    dist = [-1]*(N+1)
    dist[1] = 0
    pre = [-1]*(N+1)
    q = [1] 
    while len(q) != 0:
        i = q.pop(0)
        for ne in paths[i]:
            if dist[ne] == -1:
                dist[ne] = dist[i]+1
                pre[ne] = i
                q.append(ne)
    
    print('Yes')
    pre.pop(0)
    pre.pop(0)
    for d in pre:
        print(d)

if __name__ == '__main__':
    function()

Solution (Python):

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


que = [0] 
ans = [0] + [-1 for i in range(N - 1)] 
while -1 in ans: 
    quetmp = que
    que = []
    for node in quetmp: 
        for neighbor in edges[node]: 
            if ans[neighbor] == -1: 
                ans[neighbor] = node + 1 
                que += [neighbor] 


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

Solution (Python):
import queue
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    p = q.get()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.put(c)
print('Yes')
for x in ans[2:]: print(x)

Solution (Python):
import queue
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    p = q.get()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.put(c)
print('Yes')
print(*ans[2:], sep='\n')

Solution (Python):
from collections import deque

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

    p=[-1]*N
    q=deque([0])
    while q:
        i=q.popleft()
        for j in r[i]:
            if p[j] == -1:
                p[j] = i
                q.append(j)
    print('Yes')
    for i in range(1,N):
        print(p[i]+1)

main()

Solution (Python):





from collections import deque

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

    
    q = deque()
    q.append(0)
    seen = [-1]*N
    seen[0] = 0
    while len(q)>0:
        cur = q.popleft()
        lvl = seen[cur]
        for i in graph[cur]:
            if seen[i]==-1:
                
                
                
                seen[i] = cur
                q.append(i)

    if min(seen)==-1:
        print('No')
    else:
        print('Yes')
        for i in seen[1:]:
            print(i+1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

rooms = [-1] * N
def bfs(u):
    q = deque()
    q.append(u)
    while 0 < len(q):
        v = q.popleft()
        for e in edges[v]:
            if rooms[e] == -1:
                rooms[e] = v + 1
                q.append(e)

bfs(0)
print("Yes")
print(*rooms[1:], sep="\n")

Solution (Python):
from collections import deque

n, m = map(int, input().split())
u = [[] for _ in range(n)] 

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

q = deque([0])
ans = [-1] * n
count = 0

while len(q):
    p = q.popleft()
    for x in u[p]:
        if ans[x] == -1:
            ans[x] = p+1
            q.append(x)

ans[0] = 'Yes'

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

Solution (Python):
from collections import deque

def bfs(n,dict):
    que = deque()
    distance = [-1 for _ in range(n)]
    que.append([1,0,0])
    ans = [0 for _ in range(n)]
    while(len(que) > 0):
        tmp = que.popleft()
        now = tmp[0]
        step = tmp[1]
        prev = tmp[2]
        if distance[now-1] == -1:
            distance[now-1] = step
            ans[now-1] = prev
            for x in dict[now-1]:
                que.append([x,step+1,now])
        else:
            continue
    return ans

def main():
    n,m = map(int,input().split())
    L = [list(map(int,input().split())) for _ in range(m)]
    dict = [[] for _ in range(n)]
    for l in L:
        dict[l[0]-1].append(l[1])
        dict[l[1]-1].append(l[0])
    result = bfs(n,dict)
    print("Yes")
    for x in result[1:]:
        print(x)
main()

Solution (Python):
from collections import deque

def main():
  N,M=map(int,input().split())

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

  p=[-1]*N
  q=deque([0])
  while q:
    i=q.popleft()
    for j in r[i]:
      if p[j]==-1:
        p[j]=i
        q.append(j)

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

main()

Solution (Python):
from collections import deque

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))

def main(n,m,l):
    g = creategraph(n,l)
    for i in range(1,len(g)):
        if len(g[i]) == 0:
            print("No")
            return
    navi = bfs(n,g)
    if min(navi[2:]) == 0:
        print("No")
    else:
        print("Yes")
        for i in navi[2:]:
            print(i)
    
def bfs(n,g):
    navi = [0]*(n+1)
    navi[1] = -1
    q = deque()
    q.append(1)
    while len(q) > 0:
        cp = q.popleft()
        np = g[cp]
        for i in np:
            if navi[i] == 0:
                navi[i] = cp
                q.append(i)
    return navi
    
def creategraph(n,l):
    g = {i:[] for i in range(n+1)}
    for a,b in l:
        g[a].append(b)
        g[b].append(a)
    return g

def resolve():
    n,m = mi()
    l = mix(m)
    main(n,m,l)

if __name__ == "__main__":
    resolve()

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

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

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

Solution (Python):
from collections import deque

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

room_reached = [False] * (N + 1)
room_clue = [-1] * (N + 1)

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

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

q = deque()
q.append(1)

while len(q) > 0:
    start = q.popleft()
    for next_room in room_path_list[start]:
        if not room_reached[next_room]:
            room_reached[next_room] = True
            room_clue[next_room] = start
            q.append(next_room)

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

Solution (Python):
def main():
  N,M=map(int,input().split())

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

  p=[-1]*N
  q=[0]
  while q:
    i=q.pop(0)
    for j in r[i]:
      if p[j]==-1:
        p[j]=i
        q.append(j)

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

main()

Solution (Python):
n,m=map(int,input().split())
d={}
for i in range(m):
	x,y=map(int,input().split())
	if x in d:
		d[x].append(y)
	else:
		d[x]=[y]
	if y in d:
		d[y].append(x)
	else:
		d[y]=[x]

parent=[0]*(n+1)
bfs=[1]
visited=set([1])
while len(bfs)!=0:
	x=bfs.pop(0)
	visited.add(x)
	for i in d[x]:
		if i not in visited:
			bfs.append(i)
			parent[i]=x
			visited.add(i)


if len(visited)==n:
	print('Yes')
	for i in range(2,n+1):
		print(parent[i])
else:
	print('No')

Solution (Python):
import math
import queue

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


q = queue.Queue()

q.put(0)
    

flag = [0]*N 
flag[0]  = 1
ans_list = [0]*N

while(1):
  if(q.empty()):
    break
  num = q.get()
  for n in Map[num]:
    if(flag[n] != 1): 
      flag[n] = 1 
      ans_list[n] = num 
      q.put(n) 

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

Solution (Python):
from collections import deque
dic = {}
def make_map(a, b, dic):
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
N, M = map(int, input().split())
for m in range(M):
    a, b = map(int, input().split())
    make_map(a-1, b-1, dic)
    make_map(b-1, a-1, dic)
queue = deque([0])
count = 0
dekai = 10**5
lenlist = [dekai]*N
lenlist[0] = 0
while queue:
    a = queue.popleft()
    for i in dic[a]:
        if lenlist[i] ==dekai or a == 0:
            queue.append(i)
            lenlist[i] = a 
print("Yes")
for n in range(1,N, 1):
    print(lenlist[n]+1)

Solution (Python):
from collections import deque

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

def intinp():
    return int(input())


n, m = mapint_inp()
graph = [[] for _ in range(n)]
ans = [0]*n

for _ in range(m):
    a, b = mapint_inp()
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a) 

q = deque([0])
visited = [False]*n
visited[0] = True
while q:
    now = q.popleft()
    for i in graph[now]:
        if visited[i]: continue
        visited[i] = True
        ans[i] = now
        q.append(i)

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

Solution (Python):
n,m = map(int, input().split())
e = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    e[a].add(b)
    e[b].add(a)

p = [-1]*n
p[0] = 0
q = [0]
while len(q)>0:
    u = q.pop(0)
    for v in e[u]:
        if p[v]==-1:
            p[v] = u
            q.append(v)
if min(p)==-1:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(p[i]+1)

Solution (Python):
from collections import deque

def bfs_tree(graph, v=1):
    """
    graph: グラフ
    v: スタート
    """
    
    
    arrow = [-1]*len(graph) 
    q = deque()
    q.append(v)
    arrow[v] = 0
    while q:
        now = q.popleft()
        for next_v in graph[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow

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

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

arrow = bfs_tree(graph, 0)

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

Solution (Python):

from collections import deque

N, M = map(int, input().split())
l = [[] for i 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)

ans = [-1] * (N)

que = deque([0])

while que:
    now = que.popleft()
    for i in l[now]:
        if ans[i] == -1:
            ans[i] = now
            que.append(i)



if(min(ans) == -1):
    print("No")


print("{} ".format('Yes'))
for i in range(1,N):
    print("{} ".format(ans[i] + 1))

Solution (Python):
from collections import deque
N, M = map(int, input().split())
p = [0]
ans = [0]
for i in range(N):
    p.append(list())
    if i == 0:
        ans.append(0)
    else:
        ans.append(-1)
for i in range(M):
    A, B = map(int, input().split())
    p[A].append(B)
    p[B].append(A)
D = deque([1])
while D:
    ind = D.popleft()
    for i in p[ind]:
        if ans[i] == -1:
            D.append(i)
            ans[i] = ind

if -1 in ans[2:]:
    print('No')
else:
    print('Yes')
    for i in ans[2:]:
        print(i)

Solution (Python):
import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    
dist = [-1] * (N + 1)
que = collections.deque()

dist[1] = 0
que.append(1)

while len(que):
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = v
        que.append(nv)

print('Yes')
for value in dist[2:]:
    print(value)

Solution (Python):

import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 

from collections import defaultdict,deque 
n,m=map(int,input().split())
d=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
l=[0]
dist=[0]*n
l=deque(l)
while(l):
    s=l.popleft()
    for i in d[s]:
        if dist[i]==0:
            dist[i]=s+1
            l.append(i)
if 0 in dist[1:]:
    print("No")
else: 
    print("Yes")
    print(*dist[1:],sep="\n")

Solution (Python):
from collections import deque


def bfs(rooms, v=1):
    arrow = [-1] * len(rooms)
    q = deque()
    q.append(v)

    while q:
        now = q.popleft()
        for next_v in rooms[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow


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

    anss = bfs(rooms)
    print("Yes")
    for ans in anss[2:]:
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    
dist = [-1] * (N + 1)
que = collections.deque()

dist[1] = 0
que.append(1)

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

memo = collections.defaultdict(int)
memo[0] = 1

print('Yes')
for i in range(2, N+1):
    memo[dist[i]] = i
for dis in dist[2:]:
    print(memo[dis-1])

Solution (Python):
import math
from queue import Queue

n, m = [int(i) for i in input().split()]

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

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

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

q = Queue()
q.put(1)

while (not q.empty()):
    now = q.get()
    for i in root[now]:
        if (check[i] == 0):
            check[i] = now
            q.put(i)

flag = 1
for i in range(2, n + 1):
    if (check[i] == 0):
        flag = 0

if (flag == 1):
    print("Yes")
    for j in range(2, n + 1):
        print(check[j])
else:
    print("No")

Solution (Python):
from collections import deque

def bfs(graph,v=1):
    
    
    
    arrow = [-1]*len(graph) 
    q = deque()
    q.append(v)
    arrow[v] = 0
    while q:

        now = q.popleft()
        for next_v in graph[now]:
            if arrow[next_v] != -1:
                continue
            else:
                q.append(next_v)
                arrow[next_v] = now
    return arrow

def main():
    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)
    answer = bfs(graph)
    print("Yes")
    for ans in answer[2:]: 
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import queue

n,m=list(map(int,input().split()))
graph = [[] for i 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 i 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())
c = [[] for i in range(n)]
d = [-1 for i in range(n)]
d[0] = 0

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


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

while que:
    
    p = que.popleft()
    
    for i in c[p]:
        
        if d[i] != -1:
            continue
            
        que.append(i)
        d[i] = p

print("Yes")
for i in d[1:]:
    print(i+1)

Solution (Python):
from collections import deque
q = deque([0])

def dfs():
    while q:
        v = q.popleft()
        for nv in g[v]:
            if p[nv] < 1:
                p[nv] = v + 1
                q.append(nv)
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(lambda x:int(x) - 1,input().split())
    g[a].append(b)
    g[b].append(a)
    
p = [0] * n
dfs()
if 0 in p:
    print('No')
else:
    print('Yes',*p[1:],sep='\n')

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

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    
import collections
que = collections.deque()
que.append(0)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        if ans[to] == -1:
            ans[to] = x + 1
            que.append(to)
            
print("Yes")
print(*ans[1:],sep="\n")

Solution (Python):
import queue

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

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


v = [-1 for i 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):
n,m = map(int,input().split())
ans = [-1] * n
edge = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    
import collections
que = collections.deque()
que.append(0)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        if ans[to] == -1:
            ans[to] = x + 1
            que.append(to)
            
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    print(*ans[1:],sep="\n")

Solution (Python):
from collections import deque

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

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

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

dist = [-1] * (N + 1)
michi = [-1] * (N + 1)
dist[1] = 0
q = deque([1])

while q:
    now = q.popleft()
    for i in links[now]:
        if dist[i] == -1:
            dist[i] = dist[now] + 1
            michi[i] = now
            q.append(i)

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

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

n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,stdin.readline().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
queue=[0]
ans=[-1]*n
ans[0]=0
while len(queue)!=0:
    now_check=queue.pop(0)
    for i in ab[now_check]:
        if ans[i]==-1:
            queue.append(i)
            ans[i]=now_check
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

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

N , M = map(int,input().split())
miti = [ [] for _ in range(N)]
for m in range(M):
    a , b = map(int , input().split())
    if b-1 != 0:
        miti[a-1].append(b-1)
    if a-1 != 0:
        miti[b-1].append(a-1)
visit = [0] * N
point = [ -1 for _ in range(N)]

def bfs():
    G = deque([0])
    visit[0] = 1
    while G:
        m = G.popleft()
        for n in miti[m]:
            if visit[n] == 0 :
                visit[n] = 1
                point[n] = m
                G.append(n)

def solve():
    bfs()
    print("Yes")
    for a in point[1::]:
        print(a+1)

if __name__ == "__main__":
    solve()

Solution (Python):

import sys

input = sys.stdin.readline


from collections import deque

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

r = [[] for i in range(N+1)] 

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

miteru = deque([1]) 
mita = {1} 
res = [-1]*(N+1)

while  miteru: 
    now = miteru.popleft()
    x =set( r[now])
    x = x - mita
    for i in x:
        miteru.append(i)
        if res[i] == -1:res[i] =now
        mita.add(i)
    
print("Yes")
for i in res[2:]:
    print(i)