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):
import numpy as np
from collections import deque

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

ans = np.zeros(n, dtype = np.int)
ans[0] = 1
check = 0
queue = deque([0])

while queue:
    pos = queue.popleft()
    check += pos
    for next_pos in root[pos]:
        if ans[next_pos] != 0:
            continue
        ans[next_pos] = pos + 1
        queue.append(next_pos)
if check != n * (n - 1) / 2:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(ans[i])

Solution (Python):
from collections import deque

def bfs(E, s):
    N = len(E)
    order = [-1] * N 
    parent = [-1] * N 
    depth = [-1] * N 
    q = deque([(s, -1, 0)]) 
    num = 0 
    while q:
        v, p, d = q.popleft()
        if order[v] < 0: 
            order[v] = num; parent[v] = p; depth[v] = d
            num += 1
            for u in E[v]:
                if order[u] >= 0: continue
                q.append((u, v, d+1))
    return order, parent, depth

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1); E[b-1].append(a-1)
_, par, _ = bfs(E, 0)
print('Yes')
for p in par[1:]: print(p + 1)

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

    n, m = map(int, input().split())
    roads = defaultdict(deque)
    for _ in range(m):
        a, b = map(int, input().split())
        roads[a].append((b, a))
        roads[b].append((a, b))
    visited = [False]*(n+1)
    visited[1] = True
    ans = [0]*(n+1)
    neighbor = deque(roads[1])
    while neighbor:
        now, base = neighbor.popleft()
        if visited[now]:
            continue
        visited[now] = True
        ans[now] = base
        neighbor.extend(roads[now])
    print('Yes')
    for p_ans in ans[2:]:
        print(p_ans)

Solution (Python):
import queue

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


q = queue.Queue()
q.put(0)
guide = [-1] * n
guide[0] = 0
while True:
    if q.empty():
        break
    node = q.get()
    next_nodes = paths[node]
    for next_node in next_nodes:
        if guide[next_node] > -1:
            continue
        guide[next_node] = node
        q.put(next_node)

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

Solution (Python):
class queue:
    listQ = []
    def push(self, x):
        self.listQ.append(x)
    def pop(self):
        a = self.listQ[0]
        del self.listQ[0]
        return a
    def length(self):
        return len(self.listQ)


n, m = map(int, input().split())
nodeMap = {}
doneL = [0]*(n+1)
doneL[1] = -1
for i in range(m):
    a, b = map(int, input().split())
    if a in nodeMap:
        nodeMap[a].append(b)
    else:
        nodeMap[a] = [b]
    if b in nodeMap:
        nodeMap[b].append(a)
    else:
        nodeMap[b] = [a]

q = queue()
q.push(1)
while q.length():
    poped = q.pop()
    popedL = nodeMap[poped]
    for r in popedL:
        if doneL[r] != 0:
            pass
        else:
            doneL[r] = poped
            q.push(r)
print("Yes")
for r in doneL:
    if r <= 0:
        pass
    else:
        print(r)

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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)


parent = [-1] * N
q = deque()
q.append(0)
visited = set()
visited.add(0)

while len(q) != 0:
    cur = q.popleft()
    for n in graph[cur]:
        if n not in visited:
            visited.add(n)
            parent[n] = str(cur + 1)
            q.append(n)

print('Yes')
ans = '\n'.join(parent[1::])
print(ans)

Solution (Python):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range (M)]
import sys
sys.setrecursionlimit(10**8)

edge = [[] for _ in range(N)]
for u,v in AB:
    edge[u-1].append([v-1,1])
    edge[v-1].append([u-1,1])


import heapq
def dijkstra(S, N, Edge):
    
    
    
    
    INF = 10**20
    dist = [INF]*N
    dist[S] = 0
    que = [[0, S]]
    parent = [0]*N
    heapq.heapify(que)
    
    while que:
        c, v = heapq.heappop(que)
        if dist[v] < c: continue

        for nv, nc in Edge[v]:
            if c+nc < dist[nv]:
                dist[nv] = c+nc
                parent[nv] = v
                heapq.heappush(que, [c+nc, nv])
    
    return parent

parent = dijkstra(0, N, edge)
print('Yes')
for i in range(1,N):
    print(parent[i]+1)

Solution (Python):
from collections import deque

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

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

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

seen = [0 for i in range(n)]

mile = [-1 for i in range(n)]

q = deque()

q.append(0)
seen[0] = 1

while len(q) != 0:
    cur = q.popleft()

    for nx in maze[cur]:
        if not seen[nx] == 1:
            mile[nx] = cur+1
            seen[nx] = 1
            q.append(nx)

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

Solution (Python):
from collections import deque, Counter

N, M = map(int, input().split())
Road = [[] for _ in range(N)]
Ans = [-2] * N
Q = deque()
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    Road[A].append(B)
    Road[B].append(A)

now = 0
Ans[0] = -1
Q.append(now)

while len(Q) > 0:
    now = Q.popleft()
    for next in Road[now]:
        if Ans[next] == -2:
            Ans[next] = now
            Q.append(next)

Ans_S = set(Ans)

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

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,m=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v=MI1()
        to[u].append(v)
        to[v].append(u)
    hp=[]
    ans=[-1]*n
    heappush(hp,(0,0,0))
    while hp:
        d,u,pu=heappop(hp)
        if ans[u]!=-1:continue
        ans[u]=pu
        for v in to[u]:
            if ans[v]!=-1:continue
            heappush(hp,(d+1,v,u))
    print("Yes")
    for a in ans[1:]:
        print(a+1)

main()

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

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

from collections import deque
q = deque()
visit = [-1]*n
q.append(0)
visit[0] = 0
while q:
    v = q.popleft()
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = visit[v]+1
            q.append(u)

ans = [0]*n
for v in range(1, n):
    for u in g[v]:
        if visit[u] == visit[v]-1:
            ans[v] = u+1
print('Yes')
for i in range(1, n):
    print(ans[i])

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

Es = dd(dict)
for _ in range(M):
    a, b = map(int, input().split())
    Es[a][b] = Es[b][a] = 1

parents = [None] * (N+1)
parents[1] = 1
q = set([1])
while q:
    nq = set()
    for node in q:
        for to in Es[node]:
            if parents[to] is None:
                parents[to] = node
                nq.add(to)
    q = nq
print('Yes')
for i in range(2, N+1):
    print(parents[i])

Solution (Python):
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)

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

import queue
q = queue.Queue()
q.put([0,0])

while not q.empty():
    cost, nown = q.get()
    for nextn in g[nown]:
        if dist[nextn] != float('inf'):
            continue
        dist[nextn] = nown+1
        q.put([cost + 1,nextn])

for i in range(n):
    if dist[i] == float('inf'):
        print('No')
        exit()
print('Yes')
for i in range(1,n):
    print(dist[i])

Solution (Python):
import queue
import sys
input = sys.stdin.readline
from collections import defaultdict as dd
sys.setrecursionlimit(1000000)
N,M = map(int,input().split())
ab = [ tuple(map(int,input().split())) for i in range(M)]

edge = dd(list)

for i in range(M):
    tmp1 = ab[i][0]
    tmp2 = ab[i][1]
    edge[tmp1].append(tmp2)
    edge[tmp2].append(tmp1)
q = queue.Queue()
q.put((1,0))
res = [0]*N
mita = set()
mita.add(1)

while not q.empty():
    tmp = q.get()
    now = tmp[0]
    depth = tmp[1]
    for elem in edge[now]:
        if elem not in mita:
            mita.add(elem)
            q.put((elem,depth+1))
            res[elem-1] = now
            

if 0 not in res[1:]:
    print('Yes')
    for val in res[1:]:
        print(val)
else:
    print('No')

Solution (Python):




def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

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

    res = [-1]*n
    visited = [0]*n
    visited[0] = 1
    d = deque([0])
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if visited[nv] == 0:
                d.append(nv)
                res[nv] = v+1
                visited[nv] = 1

    for i in visited:
        if i == 0:
            print('No')
            break
    else:
        print('Yes')
        for i in res[1:]:
            print(i)

if __name__ == '__main__':
    main()

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, m = LI()
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

check = [True]*n
ans = [None]*n
que = deque()
que.append((0,-1))
while que:
    v, p = que.popleft()
    if not check[v]:
        continue
    check[v] = False
    for u in edges[v]:
        if u == p:
            continue
        que.append((u,v))
        if ans[u] == None:
            ans[u] = v+1

for i in range(1,n):
    if ans[i] == None:
        print('No')
        break
else:
    print('Yes')
    for i in ans[1:]:
        print(i)

Solution (Python):
from collections import deque

N, M = [int(v) for v in input().split()]

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

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

visited = [-1 for _ in range(N)]


queue = deque([0])

while queue:
    now = queue.pop()
    for n in ad_l[now]:
        if visited[n] != -1: continue
        visited[n] = now + 1
        queue.appendleft(n)

visited = visited[1:]

if -1 in visited:
    print("No")
else:
    print("Yes")
    for v in visited:
        print(v)

Solution (Python):
from collections import deque

int1 = lambda x: int(x) - 1

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


ans_lst = [None] * N
ans_lst[0] = 0
D = deque([0])
while D:
    v = D.popleft()
    for x in G[v]:
        if ans_lst[x] is None:
            ans_lst[x] = v
            D.append(x)
print('Yes')
for x in ans_lst[1:]:
    print(x + 1)

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

N,M = map(int,input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    A,B = [int(i)-1 for i in input().split()]
    adj[A].append(B)
    adj[B].append(A)
blis = [True]*N
ans = [0]*N
q = queue.Queue()
cou = 1
q.put(0)
blis[0] = False

while cou != N:
    now = q.get()
    for ad in adj[now]:
        if blis[ad]:
            blis[ad] = False
            ans[ad] = str(now+1)
            cou += 1
            q.put(ad)

print("Yes")
print("\n".join(ans[1:]))

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

graph = [[] for _ in range(N)]
for i, (Ai, Bi) in enumerate(AB):
    graph[Ai - 1].append(Bi - 1)
    graph[Bi - 1].append(Ai - 1)

import heapq
    
MY_INF = 1000000007
q = [(0, 0)]
d = [MY_INF] * N
d[0] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d[dst] > dist_tmp:
            d[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

for src in range(N):
    if src == 0:
        print('Yes')
        continue
    
    dist_min = MY_INF
    ans = 0
    for dst in graph[src]:
        if dist_min > d[dst]:
            dist_min = d[dst]
            ans = dst + 1
    
    print(ans)

Solution (Python):
from collections import deque
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
routes = [set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    A -= 1
    B -= 1
    routes[A].add(B)
    routes[B].add(A)

pool = deque([0])
ans = [-1] * N
ans[0] = 0
while pool:
    n = pool.popleft()
    for c in routes[n]:
        if ans[c] < 0:
            ans[c] = n
            pool.append(c)
print('Yes')
for i in range(1,N):
    print(ans[i]+1)

Solution (Python):
from collections import deque

N,M = map(int,input().split())
A = [set() for x in range(N)]
B = [-1]*N

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

B[0] = 0
D = deque()
D.append(0)
while len(D) != 0:
    d = D.popleft()
    for a in A[d]:
        if B[a] != -1:
            continue
        B[a] = d
        D.append(a)

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

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
connection=[[] for i in range(n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

b=bfs(0)
ans=[0]*n
print('Yes')
for i in range(1,n):
  for j in range(len(connection[i])):
    if b[connection[i][j]]==b[i]-1:
      print(connection[i][j]+1)
      break

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

N, M = map(int, readline().split())
AB = [list(map(int, readline().split())) for i in range(M)]
AB = [(a-1, b-1) for a,b in AB]

adj = [[] for i in range(N)]
for a,b in AB:
    adj[a].append(b)
    adj[b].append(a)

ans = [-1] * N

q = deque()
q.append(0)

while q:
    n = q.popleft()
    for c in adj[n]:
        if ans[c] == -1:
            ans[c] = n
            q.append(c)

if all(v != -1 for v in ans[1:]):
    print('Yes')
    for c in ans[1:]:
        print(c + 1)
else:
    print('No')

Solution (Python):
n,m=map(int,input().split())
node=[[]for _ in range(n)]
for _ in range(m):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
from collections import deque
sign=[-1]*n
sign[0]=0
queue=deque([0])
while queue:
	r=queue.popleft()
	for x in node[r]:
		if sign[x]==-1:
			sign[x]=r+1
			queue.append(x)
if -1 in sign:
	print("No")
else:
	print("Yes")
	for i in range(n-1):
		print(sign[i+1])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    N, M = inpl()
    AB = [inpl() for _ in range(M)]

    edges = {}
    for a, b in AB:
        if a not in edges:
            edges[a] = []
        if b not in edges:
            edges[b] = []

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

    Q = deque()
    Q.append(1)
    assigned = set()
    assigned.add(1)
    cost = {}
    cost[1] = 0
    previous_v = {}

    while Q:
        v = Q.popleft()
        for nv in edges[v]:
            if nv not in assigned:
                assigned.add(nv)
                Q.append(nv)

            tmp = cost[v] + 1
            if nv not in cost:
                cost[nv] = tmp
                previous_v[nv] = v
            elif tmp < cost[nv]:
                cost[nv] = tmp
                previous_v[nv] = v

    for i in range(2, N + 1):
        if i not in previous_v:
            print("No")
            break
    else:
        print("Yes")
        for i in range(2, N + 1):
            print(previous_v[i])

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()
 
class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: 
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    
    def query(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    
    def query_id(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]
 
    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


show_flg=False
show_flg=True
ans=0

n,m=LI()
g,_=GI(n,m)
d,p=dijkstra(g,0)

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

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

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

q = queue.Queue()
q.put(1)
t = [10**18 for i in range(n+1)]
tmt = [-1 for i in range(n+1)]
t[0] = 10*18
t[1] = 0

while not q.empty():
    qi = q.get()
    for i in way[qi]:
        if t[i] > t[qi]+1:
            t[i] = t[qi]+1
            tmt[i] = qi
            q.put(i)

if 10**18 in t:
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(tmt[i])

Solution (Python):
import queue
from collections import defaultdict
n,m = map(int,input().split())
g = defaultdict(set)
ans = [0]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].add(b)
    g[b].add(a)

visited = [False]*n
visited[0] = True
q = queue.Queue()
q.put(0)
while not q.empty():
    v = q.get()
    for p in g[v]:
        if not visited[p]:
            ans[p] = v
            q.put(p)
            visited[p] = True
print('Yes')
for x in ans[1:]:
    print(x+1)

Solution (Python):
import heapq as hq

def D_stra(N,connections,st):
    mxc=2**29
    cost =[mxc for i in range(N)]
    visited =[False for i in range(N)]
    flx = [mxc for i in range(N)]
    cost[st]=0
    q=[]

    hq.heappush(q,(0,st))

    while q:
        c,node=hq.heappop(q)
        if visited[node]:
            continue
        visited[node]=True

        for connection in connections[node]:
            target,mc=connection
            if cost[target]>c+mc:
                cost[target]=c+mc
                hq.heappush(q,(c+mc,target))
                flx[target]=node
    
    return cost,flx


    

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

    connections = [[] for i in range(N)]
    for i in range(M):
        a,b = map(int,input().split())
        connections[a-1].append([b-1,1])
        connections[b-1].append([a-1,1])
    ans,ans2 = D_stra(N,connections,0)

    if 2**29 in ans:
        print("No")
        return
    print("Yes")
    for i in ans2[1:]:
        print(i+1)

resolve()

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

from queue import Queue

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

used = [-1] * n
q = Queue()
used[0] = 0
q.put(0)
while not q.empty():
    s = q.get()
    for t in g[s]:
        if used[t] != -1:
            continue
        used[t] = s
        q.put(t)

if any(x == -1 for x in used):
    print("No")
    exit()

print("Yes")
for x in used[1:]:
    print(x + 1)

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

q = deque([(1,0)])
ans = [-1]*(N+1)
while q:
    u,v = q.popleft()
    if ans[u] == -1:
        ans[u] = v
        for w in g[u]:
            if w==v:
                continue
            q.append((w,u))

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