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 i in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)
Q = deque()
vstd = [0]*(N+1)
mark = [0]*(N+1)
vstd[1] = 1
Q.append(1)
while Q:
    par = Q.popleft()
    for r in g[par]:
        if vstd[r]:
          continue
        else:
          mark[r]=par
          vstd[r]=1
          Q.append(r)
print('Yes')
for mk in mark[2:]:
    print(mk)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
g = [[] for i in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)
Q = deque()
vstd = [0]*(N+1)
mark = [0]*(N+1)
vstd[1] = 1
Q.append(1)
while Q:
    par = Q.popleft()
    for r in g[par]:
        if vstd[r]==0:
            mark[r]=par
            vstd[r]=1
            Q.append(r)
print('Yes')
for mk in mark[2:]:
    print(mk)

Solution (Python):
from collections import deque

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

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

d = deque([1])
ans = [-1] * 2 + [0 for i in range(n - 1)]

while d:
    parent = d.popleft()
    for child in t[parent]:
        if ans[child] == 0:
            d.append(child)
            ans[child] = parent

print('Yes')
[print(v) for v in ans[2:]]

Solution (Python):
import sys
import sys
import heapq
def dijkstra(s, es):
    '''Single Source Shortest Path (cost must not be negative)
    arguments
        s : source node number
        es: adjacency list
    returns
        cs: shortest path costs to each nodes
    '''
    INF=sys.maxsize
    cs=[INF]*len(es)
    ss=[-1]*len(es)
    cs[s],hq=0,[]
    heapq.heapify(hq)
    heapq.heappush(hq,(cs[s],s))
    while hq:
        d,v=heapq.heappop(hq)
        if cs[v]<d:continue
        for t,c in es[v]:
            if cs[t]>cs[v]+c:
                cs[t]=cs[v]+c
                ss[t]=v
                heapq.heappush(hq,(cs[t],t))
    return cs,ss
def main():
    N,M=tuple(map(int,sys.stdin.readline().split()))
    es=[[] for _ in range(N)]
    for _ in [0]*M:
        a,b=tuple(map(int,sys.stdin.readline().split()))
        a,b=a-1,b-1
        es[a].append((b,1))
        es[b].append((a,1))
    cs,ss=dijkstra(0,es)
    if ss.count(-1)>1:print('No')
    else:
        print('Yes')
        for d in ss[1:]:print(str(d+1))
if __name__=='__main__':main()

Solution (Python):
import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
def main():
    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)
    ans = [-1]*(N+1)
    Q = deque()
    Q.append(1)
    while len(Q) > 0:
        ima = Q.popleft()
        for tsugi in G[ima]:
            if ans[tsugi] == -1:
                ans[tsugi] = ima
                Q.append(tsugi)
    print("Yes")
    for e in ans[2:]:
        print(e)
if __name__ == '__main__':
    main()

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

v = [[0]]*2 + [[10**9] for i in range(n-1)]

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

while q:
    temp = q.popleft()
    for i in v[temp][1:]:
        if v[i][0] == 10**9:
            v[i][0] = temp
            q.append(i)
print("Yes")
for i in v[2:]:
    print(i[0])

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def bfs(G, s, t=None):
    """
    G[v] = [x1, x2,...]
    """
    dist = [-1] * len(G)
    dist[s] = 0
    par = [-1] * len(G)
    q = deque([s])
    while q:
        v = q.popleft()
        for x in G[v]:
            if dist[x] < 0 or dist[x] > dist[v] + 1:
                par[x] = v + 1
                dist[x] = dist[v] + 1
                q.append(x)
    return par


def solve():
    n, m = nm()
    G = [list() for _ in range(n)]
    for _ in range(m):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    par = bfs(G, 0)
    print('Yes')
    print(*par[1:], sep='\n')
    return

solve()

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

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

queue = [0]
dist = [0] * N
prev = [-1] * N
while(len(queue) != 0):
    now = queue[0]
    queue.pop(0)
    for i in loads[now]:
        if dist[i] != 0:
            continue
        else:
            queue.append(i)
            dist[i] = dist[now] + 1
            prev[i] = now + 1
print('Yes')
for i in prev[1:]:
    print(i)

Solution (Python):

n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
 a,b=map(int,input().split())
 g[a-1].append(b-1)
 g[b-1].append(a-1)
p=[-1]*n
q=[0]
while q:
 i=q.pop(0)
 for j in g[i]:
  if p[j]==-1:
   p[j]=i
   q.append(j)
print('Yes')
for i in range(1,n):
 print(p[i]+1)

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

def main():
    n, m = map(int, input().split())
    L = [[0] for _ in range(n)]
    for _ in [0] * m:
        a, b = map(int, input().split())
        L[a-1].append(b-1)
        L[b-1].append(a-1)
    L[0][0] = 1
    ans = [0] * n
    dq = deque([0])
    while dq:
        t = dq.popleft()
        for i in range(1, len(L[t])):
            next = L[t][i]
            if ans[next] != 0:
                continue
            ans[next] = t + 1
            dq.append(next)
        else:
            L[t][0] = 1
    print('Yes')
    print(*ans[1:], sep='\n')

main()

Solution (Python):
from collections import deque

WHITE=0
GRAY=1
BLACK=2

nList = []
labelList = []
color = []
Q = deque([])

def readinput():
    global nList
    global color
    global Q
    global labelList

    n,m=list(map(int,input().split()))
    nList = []
    for _ in range(n+1):
        nList.append([])  

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

    labelList = [0]*(n+1)
    color = [WHITE]*(n+1)
    Q = deque([])

    

def bfs(p):
    global Q
    global nList
    global color
    global labelList

    Q.append(p)
    color[p]=GRAY
    
    
    while(len(Q)>0):
        current=Q.popleft()
        for next in nList[current]:
            if(color[next]==WHITE):
                Q.append(next)
                color[next]=GRAY
                labelList[next]=current
                
                
                
        color[current]=BLACK

def main():

    bfs(1)


if __name__=='__main__':
    readinput()

    main()
    print('Yes')
    for l in labelList[2:]:
        print(l)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
for _ in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)

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

q = deque([1])
while q:
    a = q.popleft()
    for b in d[a]:
        if par[b]!=-1:continue
        par[b] = a
        q.append(b)

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

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

ans[0]=-1
ans[1]=1
for i in range(m):
    if a[i][0]==1:
        ikeruheya[0].append(a[i][1])
    elif a[i][1]==1:
        ikeruheya[0].append(a[i][0])
    else:
        ikeruheya[a[i][0]-1].append(a[i][1])
        ikeruheya[a[i][1]-1].append(a[i][0])


next=[1]
count = 1
while count < n and len(next)!=0:
    
    imaheya = next.pop(0)
    j = 0
    while j < len(ikeruheya[imaheya-1]) and count < n:
    
        if ans[ikeruheya[imaheya-1][j]]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya             
            next.append(ikeruheya[imaheya-1][j])
            count += 1
            j+=1
        else:
            j+=1


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

Solution (Python):
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*n

ans[0]=1

for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])


next=[1]

while len(next):
    imaheya = next.pop(0)-1
    for j in range(len(ikeruheya[imaheya])):
        if ans[ikeruheya[imaheya][j]-1]==0:
            ans[ikeruheya[imaheya][j]-1]= imaheya + 1           
            next.append(ikeruheya[imaheya][j])
            
        

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(n)]
sirusi=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
D=deque([0])
visited=[False]*n
visited[0]=True
while D:
    v=D.popleft()
    for i in graph[v]:
        if visited[i]:continue
        visited[i]=True
        sirusi[i]=v
        D.append(i)
print("Yes")
for i in range(1,n):
    print(sirusi[i]+1)

Solution (Python):
N,M=map(int,input().split())
ls_pass=[list(map(int,input().split())) for i in range(M)]

ls=[[] for i in range(N+1)]
for i in range(M):
  ls[ls_pass[i][0]].append(ls_pass[i][1])
  ls[ls_pass[i][1]].append(ls_pass[i][0])

ls_mark=[""]*2+[0]*(N-1)


from queue import Queue 
S=Queue()
S.put(1)
while not S.empty():
  a=S.get()
  for i in ls[a]:
    if ls_mark[i]==0:
      ls_mark[i]=a
      S.put(i)
if 0 in ls_mark:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(ls_mark[i])

Solution (Python):
N,M=map(int,input().split())
ls_pass=[list(map(int,input().split())) for i in range(M)]

ls=[[] for i in range(N+1)]
for i in range(M):
  ls[ls_pass[i][0]].append(ls_pass[i][1])
  ls[ls_pass[i][1]].append(ls_pass[i][0])

ls_mark=[""]*2+[0]*(N-1)


from queue import Queue 
S=Queue()
S.put(1)
while not S.empty():
  a=S.get()
  for i in ls[a]:
    if ls_mark[i]==0:
      ls_mark[i]=a
      S.put(i)
if 0 in ls_mark:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(ls_mark[i])

Solution (Python):
"""
 - https://atcoder.jp/contests/abc168/tasks/abc168_d
 - 幅優先探索
 - 部屋(d+1)の道しるべが部屋(d)を指すように設定すれば目標を達成できる
"""
from collections import deque
n, m = map(int, input().split()) 
list_init = [0]*(n+1)
c = [[] for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        list_init[i] = now
        que.append(i)
if 0 in list_init[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, list_init[2:])))

Solution (Python):




import sys
input = sys.stdin.readline

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

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

from collections import deque

def BFS(u): 
    queue = deque([u]) 
    dis = [None] * (n+1) 
    dis[u] = 0 
    ans = [-1] * (n+1) 
    while queue:
        v = queue.popleft() 
        for i in pic[v]: 
            if ans[i] == -1: 
                ans[i] = v
            if dis[i] is None:
                dis[i] = dis[v]
                queue.append(i)
    return ans

tmp = BFS(1) 
print('Yes')
for j in tmp[2:]:
    print(j)

Solution (Python):
import sys
from functools import lru_cache
 

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
inf = float('inf')
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,m=reads()
ls=[]
link=[[]for i in range(n)]
for i in range(m):
  a,b=reads()
  a-=1
  b-=1
  link[a].append(b)
  link[b].append(a) 
count=[inf]*n
count[0]=0


hoge=[0]
for i in range(n):
    targets=hoge
    hoge=[]
    for target in targets:
        for ele in link[target]:
            if count[ele]==inf:
                count[ele]=target+1
                
                hoge.append(ele)
    if not hoge:
        break
if inf in count:
    print("No")
    exit()
print("Yes")
for i in count[1:]:
    print(i)

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

fukasa = [0 for _ in range(n)]
fukasamoto = [0 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = {0}
kouho = 1

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					kouho += 1
					fukasa[k] = kaisuu
					fukasamoto[k] = i+1

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

Solution (Python):

def main():
    import sys
    imput = sys.stdin.readline
    
    
    
    N, M = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(M)]

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

    
    
    from collections import deque

    
    search_stack = deque([1])

    signpost = [-1] * (N+1)

    while search_stack:
        next_position = search_stack.popleft()
        for node in C[next_position]:
            if signpost[node] == -1:
                signpost[node] = next_position
                search_stack.append(node)

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

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

def main():
    n, m = map(int, input().split())

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

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

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

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

    while q:
        u = q.popleft()

        for v in g[u]:
            if f[v] == -1:
                f[v] = u
                q.append(v)

    ans = [ f[x] + 1 for x in range(1, n) ]
    print('Yes')
    print("\n".join(map(str, ans)))

main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n, m = map(int, readline().split())
ab = map(int, read().split())

graph = [[] for _ in range(n+1)]
for a, b in zip(ab, ab):
    graph[a].append(b)
    graph[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 graph[v]:
        if visited[w]:
            continue
        visited[w] = 1
        ans[w] = v
        q.append(w)
 
print('Yes')
print(*ans[2:], sep='\n')

Solution (Python):
import sys
import itertools

import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

 
n, m = map(int, readline().split())
 
adj = [[] for _ in range(n)]
 
for i in range(m):
    a, b = map(int, readline().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
 
 
import heapq
 
MAX = 10 ** 9 + 5
 
visited = [False for _ in range(n)]
dist = [MAX for _ in range(n)]
path = [0 for _ in range(n)]
 
def dji(start):
    dist[start] = 0
    q = [(0, 0)]
    while len(q) > 0:
        v = heapq.heappop(q)
        if visited[v[1]]:
            continue
        visited[v[1]] = True
        for u in adj[v[1]]:
            if dist[v[1]] + 1 < dist[u]:
                dist[u] = dist[v[1]] + 1
                path[u] = v[1] + 1
                heapq.heappush(q, (dist[u], u))
 
dji(0)
if all(visited):
    print("Yes")
    for i in path[1:]:
        print(i)
else:
    print("No")

Solution (Python):
from collections import deque
n,m=map(int,input().split())
neighbor=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  neighbor[a].append(b)
  neighbor[b].append(a)
def bfs(start,arrcnt):
  queue=deque([start])
  d=[None]*arrcnt
  d[start]=0
  while queue:
    l=queue.popleft()
    for i in neighbor[l]:
      if d[i]==None:
        d[i]=l+1
        queue.append(i)
  return d
d=bfs(0,n)
if None in d:
  print("No")
else:
  print("Yes")
  for i in range(1,n):
    print(d[i])

Solution (Python):

def main():
    import sys
    from collections import defaultdict
    from collections import deque
    N, M = map(int, sys.stdin.readline().split())
    AB = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    
    
    edge = defaultdict(list)
    for ab in AB:
        edge[ab[0]-1] +=[ab[1]-1]
        edge[ab[1]-1] +=[ab[0]-1]
    
    
    flag = [-1 for i in range(N)]
    def bfs(start, queue=deque([])):
        queue += [start]
        flag[start] =1
        while queue:
            now = queue.popleft()
            for ch in edge[now]:
                if flag[ch]==-1:
                    flag[ch] = now+1
                    queue.append(ch)
            
            
    
    bfs(0)
    print('Yes')
    for f in flag[1:]:
        print(f)
        
if __name__=='__main__':
    main()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
ans=[0]*(n+1)
adj=[[] for _ in range(n+1)]
for i in range(m):
    u,v=map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
que=deque([1])
vis=[0 for _ in range(n+1)]
vis[1]=1
while que:
    t=que.popleft()
    
    for i in adj[t]:
        
        if vis[i]==1:
            continue
        vis[i]=1
        ans[i]=t
        que.append(i)

if 0 in ans[2:]:
    print("No")
else:
    print("Yes")
    for i in ans[2:]:
        print(i)

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

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

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

q = deque([0])

while q:
    v = q.pop()
    for nex in aisles[v]:
        if visited[nex] != 0:
            continue
        visited[nex] = v + 1
        q.appendleft(nex)

print("Yes")
for point in visited[1:]:
    print(point)

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    adj = [[]for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)
    parent = [0]*(n+1)
    visited = [0]*(n+1)
    root = 1
    visited[root] = 1
    q = deque([root])
    while q:
        v = q.popleft()
        for i in adj[v]:
            if visited[i]:
                continue
            visited[i] = 1
            parent[i] = v
            q.append(i)
    print('Yes')
    print(*parent[2:], sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
g=[[] for _ in range(N)]
for i in range(M):
  A,B=map(int,input().split())
  g[A-1].append(B-1)
  g[B-1].append(A-1)
from collections import deque  
queue = deque([0])
d = [None] * N
d[0] = 0 
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = d[v] + 1
      queue.append(i)
  
l=[0]*(N-1)
for i in range(1,N):
  for j in g[i]:
    if d[j]==(d[i]-1):
      l[i-1]=j+1
      break
if 0 in l:
  print('No')
else:
  print('Yes')
  for i in range(len(l)):
    print(l[i])

Solution (Python):
n,m = map(int,input().split())
path = [[]for i in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1,input().split())
    path[a] += [b]
    path[b] += [a]
ans = [-1 for i in range(n)]
depth = [[] for i in range(n)]
visited = [False for i in range(n)]
d=0
ans[0] = -2
depth[0]+=[0]
visited[0]=True
while False in visited:
    for i in depth[d]:
        for j in path[i]:
            if not visited[j]:
                ans[j] = i+1
                depth[d+1] += [j]
                visited[j] = True
    d += 1
print("Yes")
for i in range(1,n):
    print(ans[i])

Solution (Python):
from collections import deque
n, m = map(int, input().split())
lis = [0]*(n+1)
c = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        lis[i] = now
        que.append(i)
if 0 in lis[2:]:
    print("No")
else:
    print("Yes")
    print("\n".join(map(str, lis[2:])))

Solution (Python):
from collections import deque
n, m = map(int, input().split())
lis = [0]*(n+1)
c = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    c[a].append(b)
    c[b].append(a)
    
que = deque([1])
check = [0 for i in range(n+1)]
check[1] = 1
while que:
    now = que.popleft()
    nx = c[now]
    for i in nx:
        if check[i] == 1:
            continue
        check[i] = 1
        lis[i] = now
        que.append(i)
if 0 in lis[2:]:
    print("No")
else:
    print("Yes")
    for i in lis[2:]:
        print(i)

Solution (Python):

from collections import defaultdict
from collections import deque

graph=defaultdict(list)

n,m=map(int,input().split())
for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans=defaultdict(lambda:-1)
que=deque([1])
ans[1]=1
while len(que)>0:
    a=que.popleft()
    for b in graph[a]:
        if ans[b]==-1:
            ans[b]=a
            que.append(b)
if len(ans)!=n:
    print("No")
else:
    print("Yes")
    for b in range(2,n+1):
        print(ans[b])

Solution (Python):
from collections import deque
 
 
def main():
    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])
    sign = [0] * (N + 1)
    sign[1] = 1
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not sign[v]:
                sign[v] = u
                queue.append(v)
 
    if all(sign[2:]):
        print("Yes")
        print("\n".join(map(str, sign[2:])))
    else:
        print("No")
 
 
if __name__ == "__main__":
    main()

Solution (Python):
N,M = list(map(int,input().split()))
MAX = 1000000000
import queue
dist = [MAX for i in range(N)]
pre = [-1 for i in range(N)]
To = [[] for i in range(N)]

que = queue.Queue()

for _ in range(M):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    To[a].append(b)
    To[b].append(a)
dist[0] = 0
que.put(0)
while(not que.empty()):
    v = que.get()
    for u in To[v]:
        if pre[u] != -1: continue
        dist[u] = dist[v] + 1
        que.put(u)
        pre[u] = v
        
        
print('Yes')
for i in pre[1:N]:
    print(i+1)

Solution (Python):
import queue
N,M=map(int,input().split())
adj=[[] for s in range(N+1)]
parent=[-1]*(N+1)
for i in range(M):
    A,B=map(int,input().split())
    adj[A].append(B)
    adj[B].append(A)
q=queue.Queue()
q.put((1,0))
while(not q.empty()):
    x,p=q.get()
    if parent[x]!=-1:
        continue
    parent[x]=p
    for next in adj[x]:
        if parent[next]==-1:
            q.put((next,x))
print('Yes')
for k in parent[2:]:
    print(k)

Solution (Python):
import queue
N,M = map(int,input().split())
adj = [[]for i in range(N+1)] 
parent = [-1] * (N+1) 
for m in range(M):
    a,b = map(int,input().split())
    adj[a].append(b) 
    adj[b].append(a) 
q = queue.Queue() 
q.put((1,0)) 
while(not q.empty()): 
    x, p = q.get() 
    if parent[x] != -1: 
        continue
    parent[x] = p 
    for next in adj[x]: 
        if parent[next] == -1: 
            q.put((next,x)) 
print ('Yes') 
for p in parent[2:]: 
    print(p)

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


road=[[] for i in range(n+1)]
for i in range(m):
    road[road_input[i][0]].append(road_input[i][1])
    road[road_input[i][1]].append(road_input[i][0])

from collections import deque
q=deque([1])
ans=[-1 for i in range(n)]
while len(q)>0:
  p=q.popleft()
  for i in road[p]:
    if ans[i-1]== -1:
      ans[i-1]=p
      q.append(i)

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

Solution (Python):
n,m=map(int,input().split())
gra=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  gra[a-1].append(b-1)
  gra[b-1].append(a-1)
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
dep=[0]*n
while d:
  g=d.popleft()
  for i in gra[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    dep[i]=dep[g]+1
route=[0]*(n-1)
for i in range(1,n):
  for t in gra[i]:
    if dep[t]==dep[i]-1:
      route[i-1]=t+1
      break
print('Yes')
print(*route)

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

def dijkstra(N):
  signs = [None] * (N+1)
  signs[0] = -1
  steps = [float('inf')] * (N+1)
  visited = [False] * (N+1)

  
  q = [(0, -1, 1)]
  while q:
    step,p,cur_node = heapq.heappop(q)
    steps[cur_node] = step
    signs[cur_node] = p
    visited[cur_node] = True

    for nei in adj[cur_node]:
      if visited[nei]: continue
      if step+1 < steps[nei]:
        steps[nei] = step+1
        heapq.heappush(q, (step+1, cur_node, nei))
  return signs

signs = dijkstra(N)[2:]
if float('inf') in signs:
  print("No")
else:
  print("Yes")
  for s in signs:
    print(s)

Solution (Python):

from collections import deque
q = deque([0])
Dequeue = lambda: q.popleft()
Enqueue = lambda x: q.append(x)
n, m = map(int, input().split())
l = [[] for _ in [0]*n]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    l[a] += [b]
    l[b] += [a]
ans = [-1]*n
while q:
    v = Dequeue()
    for i in l[v]:
        if ans[i] < 1:
            ans[i] = v+1
            Enqueue(i)
if -1 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

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

graph = defaultdict(list)

V, E = map(int, input().split())
for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

ans = defaultdict(lambda: -1)
que = deque([1])
ans[1] = 1
while len(que) > 0:
    u = que.popleft()
    for v in graph[u]:
        if ans[v] == -1:
            ans[v] = u
            que.append(v)

if len(ans) != V:
    print('No')
else:
    print('Yes')
    for v in range(2, V + 1):
        print(ans[v])

Solution (Python):
n, m = map(int, input().split())
graph = {}
for i in range(m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
guide = {1: 0}
visited = [1]
i = 0
while True:
    for j in graph[visited[i]]:
        if j not in guide.keys():
            guide[j] = visited[i]
            visited.append(j)
    i += 1
    if i == len(visited):
        break

if len(visited) == n:
    print("Yes")
    for x in range(2, n+1):
        print(guide[x])
else:
    print("No")

Solution (Python):
n, m = map(int, input().split())
graph = {}
for i in range(m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
guide = {1: 0}
visited = [1]
i = 0
while True:
    
    for j in graph[visited[i]]:
        if j not in guide.keys():
            guide[j] = visited[i]
            visited.append(j)
            
    i += 1
    
    
    if i == len(visited):
        break

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

Solution (Python):
n, m = map(int,input().split())
graph = {}
for i in range(0, m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
signs = {1:0}
current = [1]
while current:
    node = current.pop(0)
    for j in graph[node]:
        if j not in signs:
            signs[j] = node
            current.append(j)  
if len(signs) == n:
    print("Yes")
    for x in range(2, n+1):
        print(signs[x])
else:
    print("No")