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 sys
import  math
from heapq import *
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

    
N,M=nm()
INF=10**18
def bfs(start,edge):
    d=[INF]*(N+1)
    ans=[0]*(N+1)
    d[start]=0
    q=[(0,start)]
    while(len(q)!=0):
        ci,i=heappop(q)
        for j in edge[i]:
            if(d[j]>d[i]+1):
                d[j]=d[i]+1
                heappush(q,(d[j],j))
                ans[j]=i

    return ans




edge=[[]for _ in range(N+1)]
for i in range(M):
    A,B=nm()
    edge[A].append(B)
    edge[B].append(A)

ans=bfs(1,edge)


for i in range(2,N+1):
    if(ans[i]==0):
        print('No')
        sys.exit(0)

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

Solution (Python):
import collections as c
class graph:
    def __init__(self, n):
        self.n = n
        self.node = [[] for _ in range(n)]
        self.unexplored = [True] * n
        self.landmark = [-1] * (n-1)

    def unit(self, a, b):
        self.node[a].append(b)
        self.node[b].append(a)
    
    def bfs(self):
        queue = c.deque([self.node[0]])
        land = c.deque([0])
        self.unexplored[0] = False
        while queue:
            v = queue.popleft()
            l = land.popleft()
            for d in v:
                if self.unexplored[d]:
                    self.landmark[d-1] = l+1
                    queue.append(self.node[d])
                    land.append(d)
                    self.unexplored[d] = False
    
    def get_land(self):
        return self.landmark

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

g.bfs()
land = g.get_land()
if -1 in land:
    print('No')
else:
    print('Yes')
    for x in land:
        print(x)

Solution (Python):
from collections import deque

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



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


d=[float('inf') for i in range(n)]
m=[0 for i in range(n)]

def bfs():

    que=deque([])
    que.append(0)
    d[0]=0
    
    while que:
        p=que.popleft()
        for np in L[p]:
            if d[np]==float('inf'):
                que.append(np)
                d[np]=d[p]+1
                m[np]=p+1

bfs()
if sum(d)==float('inf'):
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(m[i])

Solution (Python):
from collections import deque

N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

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

num = [0 for _ in range(N)]
num[0] = 1

dist = [10**15 for _ in range(N)]
dist[0] = 0

queue = deque([1])
visited = [False for _ in range(N)]

while queue:
    v = queue.popleft()
    if(visited[v-1]):
        continue
    visited[v-1] = True
    for value in graph[v]:
        if(visited[value-1]):
            continue
        if(dist[value-1] > dist[v-1]+1):
            dist[value-1] = dist[v-1]+1
            num[value-1] = v
        queue.append(value)

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

Solution (Python):
from collections import deque

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

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

res = [-1]*N
res[0] = N
d = deque()
d.append(0)

while True:
    now = d.popleft()
    
    for n in miti[now]:
        if not res[n] < 0:
            continue
        res[n] = now

        d.append(n)

    if not len(d):
        break

if -1 in res:
    print("No")
else:
    print("Yes")
    print("\n".join(str(r+1) for r in res[1:]))

Solution (Python):
N, M = map(int,input().split())
A = []
B = []
for i in range(M):
  a, b = map(int,input().split())
  A.append(a)
  B.append(b)
  
link_dic = {}
for i in range(M):
  if A[i] not in link_dic.keys():
  	link_dic[A[i]] = [B[i]]
  else:
  	link_dic[A[i]].append(B[i])
  if B[i] not in link_dic.keys():
  	link_dic[B[i]] = [A[i]]
  else:
  	link_dic[B[i]].append(A[i])

sign = [0] * N
j = 1
current_room = [1]

def search_room(l):
  global current_room
  did = 0
  next_cr = []
  for i in l:
    li = link_dic[i]
    for k in range(len(li)):
      if sign[li[k]-1] == 0:
        sign[li[k]-1] = i
        next_cr.append(li[k])
        did += 1
        
  current_room = list(next_cr)
        
  if did == 0:
  	return 1
  else:
  	return 0
  	
while j > 0:
  result = search_room(current_room)
  if result:
    break

sign_ans = sign[1:N]
if min(sign_ans) == 0:
  print('No')
else:
  print('Yes')
  for i in sign_ans:
    print(i)

Solution (Python):
from collections import deque
def D():
    n, m = map(int, input().split())
    G = {}
    for i in range(n+1):
        G[i] = []
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    visited = [False] * (n+1)
    visited[1] = True
    mark = [0] * (n+1)
    dq = deque()
    for node in G[1]:
        mark[node] = 1
        visited[node] = True
        dq.append(node)
    while len(dq) != 0:
        node = dq.popleft()
        for next_node in G[node]:
            if not visited[next_node]:
                mark[next_node] = node
                visited[next_node] = True
                dq.append(next_node)
    print("Yes")
    for i in range(n-1):
        print(mark[i+2])
D()

Solution (Python):
N,M=map(int,input().split())
from heapq import heappop,heappush 

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

mark=[-1]*(N-1)

inf=float("inf")

di=[inf]*N
di[0]=0
hq=[(0,0)]

while hq:
    t,r=heappop(hq) 
    if t>di[r]:
        continue
    for x in graph[r]:
        t_new=t+1
        r_new=x
        if t_new<di[r_new]:
            di[r_new]=t_new
            heappush(hq,(t_new,r_new))
            if mark[r_new-1]==-1:
                mark[r_new-1]=r
            else:
                print("No")
                exit()
    
print("Yes")
for i in mark:
    print(i+1)

Solution (Python):
from collections import  deque

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

used = [False for _ in range(N)]
INF = int(1e20)
shirube = [0 for _ in range(N-1)]


def bfs(e):
    d = deque()
    used[e] = True
    d.append(e)
    while len(d) != 0:
        ne = d.pop()
        for elm in graph[ne]:
            if not used[elm]:
                shirube[elm-1] = ne
                used[elm] = True
                d.appendleft(elm)


bfs(0)
if all(used):
    print("Yes")
    for el in shirube:
        print(el+1)
else:
    print("No")

Solution (Python):



from collections import deque
import sys
input = sys.stdin.readline



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

    next = [[] for i in range(N)]
    for i in range(M):
        temp1,temp2 = map(int,input().split())
        next[temp1-1].append(temp2)
        next[temp2-1].append(temp1)

    visited = set([1])
    test = set([i+1 for i in range(N)])

    res = [0 for i in range(N)]
    res[0] = 'No'

    temp = next[0]
    queue = deque(next[0])
    for i in temp:
        res[i-1] = 1
        visited.add(i)

    while queue:
        v = queue.popleft()
        temp = next[v-1]
        for i in temp:
            if i not in visited:
                res[i-1] = v
                queue.append(i)
                visited.add(i)

    
    

    if test != visited:
        print(res[0])
    else:
        res[0] = 'Yes'
        for i in range(N):
            print(res[i])



main()

Solution (Python):
N,M=map(int,input().split())
tree=[[] for i in range(N)]
ans=[0]*N
ischecked=[0]*N
ischecked[0]=1
for i in range(M):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)
q=[0]
while q:
    now=q.pop(0)
    for i in tree[now]:
        if ischecked[i]==1:
            continue
        ans[i]=now+1
        ischecked[i]=1
        q.append(i)
flag=0
for i in range(1,N):
    if ans[i]==0:
        flag=1
        break
if flag==0:
    print("Yes")
    for i in range(1,N):
        print(ans[i])
else:
    print("No")

Solution (Python):
from collections import deque
N, M = map(int, input().split())
d = dict()
for m in range(M):
    a, b = map(int, input().split())
    d.setdefault(a-1, []).append(b-1)
    d.setdefault(b-1, []).append(a-1)
n = [-1] * N
n[0] = 0
q = deque()
q.append(0)
if 0 in d:
    while len(q) > 0:
        i = q.popleft()
        for dd in d[i]:
            if n[dd] == -1:
                n[dd] = i
                q.append(dd)
if -1 not in n:
    print('Yes')
    for x in range(1, N):
        print(n[x] + 1)
else:
    print('No')

Solution (Python):
import heapq


def qqq(path, par, reached):
    queue = []
    heapq.heappush(queue, 0)
    reached[0] = True

    while queue:
        queue_next = []
        for _ in range(len(queue)):
            p = heapq.heappop(queue)

            for i in path[p]:
                if reached[i] is False:
                    reached[i] = True
                    par[i] = p
                    heapq.heappush(queue_next, i)
        queue = queue_next

        if all(reached):
            break


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

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

    for a, b in AB:
        path[a - 1].append(b - 1)
        path[b - 1].append(a - 1)

    par = [-1 for _ in range(N)]
    reached = [False for _ in range(N)]

    qqq(path, par, reached)

    if all(reached):
        print('Yes')
        for i in par[1:]:
            print(i + 1)
    else:
        print('No')


main()

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

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

parents = [-1]*n
tmparr = []
children = [0]
flags = [True] * n
flags[0] = False

while any(flags):
    while children:
        tmp = children.pop()
        for node in graph[tmp]:
            if flags[node]:
                flags[node] = False
                parents[node] = tmp
                tmparr.append(node)
    children = tmparr[:]
    tmparr = []
    
print("Yes")
for i in parents[1:]:
    print(i+1)

Solution (Python):
import numpy as np

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(m)]

root = []
for i in range(n):
    root.append(set())

for ab in AB:
    root[ab[0]-1].add(ab[1]-1)
    root[ab[1]-1].add(ab[0]-1)

sign = [0]*n
sign[0]=-1
list = [0]

while True:
    x = list.pop(0)

    for next in root[x]:
        if sign[next]==0:
            sign[next]=x+1
            list.append(next)

    if len(list)==0:
        break

print('Yes')
for p in sign[1:]:
    print(p)

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

table = [-1]*N
queue = deque([1])
table[0] = 0
count = 0
while queue:
    n = queue.popleft()
    for c in path[n-1]:
        if table[c-1] == -1:
            table[c-1] = n
            queue.append(c)
            count += 1
        
if count < N - 1:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(table[i])

Solution (Python):
n,edge = map(int,input().split())
l = [0]*n 
stack = [1]
dic  = {}
for i in range (edge) :
    x = [int(x) for x in input().split()]
    if x[0] not in dic :
        dic[x[0]] = []
    if x[1] not in dic :
        dic[x[1]] = []
    dic[x[0]].append(x[1])
    dic[x[1]].append(x[0])
x = 1 
while len(stack) != 0 :
    check = stack[0]
    stack.pop(0)
    for i in range (len(dic[check])) :
        if l[dic[check][i]-1] == 0 :
            x += 1 
            stack.append(dic[check][i])
            l[dic[check][i]-1] = check 
if l.count(0) != 0 :
    print("No")
else :
    print("Yes")
    for i in range (1,n) :
        print(l[i])

Solution (Python):
def main():
    N,M=map(int,input().split())
    graph=[[] for _ in range(N)]
    for _ in range(M):
        A,B=map(int,input().split())
        graph[A-1].append([A-1,B-1])
        graph[B-1].append([B-1,A-1])
    
    ans=[-1]*N
    Q=graph[0]
    while Q!=[]:
        tmp=[]
        for q in Q:
            ind,val=q
            if ans[val]!=-1:
                continue
            ans[val]=ind
            tmp+=graph[val]
        Q=tmp
    for w in ans:
        if w==-1:
            print("No")
            break
    print("Yes")
    for w in ans[1:]:
        print(w+1)
main()

Solution (Python):
from collections import deque

n, m = map(int, input().split())
room = {i: set() for i in range(n)}
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    room[a].add(b)
    room[b].add(a)

ans = dict()
visited = [1] + [0] * (n - 1)
que = deque([0])
while que:
    now = que.popleft()
    for i in room[now]:
        if visited[i]:
            continue
        ans[i] = now
        visited[i] = 1
        que.append(i)

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

Solution (Python):
from collections import deque

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

ans = [(-1, float("inf"))] * N
cnt = 0

queue = deque([(1, 0)])

while queue:
    val, step = queue.popleft()
    next_vals = d[val]
    for nxt in next_vals:
        
        if ans[nxt - 1][0] == -1:
            cnt += 1
            ans[nxt - 1] = (val, step + 1)
            queue.append((nxt, step + 1))

if cnt < N - 1:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i][0])

Solution (Python):
from collections import deque

N, M = map(int, input().split())
G = [deque([]) for i in range(N+1)] 

road = [input().split() for i in range(M)]

for i in range(M):
    G[int(road[i][0])].append(int(road[i][1]))
    G[int(road[i][1])].append(int(road[i][0]))     

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

def dfs(v):
    stack = deque([v])
    
    while stack:    
        tmp = stack[0]
        if G[tmp]:
            w = G[tmp].popleft() 
            if check[w] < 0:
                check[w] = tmp
                stack.append(w)
        else:
            stack.popleft()
    return check


check = dfs(1)
check[0] = 100
check[1] = 100

if -1 in check:
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(check[i])

Solution (Python):

import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div

N, M = ri_()
d = [[] for i in range(N + 1)]
ans = [0] * (N + 1)
for i in range(M):
    A, B = ri_()
    d[A].append(B)
    d[B].append(A)
L = deque([1])
while L:
    n = L.popleft()
    for i in d[n]:
        if not ans[i]:
            ans[i] = n
            L.append(i)
if 0 in ans[2:]:
    print('No')
    exit()
print('Yes')
for i in range(2, N + 1):
    print(ans[i])

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split(' '))
edges = defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split(' '))
    edges[a].add(b)
    edges[b].add(a)

queue = deque()
queue.append(1)
results = {}

while len(queue) > 0:
    x = queue.popleft()
    next_nodes = edges[x]
    for node in next_nodes:
        if node not in results.keys():
            results[node] = x
            queue.append(node)

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

Solution (Python):


def solve():
    import sys
    from collections import deque

    N, M = list(map(int, sys.stdin.readline().split()))
    rooms = [None]*(N+1)
    for _ in range(M):
        A, B = list(map(int, sys.stdin.readline().split()))
        
        if rooms[A] is None:
            rooms[A] = []
        if rooms[B] is None:
            rooms[B] = []
        rooms[A].append(B)
        rooms[B].append(A)

    ans = [None] * (N+1)
    ans[0] = -1
    ans[1] = -1

    
    que = deque([1])
    while que:
        room = que.popleft()
        nrooms = rooms[room]
        
        

        for nroom in nrooms:
            if ans[nroom] == None:
                ans[nroom] = room
                que.append(nroom)
            else:
                pass

    if None in ans:
        print("No")
        return
    print("Yes")
    for v in ans[2:]:
        print(v)


if __name__ == "__main__":
    solve()

Solution (Python):

import sys
input = sys.stdin.readline


from collections import deque


def main():
    n, m = map(int, input().split())
    AL = [[] for i in range(n+1)]
    check = [0 for i in range(n+1)]
    for i in range(m):
        s, e = map(int, input().split())
        AL[s].append(e)
        AL[e].append(s)
    que = deque()
    pb = 1, 1
    que.append(pb)
    ANS = [0 for i in range(n+1)]
    while(que):
        pb = que.popleft()
        p = pb[0]
        b = pb[1]
        if check[p] == 1:
            continue
        elif check[p] == 0:
            ANS[p] = b
            check[p] = 1
            for num in AL[p]:
                que.append((num, p))
    print("Yes")
    for i in range(n+1):
        if i in [0, 1]:
            continue
        else:
            print(ANS[i])

    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
tunagari={}
for i in range(m):
    a,b=map(int,input().split())
    if a not in tunagari:
        tunagari[a]=[b]
    else:
        tunagari[a].append(b)
    if b not in tunagari:
        tunagari[b]=[a]
    else:
        tunagari[b].append(a)
heya=["." for i in range(n)]
ans=[0 for i in range(n)]
heya[0]=0
tmp=deque([1])
count=1
while tmp:
    now=tmp.popleft()
    for i in tunagari[now]:
        if heya[i-1]==".":
            heya[i-1]=heya[now-1]+1
            tmp.append(i)
            ans[i-1]=now

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

Solution (Python):



def input_int():
    return int(input())



def int1(x):
    return int(x) - 1



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



def input_to_int_tuple():
    return tuple(map(int, input().split()))



def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, m = input_to_int_map()
    ab = [input_to_int_tuple() for i in range(m)]

    from collections import defaultdict
    room = defaultdict(set)
    for a, b in ab:
        room[a].add(b)
        room[b].add(a)


    from collections import deque
    root = deque()
    root.append(1)
    moved = [-1] * n
    moved[0] = 0
    while root:
        room_no = root.popleft()
        for move_room_no in room[room_no]:
            if moved[move_room_no - 1] != -1:
                continue

            root.append(move_room_no)
            moved[move_room_no - 1] = room_no

    if min(moved) == -1:
        print("No")
    else:
        print("Yes")
        for i in moved[1:]:
            print(i)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

n, m = map(int, input().split())
e = {i:[] for i in range(1, n+1)}
for _ in range(m):
    p, q = map(int, input().split())
    e[p].append(q)
    e[q].append(p)

def bfs():
    visited = [0] + [None] * n
    queue = deque([1])
    visited[1] = 0
    while queue:
        current = queue.pop()
        for x in e[current]:
            if visited[x] == None:
                visited[x] = current
                queue.appendleft(x)
    return visited

print('Yes')
print(*bfs()[2:], sep='\n')

Solution (Python):
from collections import deque, defaultdict

def solve(N, M, paths):
    used = [False for _ in range(M)]
    stack = deque([1])
    ret = [[float("inf"), -1] for _ in range(N + 1)]
    ret[1] = [0, 1]

    while stack:
        cur = stack.popleft()
        nexts = paths[cur]
        for n in nexts:
            if used[n[0]]:
                continue
            used[n[0]] = True
            if ret[cur][0] + 1 < ret[n[1]][0]:
                ret[n[1]] = [ret[cur][0] + 1, cur]
                stack.append(n[1])

    print("Yes")
    for r in ret[2:]:
        print(r[1])

if __name__ == "__main__":
    N, M = map(int, input().split())
    paths = defaultdict(list)
    for idx in range(M):
        a, b = map(int, input().split())
        paths[a].append([idx, b])
        paths[b].append([idx, a])

    solve(N, M, paths)

Solution (Python):

import queue

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


edges_dict = {}
for edge in edges:
    a, b = edge

    if a not in edges_dict:
        edges_dict[a] = [b]
    else:
        edges_dict[a].append(b)

    if b not in edges_dict:
        edges_dict[b] = [a]
    else:
        edges_dict[b].append(a)


COST = 1
INF = 1e10


dist_list = [INF] * (n + 1)

prev_list = [None] * (n + 1)
q = queue.PriorityQueue()


q.put((0, 1)) 
dist_list[1] = 0
prev_list[1] = 1

while not q.empty():
    min_dist, v = q.get()
    

    if dist_list[v] < min_dist:
        
        continue

    
    for w in edges_dict[v]:
        cost = dist_list[v] + COST
        if dist_list[w] > cost:
            
            dist_list[w] = cost
            prev_list[w] = v
            q.put((cost, w))

print("Yes")



for v in prev_list[2:]:
    print(v)

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
e = []
es = defaultdict(set)
for i in range(m):
    ee = tuple(sorted(map(int, input().split())))
    e.append(ee)
    es[ee[0]].add(ee[1])
    es[ee[1]].add(ee[0])

path = [None] * (n + 1)
path[1] = 1
num = 0
nodes = {1}
while nodes:
    new_nodes = set()
    for nd in nodes:
        for e in es[nd]:
            if path[e] is None:
                path[e] = nd
                num += 1
                new_nodes.add(e)
    nodes = new_nodes
if num == n - 1:
    print("Yes")
    for i in range(2, n + 1):
        print(path[i])
else:
    print("No")

Solution (Python):
n,m=map(int,input().split())



r=list()
for i in range(n):
    a=list()
    r.append(a)
a=list()
for i in range(n):
    a.append(-1)
for i in range(m):
    x=0;y=0
    x,y=map(int,input().split())
    x-=1
    y-=1
    r[x].append(y)
    r[y].append(x)
    

a[0]=0
now=[0]
while len(now)!=0:
    nex=list()
    for i in now:
        for j in r[i]:
            if a[j]==-1:
                a[j]=i
                nex.append(j)
    now=nex


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

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import heapq


def Bellman_Ford(s,n,w,es):
    
    
    d = [Max] * n
    
    d[s] = 0
    po = 0
    while po < 2*N + 100:
        update = False
        for p,q,r in es:
        
            if d[p] != Max and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
        po += 1
    return d


def dijkstra():
    

    edge = [[] for i in range(n)]
    dg = 10**7
    
    for i in range(e):
        x,y = map(int,input().split())
        z = 1
        x -= 1
        y -= 1
        edge[x].append(z*dg + y)
        edge[y].append(z*dg + x)
    
    s = w-1
    d = [-1]*n
    d[s] = 0

    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)

        

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v,c = minedge%dg,minedge//dg
        if d[v] >= 0:
            continue
        d[v] = c
        for e in edge[v]:
            vNext = e%dg
            if d[vNext]:
                heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

    return d


def warshall_floyd(n,d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d






N,M = m()


n = N
w = 1
gr = [[] for i in range(n)]
edge = [[] for i in range(n)]
dg = 10**7

for i in range(M):
    a,b = map(int,input().split())
    z = 1
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
    edge[a].append(z*dg + b)
    edge[b].append(z*dg + a)

s = w-1
d = [-1]*n
d[s] = 0

edgelist = []
for e in edge[s]:
    heapq.heappush(edgelist,e)

    

while len(edgelist):
    minedge = heapq.heappop(edgelist)
    v,c = minedge%dg,minedge//dg
    if d[v] >= 0:
        continue
    d[v] = c
    for e in edge[v]:
        vNext = e%dg
        if d[vNext]:
            heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)
print("Yes")
for i in range(1,N):
    for j in gr[i]:
        if d[i] == d[j]+1:
            print(j+1)
            break

Solution (Python):
import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M = map(int, readline().split())
graph = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int1, readline().split())
    graph[A].append(B)
    graph[B].append(A)
ans = [None] * (N)

visited = [False] * N
visited[0] = True

que = deque([0])

while len(que) > 0:
    acc = que.popleft()
    for connected in graph[acc]:
        if visited[connected]:
            continue

        ans[connected] = acc + 1
        visited[connected] = True
        que.append(connected)

if sum(visited) == len(visited):
    print("Yes")
    for sign in ans[1:]:
        print(sign)
else:
    print("No")

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def print_ans(self):
        for i in range(1, n):
            print(self.prev[i]+1)

g = Graph()

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

d = Dijkstra(g, 0)
print('Yes')
d.print_ans()