Problem:
 Score: 400 points    Problem Statement  There is a cave.  The cave has N rooms and M passages. The rooms are numbered 1 to N , and the passages are numbered 1 to M . Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.  It is dark in the cave, so we have decided to place a signpost in each room except Room 1 . The signpost in each room will point to one of the rooms directly connected to that room with a passage.  Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1 .   If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.   Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.      Constraints   All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 2 \times 10^5  1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)  A_i \neq B_i\ (1 \leq i \leq M)  One can travel between any two rooms by traversing passages.         Input  Input is given from Standard Input in the following format:  N  M  A_1  B_1  :  A_M  B_M       Output  If there is no way to place signposts satisfying the objective, print No .  Otherwise, print N lines. The first line should contain Yes , and the i -th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i .        Sample Input 1 4 4
1 2
2 3
3 4
4 2      Sample Output 1 Yes
1
2
2  If we place the signposts as described in the sample output, the following happens:   Starting in Room 2 , you will reach Room 1 after traversing one passage: (2) \to 1 . This is the minimum number of passages possible.  Starting in Room 3 , you will reach Room 1 after traversing two passages: (3) \to 2 \to 1 . This is the minimum number of passages possible.  Starting in Room 4 , you will reach Room 1 after traversing two passages: (4) \to 2 \to 1 . This is the minimum number of passages possible.   Thus, the objective is satisfied.       Sample Input 2 6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6      Sample Output 2 Yes
6
5
5
1
1  If there are multiple solutions, any of them will be accepted.

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
from queue import deque
setrecursionlimit(10 ** 7)

n,m = map(int,stdin.readline().rstrip().split())
li = [[]for _ in range(n)]
lin = []

length = {}
length_path = [0]*n

for i in range(m):
    a,b = map(int,stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    li[a].append(b)
    li[b].append(a)
    if a < b:
        length[(a,b)] = 1
    else:
        length[(b,a)] = 1
    lin.append([a,b])


work_queue = deque([])
visited = [False]*n
work_queue.append(0)
while work_queue:
    now = work_queue.popleft()
    visited[now] = True
    for i in li[now]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if now < i:
            length_path[i] = length_path[now]+length[(now,i)]
        else:
            length_path[i] = length_path[now]+length[(i,now)]
kotae = [0]*n

for num,i in enumerate(li):
    ima = i
    now = 10**10
    for j in ima:
        if length_path[j] < now:
            now = length_path[j]
            k = j
    kotae[num] = k+1
print("Yes")
for i in kotae[1:]:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,sin,cos
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]




n,m=mii()

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


ans=[-1]*n

for i in range(m):
    a,b=mii()
    mat[a-1].append([a-1,b-1])
    mat[b-1].append([b-1,a-1])


q=deque(mat[0])

while len(q)>0:

    node = q.popleft()
    
    if node is not None:
        if ans[node[1]]==-1:
            ans[node[1]]=node[0]
            for i in mat[node[1]]:
                q.append([node[1],i[1]])

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

Solution (Python):
from collections import defaultdict
def D():
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for i in range(M):
        A, B = map(int, input().split())
        edges[A].append(B)
        edges[B].append(A)
    
    ans = {}
    q = [(1, None)]
    seen = set(q)
    while q:
        cur, last = q.pop(0)
        ans[cur] = last
        for room in edges[cur]:
            if room not in seen:
                q.append((room, cur))
                seen.add(room)
    
    if len(ans) < N:
        print('No')
    else:
        print('Yes')
        for i in range(2, N+1):
            print(ans[i])

D()

Solution (Python):
n,m = map(int,input().split())
d = {i:set([]) for i in range(1,n+1)}
e={i:0 for i in range(1,n+1)}
s={i for i in range(1,n+1)}
for _ in range(m):
    a,b = map(int,input().split())
    d[a]|={b}
    d[b]|={a}
    s-={a,b}
if len(s)!=0:
    print("No")
else:
    print("Yes")
    s={1}
    while(n>0):
        t=set([])
        for i in s:
            for j in d[i]:
                if e[j]==0:
                    e[j]=i
                    t|={j}
                    n-=1
        s=t
    for k,v in e.items():
        if k>1:
            print(v)

Solution (Python):
from collections import defaultdict
import queue
d = defaultdict(list)
n,m = [int(i) for i in input().split()]
q=  queue.Queue()
for i in range(m):
    a,b =[int(i) for i in input().split()]
    d[a].append(b)
    d[b].append(a)
l = n-1
arr = [0]*(n+2)

for i in d[1]:
    if arr[i]==0:
        q.put(i)
        arr[i]=1
        l-=1
    
while(not(q.empty())):
    k = q.get()
    for i in d[k]:
        if arr[i]==0 and i!=1:
            arr[i]=k
            q.put(i)
            l-=1
    if l==0:
        break
if l==0:
    print('Yes')
    for i in range(2,n+1):
        print(arr[i])
else:
    print('No')

Solution (Python):
from collections import deque

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

g = [[] for _ in range(N+1)]

for a, b in ab:
    g[a].append(b)
    g[b].append(a)

temp = deque([[1, 0]])
visited = [-1] * (N+1)
visited[0] = 0
visited[1] = 0

while temp:
    q = temp.popleft()
    for i in g[q[0]]:
        if visited[i] == -1:
            temp.append([i, q[1]+1])
            visited[i] = q[0]
if -1 in visited: print('No')
else:
    print('Yes')
    for i in visited[2:]:
        print(i)

Solution (Python):
import queue

def resolve():
    n,m = map(int, input().split())
    signs = [0]*(n+1)
    maps = {}
    for _ in range(m):
        a,b = map(int, input().split())
        if a in maps.keys():
            maps[a].append(b)
        else:
            maps[a] = [b]

        if b in maps.keys():
            maps[b].append(a)
        else:
            maps[b] = [a]

        
        
        
        
        
        
        
        
        
        
    
    remain = set(list(range(1, n+1)))
    q = queue.Queue()
    q.put(1)
    
    while q.empty() == False:
        curr = q.get()
        for i in maps[curr]:
            if signs[i] != 0:
                continue
            signs[i] = curr
            remain.remove(i)
            q.put(i)
    
    if len(remain) == 0:
        signs[1] = 'Yes'
        for i in range(len(signs)):
            if i == 0:
                continue
            print(signs[i])
    else:
        print('No')
            

resolve()

Solution (Python):
from heapq import heapify, heappop, heappush

def dijkstra(start,node,edge):
    d = [2*10**5] * node
    m = [0]*node
    d[start] = 0
    q = [(0,0)]
    heapify(q)
    
    while(len(q) != 0):
      ci, i = heappop(q)
      di = d[i]
      for j in edge[i]:
        if(d[j] > di+1):
          d[j] = di + 1
          heappush(q, (di+1,j))
          m[j] = i+1
    return m

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

    m = dijkstra(0, N, E)
    print("Yes")
    print("\n".join(map(str, m[1:])))

if __name__ == '__main__':
    main()

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

ans = [0]*(N+1)
done = [0]*(N+1)
done[0]=1
done[1]=1

stack = deque([1])

while stack:
  x = stack.pop()
  temp = deque([])
  for i in ab[x]:
    if done[i] == 0:
      done[i] += 1
      ans[i] = x
      stack.appendleft(i)

print('Yes')
for i in range(2,len(ans)):
  print(ans[i])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18


n, m = Is()
AB = TIR(m)
C = [set() for _ in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    C[a].add(b)
    C[b].add(a)

ANS = [INF]*n
visited = [False]*n
def bfs():
    que = deque()
    que.append(0)
    while que:
        x = que.popleft()
        visited[x] = True
        for y in C[x]:
            if not visited[y]:
                ANS[y] = x
                que.append(y)
                visited[y] = True

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

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

queue = deque()
pre = [-1 for _ in range(n)]
dist = [10**10 for _ in range(n)]

dist[0] = 0
queue.append(0)
while queue:
    now = queue.popleft()
    for to in G[now]:
        if dist[to] > dist[now] + 1:
            dist[to] = dist[now] + 1
            pre[to] = now
            queue.append(to)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
from collections import deque
N,M=map(int,input().split())
G=[[]for _ 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)

dist=[-1 for _ in range(N)]
chk=[0 for _ in range(N)]
dist[0]=0
prev=[-1 for _ in range(N)]


que=deque()
que.append((0,-1))

while(len(que)):
    v,p=que.popleft()
    for tmp in G[v]:
        if dist[tmp]!=-1:
            continue
        dist[tmp]=dist[v]+1
        prev[tmp]=v
        que.append((tmp,v))

print("Yes")

for i in range(N):
    if i==0:
        continue
    print(prev[i]+1)

Solution (Python):
N, M = [int(x) for x in input().split()]
path = []
for i in range(N):
  path.append([])
for i in range(M):
  t1, t2 = [int(x) for x in input().split()]
  path[t1-1].append((t1,t2))
  path[t2-1].append((t2,t1))
l = [1]
ans = [1] + [0] * (N-1)
while len(l) > 0:
  t = l.pop(0)
  for i in range(len(path[t-1])):
    if ans[path[t-1][i][1]-1] == 0:
      ans[path[t-1][i][1]-1] = t
      l.append(path[t-1][i][1])
print('Yes')
for i in range(1, N):
  print(ans[i])

Solution (Python):


import sys
import math
import time

import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def bfs(x, n):
  que = deque([x])
  while que:
      node = que.popleft()
      for i in range(len(Edge[node])):
          if(Val[Edge[node][i]] > Val[node]):
              Val[Edge[node][i]] = Val[node]+1
              Dir[Edge[node][i]] = node
          que.append(Edge[node][i])
      Edge[node] = []


sys.setrecursionlimit(10**7)






N, M = map(int,input().split())
INF = N+1

Dir = [0 for i in range(N)]
Val = [INF for i in range(N)]
Val[0] = 0
Edge = [[] for i in range(N)]
ans = 0

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


bfs(0,N)


print("Yes")
for i in range(N-1):
    print(Dir[i+1]+1)

Solution (Python):
from collections import deque
N, M = [int(x) for x in input().split()]
INF = 10**6
dist = [INF] * N
ans = [-1] * N
to = [set() for _ in range(N)]
for _ in range(M):
    A, B = [int(x)-1 for x in input().split()]
    to[A].add(B)
    to[B].add(A)
bfs = deque([(0, 0, -1)])
while len(bfs):
    cur, d, p = bfs.popleft()
    if d >= dist[cur]: continue
    dist[cur] = d
    ans[cur] = p
    for v in to[cur]:
        if d+1 < dist[v]:
            bfs.append((v, d+1, cur))
print('Yes')
for a in ans[1:]:
    print(a+1)

Solution (Python):
from collections import deque

R=lambda: map(int, input().split())

n, m = R()
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = R()
  g[u - 1].append(v - 1)
  g[v - 1].append(u - 1)

r = [None] * (n - 1)
V = [True] + [False] * (n - 1)
q = deque([0])
while q:
  u = q.popleft()
  for v in g[u]:
    if not V[v]:
      V[v] = True
      r[v - 1] = u + 1
      q.append(v)

print(*(['No'],['Yes'] + r)[all(r)], sep='\n')

Solution (Python):
import itertools
from collections import defaultdict
import collections
import math
import sys
import queue
sys.setrecursionlimit(200000)
mod = 1000000007

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

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

tf = [False] * (n + 1)
sirube = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v,0])
    tf[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        before = sub[1]
        for next in graph[now]:
            if tf[next]:
                continue
            tf[next] = True
            if sirube[next] == 0:
                sirube[next] = now
            q.put([next, now])

bfs(1)
for i in range(2, n + 1):
    if sirube[i] == 0:
        print("No")
        exit()

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

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
path_d = defaultdict(list)
result = dict()

for _ in range(m):
    a, b = input().split()
    if a == "1":
        result[b] = a
    elif b == "1":
        result[a] = b
    else:
        path_d[a].append(b)
        path_d[b].append(a)

tmp = list(result.keys())

while path_d:
    tmp2 = list()
    for _a in tmp:
        for _b in path_d[_a]:
            if _b not in result:
                result[_b] = _a
                tmp2.append(_b)
        del path_d[_a]
    tmp = tmp2

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

Solution (Python):
N, M = map(int, input().split())
X = {}
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in X:
        X[a].append(b)
    else:
        X[a] = [b]

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

ans = [0 for _ in range(N)]
ans[0] = 1
que = [[0, X[0]]]
while len(que) > 0:
    f, targets = que.pop(0)
    for t in targets:
        if ans[t] == 0:
            ans[t] = f + 1
            que.append([t, X[t]])

if 0 in ans:
    print("No")
else:
    print("Yes")
    for a in ans[1:]:
        print(a)

Solution (Python):
from collections import deque

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

n, m = map(int, input().split())
table = [[] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
ans = [-1 for i in range(n)]
ans = bfs(0, ans)
if -1 in ans:
    print('No')
else:
    print('Yes')
    for a in ans[1:]:
        print(a+1)

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        route[a].append(b)
        route[b].append(a)
    q = deque([1])
    ans = [None]*(n+1)
    while q:
        parent = q.pop()
        children = route[parent]
        for child in children:
            if ans[child] is None:
                ans[child] = parent
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

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

for i in range(n):
    if len(arr[i])==0:
        print('No')
        sys.exit()

def bfs(d):
    que=deque()
    que.append(0)
    ans=[0]*n
    while que:
        x=que.popleft()
        if x==0:
            for i in arr[x]:
                ans[i]=1
                que.append(i)
        else:
            for i in arr[x]:
                if ans[i]==0 and i!=0:
                    ans[i]=x+1
                    que.append(i)
    print('Yes')
    for i in range(1,n):
        print(ans[i])        

bfs(arr)

Solution (Python):
from collections import deque

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

line = [[] for _ in range(N+1)]
flag = True
ans = [0] * (N+1)

for A,B in AB:
    line[A].append(B)
    line[B].append(A)

def bfs(now):
    que = deque()
    que.append(now)
    while que.__len__() != 0:
        now = que.popleft()
        for ne in line[now]:
            if ans[ne] != 0:
                continue
            ans[ne] = now
            que.append(ne)

bfs(1)
if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    print("\n".join(str(i) for i in ans[2:]))

Solution (Python):
import itertools
from collections import defaultdict
import collections
import math
import sys
import queue
sys.setrecursionlimit(200000)
mod = 1000000007

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

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

tf = [False] * (n + 1)
sirube = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v,0])
    tf[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        before = sub[1]
        for next in graph[now]:
            if tf[next]:
                continue
            tf[next] = True
            if sirube[next] == 0:
                sirube[next] = now
            q.put([next, now])

bfs(1)
for i in range(2, n + 1):
    if sirube[i] == 0:
        print("No")
        exit()

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

Solution (Python):
from collections import defaultdict,deque
n,m = map(int,input().strip().split())
graph = defaultdict(list)
for _ in range(m):
    u,v = map(int,input().strip().split())
    graph[u].append(v)
    graph[v].append(u)

queue = deque()
queue.append(1)

mini_passage = defaultdict(list)
visited = defaultdict(int)
level = 0
while queue:
    temp = []
    while queue:
        x = queue.pop()
        visited[x] = 1
        for neighbour in graph[x]:
                
                if neighbour in mini_passage:
                    if level<mini_passage[neighbour][1]:
                        mini_passage[neighbour] = [x,level]
                        temp.append(neighbour)
                else:
                    mini_passage[neighbour] = [x, level]
                    temp.append(neighbour)
    queue = temp.copy()
    level += 1

if len(mini_passage)<n-1:
    print("No")
else:
    print("Yes")
    for key in range(2,n+1):
        print(mini_passage[key][0])

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


from collections import defaultdict
import queue
connection = defaultdict(lambda: defaultdict(int))

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

c = defaultdict(int)
q = queue.Queue()
d = defaultdict(int)
p = defaultdict(int)

c[0] = 1
d[0] = 0
q.put(0)

while not(q.empty()):
  u = q.get()
  for v in connection[u]:
    if c[v] == 0:
      c[v] = 1
      d[v] = d[u] + 1
      p[v] = u
      q.put(v)
  c[u] = 2
print("Yes")
for i in range(1,N):
  print(p[i] + 1)

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

ans = [-1] * n
ans[0] = 0
stk = [[0] + node[0]]

while stk:
    s = stk.pop(0)
    fr = s[0]
    for i in s[1:]:
        if ans[i] == -1:
            ans[i] = fr + 1
            stk.append([i] + node[i])

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

Solution (Python):
from collections import deque

INF = 10**6
n, m = map(int, input().split())
path = {i: [] for i in range(1, n+1)}
for i in range(m):
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)

dist = [INF for i in range(n+1)]
dist[1] = 0
ans = [0 for i in range(n+1)]
que = deque([1])

while len(que) > 0:
    p = que.popleft()
    for r in path[p]:
        if dist[r] == INF:
            dist[r] = dist[p] + 1
            ans[r] = p
            que.append(r)

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

Solution (Python):
from collections import deque

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

adj_list = [[] for _ in range(n)]

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

distance = [-1] * n
prev = [-1] * n

q = deque()
q.append([0, 0, 0])  

while len(q) > 0:
    room, d, p = q.popleft()
    
    
    

    for n_room in adj_list[room]:
        if distance[n_room] > 0:
            continue
        q.append([n_room, d + 1, room])
        distance[n_room] = d + 1
        prev[n_room] = room

flag = True
for i in range(n):
    if distance[i] < 0:
        flag = False
        break

if flag is True:
    print("Yes")
    for i in range(1, n):
        print(prev[i] + 1)
else:
    print("No")

Solution (Python):

from collections import deque


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    AB = [set() for _ in range(n+1)]
    for a, b in map(lambda x: map(int, x.split()), args[1:]):
        AB[a].add(b)
        AB[b].add(a)

    inf = 10**9
    D = [inf]*(n+1)
    B = [0]*(n+1)

    Q = deque()
    Q.append((1, 0, 0))  
    while Q:
        r, d, p = Q.popleft()
        if d < D[r]:
            D[r] = d
            B[r] = p
            for nr in AB[r]:
                Q.append((nr, d+1, r))

    ret = ['Yes']
    for i in range(2, n+1):
        if D[i] == inf:
            ret = ['No']
            break
        ret.append(str(B[i]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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

aisle_dict = {i+1:[] for i in range(N)}
direction = {1:0}

for i in range(M):
    A, B = list(map(int, input().split()))
    aisle_dict[A].append(B)
    aisle_dict[B].append(A)
    
def calc_next(current_rooms):
    all_next_rooms = []
    for current_room in current_rooms:
        next_rooms = aisle_dict[current_room]
        for room in next_rooms:
            if room not in direction:
                direction[room] = current_room
                all_next_rooms.append(room)
    return all_next_rooms
    
rooms = [1]
while len(direction) < N:
    rooms = calc_next(rooms)

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

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

N, M = [int(x) for x in stdin.readline().rstrip().split()]

par = [i for i in range(N+1)]
rank = [0] * (N+1)
size = [1] * (N+1)


def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
        size[x] = 0

    else:
        par[y] = x
        size[x] += size[y]
        size[y] = 0
        if rank[x] == rank[y]:
            rank[x] += 1


def check_same(x, y):
    return find(x) == find(y)


def check_size(x):
    return size[find(x)]


adj = defaultdict(set)

for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    union(A, B)
    adj[A].add(B)
    adj[B].add(A)

print("Yes")
ans = [0]*(N+1)
visit_p = deque()
visit_p.append((1, 0))
visited = [False]*(N+1)
visited[1] = True
dist = [10**18]*(N+1)

while visit_p:
    now_v, distance = visit_p.popleft()
    for v in adj[now_v]:
        if visited[v]:
            continue

        if distance < dist[v]:
            ans[v] = now_v
        dist[v] = min(dist[v], distance)

        visited[v] = True
        visit_p.append((v, 1+distance))

for k in ans[2:]:
    print(k)

Solution (Python):
class Room:
    def __init__(self, prev=-1, dist=1 << 64):
        self.prev = prev
        self.dist = dist


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

opening = {0}
closing = {0}
guide_points = [-1] * n
while opening:
    next_opening = set()

    for curr_room in opening:
        for next_room in passages[curr_room]:
            if next_room in closing:
                continue

            guide_points[next_room] = curr_room
            next_opening.add(next_room)
            closing.add(next_room)

    opening = next_opening

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

Solution (Python):
import queue

n, m = map(int, input().split())
ng_s = 10 ** 6

d = [[]] * (n+1)
s = [ng_s] * (n+1)
for i in range(1, n+1):
  d[i] = []

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





q = queue.Queue()
q.put(1)
s[0] = 0
s[1] = 0

while not q.empty():
  c = q.get()
  to_list = d[c]
  for j in range(len(to_list)):
    to = to_list[j]
    if s[to] == ng_s and to != 1:
      s[to] = c
      q.put(to)
    
s2 = s[2:]

if min(s2) == ng_s:
  print('No')
else:
  print('Yes')
  for i in range(2, n+1):
    print(s[i])

Solution (Python):
from collections import deque

def bfs(u):
    dist = [-1 for _ in range(n)]
    dist[u] = 0
    que = deque([])
    que.append(u)

    while que:
        v = que.popleft()
        for nv in G[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v] + 1
            que.append(nv)
            D[nv] = v
    return dist


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)

D = [-1]*n
bfs(0)
print('Yes')
for d in D[1:]:
    print(d+1)

Solution (Python):
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import networkx as nx

import heapq
import sys

input = sys.stdin.readline


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

def dijkstra_heap(s,edge):
    
    d = [10**20] * N
    used = [True] * N 
    d[s] = 0
    used[s] = False
    edgelist = []
    path = [-1] * N
    for a,b in edge[s]:
        path[b] = s
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:                
            if used[e[1]]:
                if path[e[1]] == -1:
                    path[e[1]] = v
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d, path

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

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

d, path = dijkstra_heap(0, edge)

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

Solution (Python):

from collections import deque

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



def bfs(u):
    queue = deque([u])
    d = [None] * (n+1) 
    r = [None] * (n+1) 
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                r[i] = v
                queue.append(i)
    return d, r


d, r = bfs(1)


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

Solution (Python):
N,M = map(int,input().split())
r = [[] for _ in range(N)]
for _ in range(M):
    A_,B_ = map(int,input().split())
    r[A_-1].append(B_-1)
    r[B_-1].append(A_-1)

ans = [0]*N
t = [0]*N
p = [0]

def k(p,t,ans):
    s = []
    for i in p:
        a = r[i]
        for z in a:
            if t[z] == 0:
                s.append(z)
                ans[z] = i
                t[z] = 1
    p = s
    return p,t,ans

while len(p) > 0:
    p,t,ans = k(p,t,ans)

for i in range(N-1):
    if r[i+1] == 0:
        print('No')
        exit()
print('Yes')
for i in range(N-1):
    print(ans[i+1]+1)

Solution (Python):
from collections import deque

n,m=map(int,input().split())
l=[[] for i in range(n)]
ans=[-1]*n
flag=[False]*n
q=deque([0])
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    l[a].append(b)
    l[b].append(a)
flag[0]=True
while len(q)>0:
    now=q[0]
    q.popleft()
    for i in l[now]:
        if flag[i]:
            continue
        ans[i]=now
        flag[i]=True
        q.append(i)
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(ans[i]+1)