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):
MAX_INT = 10**6
N, M = map(int, input().split())
room = [set() for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    room[a].add(b)
    room[b].add(a)

dis = [MAX_INT] * (N + 1)
sign = [-1] * (N + 1)
dis[1] = 0
def sign_root(n):
    nxt = []
    for i in room[n]:
        if dis[n] + 1 < dis[i]:
            sign[i] = n
            dis[i] = dis[n] + 1
            nxt += [i]
    return nxt

nxt = sign_root(1)
while nxt != []:
    for i in nxt.copy():
        nxt.pop(0)
        nxt += sign_root(i)
if MAX_INT in dis[2:]:
    print("No")
else:
    print("Yes")
    for i in sign[2:]:
        print(i)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline


road_dict=defaultdict(list)

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

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

result_dict=defaultdict(int)

next_list=[]
for i in road_dict[1]:
    if i not in result_dict:
        result_dict[i]=1
        next_list.append(i)

taisho_list=next_list[:]

while True:
    next_list=[]

    if len(taisho_list)==0:
        break

    for j in taisho_list:
        for k in road_dict[j]:
            if k not in result_dict:
                result_dict[k]=j
                next_list.append(k)
    taisho_list=next_list[:]


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

Solution (Python):
from collections import deque

N, M = [int(s) for s in input().split()]
edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(N)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

dq = deque([0])
parent = [0] * N
parent[0] = 1
while(dq):
    search_obj = dq.pop()
    for candidate_obj in graph[search_obj]:
        if not parent[candidate_obj]:
            dq.appendleft(candidate_obj)
            parent[candidate_obj] = search_obj + 1

total_visited = sum(map(lambda x: x != 0, parent))
if total_visited < N:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(parent[i])

Solution (Python):
from collections import deque

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

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

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

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

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

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

import heapq
def dijkstra_heap(s):
  
  dist=[float("inf")]*size_v
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w,i in graph[s]:
    heapq.heappush(hq_edge,(w,v,i))

  while hq_edge:
    min_w,min_v,i=heapq.heappop(hq_edge)
    
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    prev[min_v]=i
    for v,w,i2 in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,i2))

  return dist

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


size_v=N+1
prev=[None]*size_v
dist=dijkstra_heap(1)



print("Yes")
for i in range(2,N+1):
  prev_e=ablist[prev[i]]
  if i==prev_e[0]:
    print(prev_e[1])
  else:
    print(prev_e[0])

Solution (Python):
import sys
import heapq


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]

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

    

    INF = 10 ** 18
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def dijkstra(s):
        color = [WHITE] * N
        d = [INF] * N
        p = [-1] * N
        d[s] = 0
        PQ = []
        heapq.heappush(PQ, (0, s))  
        color[s] = GRAY

        while PQ:
            distance, u = heapq.heappop(PQ)
            color[u] = BLACK

            if d[u] < distance:
                continue
            

            for j in range(len(adj[u])):
                v = adj[u][j]
                if color[v] == BLACK:
                    continue
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    p[v] = u
                    heapq.heappush(PQ, (d[v], v))
                    color[v] = GRAY

        return d, p

    d, p = dijkstra(0)
    
    if INF in d[1:]:
        print("No")
        sys.exit()
    else:
        print("Yes")
        for i in range(1, N):
            print(p[i] + 1)


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
L = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    L[a].append(b)
    L[b].append(a)

ans = [0 for _ in range(N+1)]
now = [1]
next = []

while len(now):
    for x in now:
        for y in L[x]:
            if (ans[y] == 0):
                ans[y] = x
                next.append(y)
    now = next.copy()
    next = []

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

Solution (Python):
from collections import deque
inf = 10 ** 7
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
a = [[] for i in range(N)]
for i in P:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
path = [-1] * N
path[0] = 0
checked = [False] * N
stack = deque([(0,0)])
while (len(stack) != 0):
    kk = stack.popleft()
    now = kk[0]
    pre = kk[1]
    if  not checked[now]:    
        nextP = a[now]
        checked[now] = True
        path[now] = pre
        for i in nextP:
            stack.append((i,now))
if False in checked:
    print("No")
else:
    print("Yes")
    for i in path[1:]:
        print(i + 1)

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

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

minv = [-1] * n
minv[0] = 0
length = [-1] * n
length[0] = 0


def bfs():
    global neighbor, length
    queue = deque([[0, 0]])
    while len(queue) > 0:
        v = queue.popleft()

        for nv in neighbor[v[0]]:
            if length[nv] == -1:
                length[nv] = v[1] + 1
                minv[nv] = v[0] + 1
                queue.append([nv, v[1] + 1])


bfs()

f = True
for i in minv:
    f &= i != -1

if not f:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(minv[i])

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

room = {}
startRoom = {1:1}

for i in range(M):
  A, B = map(int,input().split())
  room.setdefault(A, []).append(B)
  room.setdefault(B, []).append(A)
  
targetRoom = [1]
while len(targetRoom) != 0:
  nextTarget = []
  for i in targetRoom:
    roomList = room[i]
    for j in roomList:
      if j not in startRoom:
        startRoom[j] = i
        nextTarget.append(j)
  targetRoom = nextTarget
  
if len(startRoom) != N:
  print("No")
else:
  print("Yes")
  for i in range(2, N+1):
    print(startRoom[i])

Solution (Python):
from copy import copy, deepcopy
from collections import Counter, deque
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

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


def bfs(graph, visited, cost):
    now = 1
    queue = deque()
    for e in G[now]:
        queue.append((now, e))
    while queue:
        print(queue)
        pre, now = queue.popleft()
        if visited[now] == -1:
            visited[now] = pre
            cost[now] = cost[pre] + 1
            for e in G[now]:
                queue.append((now, e))
        elif cost[now] > cost[pre] + 1:
            visited[now] = pre
            cost[now] = cost[pre] + 1
            for e in G[now]:
                queue.append((now, e))


def bfs2(graph, visited, cost):
    now = 1
    queue = deque()
    for e in G[now]:
        queue.append((now, e))
    while queue:
        pre, now = queue.popleft()
        if cost[now] > cost[pre] + 1:
            visited[now] = pre
            cost[now] = cost[pre] + 1
            for e in G[now]:
                queue.append((now, e))


N, M = list(map(int, input().split()))
G = [[] for i in range(N+1)]
way = [-1 for i in range(N+1)]
cost = [INF for i in range(N+1)]
cost[1] = 0
cost[0] = 0
way[0] = 0

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



bfs2(G, way, cost)

tmp = way[2:]

if max(cost) == INF:
    print("No")
else:
    print("Yes")
    for i in range(len(tmp)):
        print(tmp[i])

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

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

for i in range(m):
    chizu[ab[i][0]].append(ab[i][1])
    chizu[ab[i][1]].append(ab[i][0])

kaisu=[chizu[1]]
for i in chizu[1]:
    ans[i]=1

error=0
j=-1
counter=len(chizu[1])
while True:
    j+=1
    if len(kaisu)<=j:
        error=0
        break
    for now in kaisu[j]:
        kari=[]
        for i in chizu[now]:
           if ans[i]==0:
                ans[i]=now
                kari.append(i)
                counter+=1
        kaisu.append(kari)
    if counter==n-1:
        break

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

elif error==1:
    print("No")

Solution (Python):
n,m=map(int,input().split())
marks = {i+1:-1 for i in range(n)}
roots = {i+1:[] for i in range(n)}

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

searchs = [{'root':roots[1], 'mark':1}]
while searchs != []:
    next_search = []
    for search in searchs:
        for root in search['root']:
            if marks[root] == -1:
                marks[root] = search['mark']
            else:
                continue
            next_search.append({'root':roots[root], 'mark':root})
    searchs = next_search[:]

marks[1] = 'Yes'
for v in marks.values():
    print(v)

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

from heapq import heappush, heappop
INF = float("inf")
miti = [-1]*N
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                if miti[t] == -1:
                    miti[t] = v+1
                heappush(que, (dist[t], t))
    return dist

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

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

dist = dijkstra(N,edge,0)

print("Yes")
for t in miti[1:]:
    print(t)

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

ans = [deque([]) for _ in range(m+10)]
ans2 = [[] for _ in range(m+10)]
for i in range(m):
    s = li[i][0]
    t = li[i][1]

    ans[s].append(t)
    ans[t].append(s)

stack = deque([1])
while stack:
    v = stack[0]

    if ans[v]:
        w = ans[v].popleft()
        if True:
            ans2[w].append(v)
        stack.append(w)
    else:
        stack.popleft()

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

Solution (Python):
n, m = map(int,input().split())
li = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    li[a-1].append(b-1)
    li[b-1].append(a-1)
sign = {0: 0}
step = {0: 1}
now = {0}
flg = False
while len(now) > 0:
    if flg:
        print('No')
        exit()
    flg = True
    next = set()
    for i in now:
        for j in li[i]:
            if not j in sign:
                sign[j] = i
                step[j] = step[i] + 1
                next.add(j)
                flg = False
    now.clear()
    now = next

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

Solution (Python):
import sys
import math
import itertools
import numpy

rl = sys.stdin.readline

n, m = map(int, rl().split())
li = [[] for _ in range(m+1)]
for _ in range(m):
  a, b = map(int, rl().split())
  a -= 1
  b -= 1
  li[a].append(b)
  li[b].append(a)

marks = [-1]*n
stack = [0]
while stack:
    for next_room in li[stack[0]]:
        if marks[next_room] == -1:
            stack.append(next_room)
            marks[next_room] = stack[0]
    del stack[0]
if -1 in marks:
  print('No')
else:
  print('Yes')
  for i in marks[1:]:
    print(i+1)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
l = [list() for i in range(n+1)]
ans = [0]*(n+1)
x = deque()
for i in range(m):
    a,b = map(int,input().split())
    if a == 1 :
        x.append(b)
        ans[b] = 1 
    elif b == 1:
        x.append(a)
        ans[a] = 1
    else:
        l[a] += [b]
        l[b] += [a]
while len(x) > 0:
    y = x.popleft()
    for num in l[y] :
        if ans[num] == 0:
            x.append(num)
            ans[num] = y
ans = ans[2:]
if 0 in ans :
    print('No')
else:
    print('Yes')
    for answer in ans:
        print(answer)

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

from heapq import heappush, heappop
INF = float("inf")
miti = [-1]*N
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                if miti[t] == -1:
                    miti[t] = v+1
                heappush(que, (dist[t], t))
    return dist

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

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

dist = dijkstra(N,edge,0)

print("Yes")
for t in miti[1:]:
    print(t)

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

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

d=[0]+[-1]*N
ans=[0]+[-1]*N
q=[0]
while q:
  u=q.pop(0)
  for v in range(len(k[u])):
    o=k[u][v]
    if d[o-1]<=0:
        d[o-1]=d[u]+1
        ans[o-1]=u
        q.append(o-1)
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

Solution (Python):
from queue import Queue

def bfs(AB,N):
    S = [None for _ in range(N+1)]
    
    AB_N = [set() for _ in range(N+1)]
    for ab in AB:
        a,b = ab[0],ab[1]
        AB_N[a].add((a,b))

    q = Queue()
    q.put(1)

    while not q.empty():
        p = q.get()
        for ab in AB_N[p]:
            a,b = ab[0],ab[1]
            if a == p:
                if  S[b] == None:
                    q.put(b)
                    S[b] = p

    can = True
    for i in range(2,N+1):
        if S[i] == None:
            can = False

    if can:
        return S[2:]
    else:
        return -1

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

    AB_ = set(AB)
    for i in range(M):
        AB_.add((AB[i][1],AB[i][0]))
    AB = AB_

    ans = bfs(AB,N)
    if ans == -1:
        print("No")
    else:
        print("Yes")
        for i in range(len(ans)):
            print(ans[i])

if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
L = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    L[a].append(b)
    L[b].append(a)

ans = [0 for _ in range(N+1)]
now = [1]
next = []

while len(now):
    for x in now:
        for y in L[x]:
            if (ans[y] == 0) and (y not in now):
                ans[y] = x
                next.append(y)
    now = next.copy()
    next = []

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

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

input = stdin.readline
def main():
    N, M = map(int, input().split())
    route = defaultdict(list)
    for i in range(M):
        a, b = map(int, input().split())
        route[a-1].append(b-1)
        route[b-1].append(a-1)
    
    arrive_time = [0] + [-1] * (N - 1)
    arrive_route = [0] + [-1] * (N - 1)
    q = deque()
    q.append(0)
    while len(q):
        idx = q.popleft()
        for c in route[idx]:
            if arrive_time[c] >= 0 and arrive_time[c] <= arrive_time[idx]+1:
                continue
            arrive_time[c] = arrive_time[idx]+1
            arrive_route[c] = idx
            q.append(c)
    if min(arrive_time) < 0:
        print("No") 
    else:
        print("Yes")
        for r in arrive_route[1:]:
            print(r+1)


if __name__ == '__main__':
    main()

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

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


d,dct = bfs(0)
if None in d:
  print('No')
  sys.exit()
print('Yes')
for _, v in sorted(dct.items()):
    print(str(v))

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

memo = {1:[0,None]}
for room in arr[1]:
    memo[room] = [1,1]

possible = True 
if len(memo.keys())<2:
    possible = False

visit = arr[1]
while len(visit) > 0:
    index = visit.pop(0)
    for item in arr[index]:
        if item not in memo.keys():
            distance = memo[index][0]
            memo[item] = [distance+1,index]
            visit.append(item)

if possible and len(memo.keys())==n:
    print("Yes")
    memo.pop(1)
    for item in sorted(memo.keys()):
        print(memo[item][1])

Solution (Python):
N,M = map(int, input().split())
path = [[] for i in range(N)]
for i in range(M):
    A,B = map(int, input().split())
    path[A-1].append(B)
    path[B-1].append(A)
    
ans = [0]*N
check = [0]*N
check[0] = 1
def func(x):
    ls = []
    for i in path[x-1]:
        if check[i-1] == 0:
            ans[i-1] = x
            check[i-1] = 1
            ls.append(i)
    return ls

fls = func(1)
while True:
    clist = []
    for i in fls:
        clist += func(i)
    if clist == []:
        break
    fls = clist
    
print('Yes')
for i in range(1,N):
    print(ans[i])

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))
from collections import deque


def bfs(u):
    queue = deque([u])
    ans = [0] * (n+1)
    ans[1] = 1
    while queue:
        v = queue.popleft()

        for i in d[v]:
            if  ans[i] == 0:           
                ans[i] = v
                queue.append(i)

    return ans

n,m = iim()
d = {}
for i in range(m):
    a,b = iim()
    la = d.get(a,[])
    la.append(b)
    d[a] = la
    lb = d.get(b,[])
    lb.append(a)
    d[b] = lb

ans = bfs(1)


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

Solution (Python):
import queue
n,m = map(int,input().split())
load = [list() for _ in range(n)]
ans = [None]*n
q = queue.Queue()
q.put(0)

for i in range(m):
    tmpa, tmpb = map(int,input().split())
    tmpa, tmpb = tmpa-1, tmpb-1
    load[tmpa].append(tmpb)
    load[tmpb].append(tmpa)

while not q.empty():
    log = q.get()
    for i in load[log]:
        if ans[i] is None:
            ans[i] = log
            q.put(i)

for i in range(n):
    if i==0 and ans[i]is None:
        print('No')
        break
    elif i==0:
        print('Yes')
    else:
        print(ans[i]+1)

Solution (Python):

import re
import math
from collections import defaultdict
from collections import deque
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache

readline=sys.stdin.readline
sys.setrecursionlimit(2000000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_pow(a,b):
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def get_primes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)

def main():
    N,M=map(int,input().split())
    G=[[] for a in range(N)]
    for a in range(M):
        x,y=map(int,input().split())
        x-=1
        y-=1
        G[x].append(y)
        G[y].append(x)
    mmin=[inf]*N
    mmin[0]=0
    to=[-1]*N
    Q=deque()
    Q.append(0)
    while len(Q)>0:
        now=Q.popleft()
        for a in range(len(G[now])):
            x=G[now][a]
            if mmin[x]>mmin[now]+1:
                mmin[x]=mmin[now]+1
                to[x]=now
                Q.append(x)
    to=to[1:]
    if to.count(-1)>0:
        print("No")
        return
    else:
        print("Yes")
        for a in range(N-1):
            print(to[a]+1)
main()

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

ans = [0] * (n - 1)

def bfs(i, queue, p):
    while len(queue) > 0:
        x = queue.popleft()
        pre = p.popleft()
        for j in range(len(x)):
            if ans[x[j] - 1] == 0 and x[j] != 0:
                ans[x[j] - 1] = pre + 1
                queue.append(data[x[j]])
                p.append(x[j])

queue = deque()
pre = deque()
pre.append(0)
queue.append(data[0])
bfs(0, queue, pre)

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

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

r=[[] for _ in range(n)]
d=deque()
b=[n+1]*n
for _ in range(m):
    a,z=map(int,input().split())
    r[a-1].append(z-1)
    r[z-1].append(a-1)

o=0
f=1
b[o]=0
for _ in range(n):
    for i in r[o]:
        if(b[i]==n+1):
            b[i]=o
            d.append(i)
    if(d):
        o=d.popleft()
        f+=1
    else:
        break

if (f==n):
    print("Yes")
    for i in b[1:]:
        print(i+1)
else:
    print("No")

Solution (Python):
import sys
import heapq

N, M = map(int, sys.stdin.readline().strip().split())
G = [[] for _ in range(N)]
for m in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)



d = [] * N
c = [False] * N
heapq.heappush(d, (0, 0))
p = [N] * N  

mindist = [float('inf')] * N
mindist[0] = 0

while d:
    now = heapq.heappop(d)[1]
    c[now] = True

    for i in G[now]:
        if mindist[now] + 1 < mindist[i]:
            mindist[i] = mindist[now] + 1
            p[i] = now
            heapq.heappush(d, (mindist[i], i))



if N in set(p[1:]):
    print('No')
else:
    print('Yes')
    for i in p[1:]:
        print(i + 1)

Solution (Python):
from collections import deque
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]+=[b-1]
  G[b-1]+=[a-1]
que=deque([0])
visited=[-1 for i in range(N)]
visited[0]=0
dokokara=[0 for i in range(N)]
while len(que)>0:
  v=que.popleft()
  for i in G[v]:
    if visited[i]!=-1:
      continue
    else:
      visited[i]+=1
      dokokara[i]=v
      que.append(i)


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

Solution (Python):
n, m = map(int,input().split())
p = [[] for x in range(n)]
r = [-2] + [-1] * (n - 1)
for _ in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    p[a].append(b)
    p[b].append(a)

from collections import deque
dq = deque()
dq.append(0)

def bfs(room):
    l = []
    global r
    for iroom in p[room]:
        if r[iroom] == -1:
            r[iroom] = room
            l.append(iroom)
    return l

while len(dq) > 0:
    c = dq.popleft()
    ll = bfs(c)
    dq.extend(ll)

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

Solution (Python):
import queue
n,m=map(int,input().split())
road_list=[set() for i in range(n)]
mitisirube=[0]*n
mitisirube[0]=1
for i in range(m):
    a,b=map(int,input().split())
    road_list[a-1].add(b)
    road_list[b-1].add(a)

q = queue.Queue()

counter_set=set()
counter_set.add(1)
for i in road_list[0]:
    q.put(i)
    mitisirube[i-1]=1
    counter_set.add(i)

while not q.empty():
    tmp=q.get()
    for i in road_list[tmp-1]:
        if i not in counter_set:
            q.put(i)
            counter_set.add(i)
            if mitisirube[i-1]==0:
                mitisirube[i-1]=tmp

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

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

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

def bfs(i, ans):
    d = deque()
    ans[i] = 0
    d.append(i)
    while len(d) > 0:
        v = d.popleft()
        for node in table[v]:
            if ans[node] == -1:
                ans[node] = v
                d.append(node)
    return ans


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

ans = bfs(0, ans)

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

Solution (Python):
import queue

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

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

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


result = [[999999999999999, None, False] for i in range(n)]


q = queue.Queue()

result[0] = [0, None, True]
for i in road[0]:
    q.put([0,i])

while not q.empty():
    n = q.get()
    if(not result[n[1]][2]):
        result[n[1]]=[result[n[0]][0]+1, n[0], True]
        for i in road[n[1]]:
            q.put([n[1], i])

flag = True
for i in result:
    if(not i[2]):
        flag = False
        break

if(flag):
    print("Yes")
    for i in range(1,len(result)):
        print(result[i][1]+1)
else:
    print("No")