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 heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    fr = [0]*N
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                fr[to] = cur
                heapq.heappush(h, [dist[to], to])
    return fr, dist

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, 1))
    G[b].append((a, 1))
ans, dis = dijkstra(0, G)
print("Yes")
for i in range(1, N):
    print(ans[i]+1)

Solution (Python):
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  E[A-1] += [B-1]
  E[B-1] += [A-1]

ans = [-1]*N
T = [0]
while len(T)>0:
  P = T
  T = []
  for x in P:
    for e in E[x]:
      if ans[e]==-1:
        T += [e]
        ans[e] = x

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

for i in range(m):
    u,v = map(int, input().split())
    u -= 1 
    v -= 1
    ns[u].add(v)
    ns[v].add(u)

from queue import deque
start = 0
q = deque([start])
seen = [None] * n
seen[start] = 0
while q:
    u = q.pop()
    d = seen[u]
    for v in ns[u]:
        if seen[v] is None:
            seen[v] = u
            q.appendleft(v)
print("Yes")
print("\n".join(map(lambda x:str(x+1), seen[1:])))

Solution (Python):
from heapq import heappush,heapify,heappop
INF = 10**10

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

es=[[] for _ in range(n)] 
d = [INF]*n 
prev=[-1]*n 


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


def dijkstra(s):
    v = -1
    que = [(0,s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que, (d[e[0]], e[0])) 
                prev[e[0]] = v
def get_path(t):
    path = []
    while t != -1:
        path.append(t)
        t = prev[t]
    path.reverse()
    return path
dijkstra(0)
print("Yes")
for i in range(1,n):
    print(prev[i]+1)

Solution (Python):
from collections import deque
N,M = map(int, input().split())
dic = [[] for i in range(N+1)]
for i in range(M):
  a,b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
ans = [-1]*(N+1)
ans[1] = 0
q = deque([1])
while q:
  p = q.popleft()
  for v in dic[p]:
    if ans[v]==-1:
      ans[v] = p
      q.append(v)
if all(-1!=c for c in ans[1:]):
  print('Yes')
  for i in range(2,N+1):
    print(ans[i])
else:
  print('No')

Solution (Python):
from collections import deque

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

ans = [-1] * n
q = deque([(0, -2)])
while q:
    v, p = q.popleft()
    if ans[v] != -1:
        continue
    ans[v] = p
    for u in links[v]:
        if ans[u] != -1:
            continue
        q.append((u, v))

print('Yes')
print('\n'.join(str(v + 1) for v in ans[1:]))

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

n,m = map(int,readline().split())
data = list(map(int,read().split()))
it = iter(data)

links = [[] for _ in range(n+1)]
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

d = deque()
d.append(1)
parent = [-1] * (n+1)
parent[1] = 0

while(d):
    i = d.popleft()
    for j in links[i]:
        if(parent[j] == -1):
            parent[j] = i
            d.append(j)

ans = parent[2:]
if(min(ans) == -1):
    print('No')
else:
    print('Yes')
    print('\n'.join(map(str,ans)))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict,deque
N,M= map(int,input().split())

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

pre = defaultdict(int)
pre[1] = 0
d = [10**6]*(N+1)

dq = deque([1])
d[1] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[v] + 1 < d[nv]:
            d[nv] = d[v] + 1
            pre[nv] = v
            dq.append(nv)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush




def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)



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

def dfs(N, start, edge):
    q=deque([(start,0)])
    visited=[False]*N
    ans=[0]*N
    while len(q):
        e, pe=q.popleft()
        if visited[e]:continue
        ans[e]=pe
        visited[e]=True
        for ne in edge[e]:
            q.append((ne,e))
            
    return ans

def main():
    mod = 10**9+7
    

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

    edgelist=tree_init(N,M)

    ans=dfs(N,0,edgelist)
    print('Yes')
    for a in ans[1:]:
        print(a+1)





if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n
    prev_node = [-1] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                prev_node[v_to] = v_from
                heappush(heap, (dist[v_to], v_to))
    return dist, prev_node


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

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

dist, prev_node = dijkstra(graph, n, 0)



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

Solution (Python):
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

N,M = Ints()

from collections import defaultdict
Graph = defaultdict(list)

for i in range(M):     
    A,B = Ints()
    Graph[A].append([B,1])
    Graph[B].append([A,1])

def dijkstra_heap(s,Graph,N):
    import heapq
    que = []
    INF = 10**18
    MIN = [INF]*(N+1)    
    From = [-1]*(N+1)
    
    heapq.heappush(que,[0,s])

    while que != []:
        nowc,to = heapq.heappop(que)
        MIN[to] = min(nowc, MIN[to])
        if MIN[to] >= nowc:
            for (b,c) in Graph[to]:
                if nowc+c < MIN[b]:
                    From[b] = to
                    MIN[b] = nowc+c
                    heapq.heappush(que,[nowc+c,b])
    return MIN,From

MIN,From = dijkstra_heap(1,Graph,N+1)

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

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

def bfs():
    q = deque([0])
    dist = [-1]*N
    dist[0] = 0
    ans = [-1]*N
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                ans[nv] = v
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return ans

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

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

ans = bfs()
print('Yes')

for i in range(1, N):
    print(ans[i]+1)

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())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

visited = [False]*n
d = [10**15]*n

visited[0] = True
d[0] = 0
q = deque([0])

ans = [0]*n

while q:
    v = q.popleft()
    for w in g[v]:
        if not visited[w]:
            visited[w] = True
            d[w] = d[v] + 1
            ans[w] = v+1
            q.append(w)

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

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

adj = [list() 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)

parent = [None]*N
queue = deque([0])
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if parent[v] is None:
            parent[v] = u
            queue.append(v)

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

Solution (Python):

def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

from collections import deque
def bfs(G):
    q=deque()
    q.append((1, -1))
    log = [0] * n
    log[0] = 1
    while q:
        
        V, P = q.popleft()
        for new_v in G[V - 1]:
            if new_v == P:continue
            if log[new_v - 1] != 0:continue
            log[new_v - 1] = V
            q.append((new_v, V))

    return log



n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)
log = bfs(G)
print('Yes')
print(*log[1:], sep='\n')

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    n,m = inpm()
    g = [[] for _ in range(n)]
    for _ in range(m):
        a,b = inpm()
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
    did = [0 for _ in range(n)]
    did[0] = 1
    que = deque()
    que.append(0)
    ans = [0 for _ in range(n-1)]
    while que:
        next_que = deque()
        while que:
            go = que.pop()
            for i in range(len(g[go])):
                if did[g[go][i]]:
                    continue
                ans[g[go][i]-1] = go + 1
                did[g[go][i]] = 1
                next_que.append(g[go][i])
        que = next_que
    if 0 in ans:
        print('No')
        return
    print('Yes')
    for i in range(n-1):
        print(ans[i])

if __name__ == "__main__":
    main()

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

graph = [[] for _ in range(N + 1)]
arrow = [0] * (N + 1)

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(st, graph):
    INF = 10 ** 18
    dist = [0] * len(graph)
    dist[st] = 1
    queue = deque([st])
    while queue:
        q = queue.popleft()
        for r in graph[q]:
            if dist[r] == 0:
                dist[r] = q
                queue.append(r)
    return dist

answer = bfs(1, graph)[2:]
print("Yes")
for a in answer:
    print(a)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

INF = float('inf')

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


def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    prevs = [None] * numV
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2 in adjList[vNow]:
            c2 = cNow + 1
            if c2 < costs[v2]:
                costs[v2] = c2
                prevs[v2] = vNow
                heappush(PQ, (c2, v2))
    return (costs, prevs)

costs, prevs = Dijkstra(adjL, 0)




print('Yes')
print('\n'.join(map(lambda x: str(x+1), prevs[1:])))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  


import heapq
from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, s, t, w=1):
        self.E[s].append((t, w))
        self.E[t].append((s, w))


def shortestPath(g: Graph, s: int):
    
    
    
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):

    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    dist, prev = shortestPath(g, 0)
    if dist == INF:
        print("No")
        return
    print("Yes")
    for i in range(1, N):
        print(prev[i]+1)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)


if __name__ == '__main__':
    main()

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

visit = [-1 for _ in range(n)]
visit[0] = 0
tree = [[] for _ in range(n)]
for a, b in ab:
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

from collections import deque
q = deque([0])
while q:
    p = q.popleft()
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = p
            q.append(i)
if all(i >= 0 for i in visit):
    print("Yes")
    for i in visit[1:]:
        print(i+1)
else:
    print("No")

Solution (Python):
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A].append(B)
        graph[B].append(A)

    visited = dict()
    cur = [1]
    while cur:
        temp = []
        for v in cur:
            for u in graph[v]:
                if u not in visited:
                    visited[u] = v
                    temp.append(u)
        cur = temp

    if len(visited) < N:
        print("No")
    else:
        print("Yes")
        for i in range(2, N+1):
            print(visited[i])


if __name__ == '__main__':
    main()

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

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

prev = [None] * (N + 1)
seen = [False] * (N + 1)
node = deque([1])
seen[1] = True

while node:
    s = node.popleft()
    for t in edge[s]:
        if not seen[t]:
            seen[t] = True
            prev[t] = s
            node.append(t)

if any(x is None for x in prev[2:]):
    print("No")
else:
    print("Yes")
    print(*prev[2:], sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map( int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map( lambda x:int(x)-1, input().split())
        E[u].append(v)
        E[v].append(u)
    d = deque([0])
    V = [-1]*N
    V[0] = 0
    while d:
        u = d.popleft()
        for v in E[u]:
            if V[v] == -1:
                V[v] = u+1
                d.append(v)
    print("Yes")
    print( "\n".join( map( str, V[1:])))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

from collections import deque
inf = 10 ** 6
mark = [-1 for _ in range(n)]
que = deque()
mark[0] = 0
que.append(0)

while que:
    cur = que.popleft()
    for to in edges[cur]:
        if mark[to] == -1:
            mark[to] = cur
            que.append(to)

if any(mark[i] == -1 for i in range(n)):
    print('No')

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
s=[[]for i in range(N)]
print("Yes")
for i in range(M):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
l=[-1]*N
b=[0]
while b:
    a=[]
    for i in b:
        for j in s[i]:
            if l[j]==-1:
                l[j]=i+1
                a.append(j)
    b=a
print(*l[1:],sep="\n")

Solution (Python):
from collections import defaultdict, deque

N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

g = defaultdict(list)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)

source = 1
dist = {}
q = deque()
q.append(source)
dist[source] = 0
while q:
    node = q.popleft()
    level = dist[node]
    for nbr in g[node]:
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = level + 1

if len(dist) != N:
    print("No")
    exit()

print("Yes")
for i in range(2, N + 1):
    for nbr in g[i]:
        if dist[nbr] == dist[i] - 1:
            print(nbr)
            break

Solution (Python):
import sys
import heapq

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0

    
    prev = [None] * n_nodes

    
    q = [(dist[start], start)]
    heapq.heapify(q)

    while q:
        
        d, i = heapq.heappop(q)

        
        
        if dist[i] < d:
            continue

        
        
        for j in edge[i]:
            if dist[j] > dist[i] + 1:
                dist[j] = dist[i] + 1
                prev[j] = i  
                heapq.heappush(q, (dist[j], j))

    return dist, prev


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

    dist, prev = dijkstra(0, N, edges)

    for d in dist:
        if d == INF:
            print("No")
            return

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


if __name__ == "__main__":
    main()

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

from collections import defaultdict, deque
import heapq
g = defaultdict(list)
for a, b in ab:
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)


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

q = [(0, 0)] 
prev = [float('inf')] * n 
heapq.heapify(q)
while q:
    du, u = heapq.heappop(q) 
    if d[u] < du:
        continue
    for v in g[u]:
        if du + 1 < d[v]:
            d[v] = du + 1
            prev[v] = u
            heapq.heappush(q, (d[v], v))

f = True
prev2 = []
for i in range(1, n):
    if prev[i] == float('inf'):
        f = False
    prev2.append(prev[i] + 1)

if f:
    print('Yes')
    for p in prev2:
        print(p)
else:
    print('No')

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(nodes, src):
    from collections import deque

    N = len(nodes)
    que = deque([src])
    res = [-1] * N
    res[src] = 0
    while que:
        u = que.popleft()
        for v in nodes[u]:
            if res[v] != -1:
                continue
            res[v] = u
            que.append((v))
    return res

N, M = MAP()
nodes = [[] for i in range(N)]
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

res = bfs(nodes, 0)
Yes()
for a in res[1:]:
    print(a+1)

Solution (Python):
import collections


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

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

que = collections.deque([0])
while que:
    target = que.popleft()
    for g in G[target]:
        if F[g] == -1:
            F[g] = target
            que.append(g)

res = [F[i] + 1 for i in range(N)]
res[0] = "Yes"
print("\n".join(map(str, res)))

Solution (Python):
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007



def main():
	
	n, m = tin()
	
	mm = [[] for _ in range(n)]
	rrp=[-1]*n
	for _ in range(m):
		a,b = tin()
		mm[a-1].append(b-1)
		mm[b-1].append(a-1)
	
	q = queue.Queue()
	q.put((0,0))
	while not q.empty():
		pos, parent = q.get()
		if rrp[pos] >= 0:
			continue
		rrp[pos] = parent
		
		for v in mm[pos]:
			q.put((v, pos))
	print('Yes')
	for v in rrp[1:]:
		print(v+1)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from collections import deque

N,M = [int(i) for i in input().split()]
graph = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = [int(i) for i in input().split()]
    graph[a].add(b)
    graph[b].add(a)

path = {1:0}
seen = set([1])
que = deque([1])
while que:
    node = que.popleft()
    for n in graph[node]:
        if n not in seen:
            seen.add(n)
            que.append(n)
            path[n] = node

if len(seen) != N:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(path[i])

Solution (Python):

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

dict_path = {i+1: [] for i in range(N)}

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

list_bfs = [1]
list_flg = [0 for _ in range(N+1)]
list_flg[1] = 1

while len(list_bfs)>0:
  list_tmp = []
  for i in list_bfs:
    for j in dict_path[i]:
      if list_flg[j]==0:
        list_tmp.append(j)
        list_flg[j] = i
  list_bfs = list_tmp

print('Yes')
for i in list_flg[2:]:
  print(i)

Solution (Python):
import sys
input=sys.stdin.readline
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)
from collections import deque
q=[0]
q=deque(q)
ans=[-1]*n
while len(q)>0:
    now=q.popleft()
    for i in G[now]:
        if ans[i]<0:
            ans[i]=now
            q.append(i)
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Solution (Python):






import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache






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






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def Yes(): print("Yes"); return
def No(): print("No"); return


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count





N,M = inputIL()

graph = [[] for i in range(N)]
for _ in range(M):
  a,b = inputIL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
d = [INF for i in range(N)]
prev = [None for i in range(N)]
q = deque([0])
d[0] = 0
while q:
  x = q.popleft()
  nd = d[x]+1
  for nx in graph[x]:
    if nd < d[nx]:
      d[nx] = nd
      prev[nx] = x
      q.append(nx)
      
print("Yes")
for i in prev[1:]:
  print(i+1)