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 collections import deque

INF = 100000000


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

maze = [[] for i in range(N)]
for i in range(M):
    ai,bi = map(int,input().split())
    maze[ai-1].append(bi-1)
    maze[bi-1].append(ai-1)




def bfs(N,M,maze):
    que = deque([])
    
    d = [INF for i in range(N)]

    
    que.append(0)
    d[0] = 0

    
    while len(que) > 0:
        
        p = que.popleft()
        
        for i in maze[p]:
            
            if d[i] == INF:
                que.append(i)
                d[i] = p
    
    return d
res = bfs(N,M,maze)

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

Solution (Python):
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()



N, M = In.ints()

conn = [set() for j in range(N+1)]

for i in range(M):
    A, B = In.ints()

    conn[A].add(B)
    conn[B].add(A)

que = deque([1])
selection = [0]*(N+1)
seen = set([1])

while len(que)>0:
    el = que.popleft()

    for nextVert in conn[el]:
        if nextVert not in seen:
            selection[nextVert] = el 
            seen.add(nextVert)
            que.append(nextVert)

Out.str("Yes")
for i in range(2, len(selection)):
    Out.int(selection[i])



if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n, m = LI()
    ab = LIR_(m)
    def Dijkstra(num, start, vedge):
        """ vedge は DAG の 重みとして vedge[from] = (to, value)　としておくこと """
        """ DAGでない場合は vedge[from] と vedge[to] の両方を作ること """
        """ dist[i] は start から i までの最短距離 """

        dist = [float("inf") for i in range(num)]
        dist[start] = 0
        q = [[dist[start], start]]
        while q:
            du, u = heappop(q)
            for j, k in vedge[u]:
                if dist[j] > du + k:
                    dist[j] = du + k
                    heappush(q, [dist[j], j])
        return dist
    edg = defaultdict(list)
    for a, b in ab:
        edg[a].append((b,1))
        edg[b].append((a,1))
    dist = Dijkstra(n, 0, edg)
    if inf in dist:
        print("No")
        return
    print("Yes")
    ans = [None] * n
    q = deque()
    q.append(0)
    while q:
        p = q.popleft()
        for e, _ in edg[p]:
            if ans[e] == None:
                if dist[p] + 1 == dist[e]:
                    ans[e] = p
                    q.append(e)
    for i in ans[1:]:
        print(i+1)
    return



if __name__ == '__main__':
    solve()

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

arrows = [-1] * N
queue = [0]
seen = {0}
while queue:
    new = []
    for cur in queue:
        for nei in graph[cur]:
            if nei in seen:
                continue
            seen.add(nei)
            new.append(nei)
            arrows[nei] = cur
    queue = new

if all(a != -1 for a in arrows[1:]):
    print('Yes')
    for a in arrows[1:]:
        print(a + 1)
else:
    print('No')

Solution (Python):
n,m = map(int,input().split())
graph = {i:[] for i in range(n)}
ans = {i:-1 for i 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)
  
from collections import deque

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

while queue:
  node,parent = queue.popleft()
  for i in graph[node]:
    if i ==parent:
      continue
    elif ans[i] != -1:
      continue
    ans[i] = node
    queue.append((i,node))

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

Solution (Python):
from collections import deque


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

    INF = 100000000

    distance = [INF for i in range(N)]
    visited = [False] * N
    
    visited[0] = True
    distance[0] = 0

    def bfs():
        queue = deque([0])
        distance[0] = 0

        while queue:
            x = queue.popleft()
            for y in graphs[x]:
                if visited[y]:
                    continue
                else:
                    distance[y] = x
                    visited[y] = True
                    queue.append(y)
        return distance

    d = bfs()
    for i in range(N):
        if not visited[i]:
            print("No")
            exit()
    print("Yes")
    for i in range(1, N):
        print(d[i]+1)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')
from collections import deque
def solve():
    n, m = MI()
    ans = [-1] * n
    to = [[] for _ in range(n)]
    for i in range(m):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
    
    q = deque([0])
    used = [0] * n
    used[0] = 1
    while len(q) > 0:
        current = q.popleft()
        for next in to[current]:
            if used[next]: continue
            if ans[next] == -1:
                q.append(next)
                ans[next] = current + 1
                used[next] = 1
        
    if sum(used) == n:
        print('Yes')
        printlist(ans[1:])
    else:
        print('No')

if __name__ == '__main__':
    solve()

Solution (Python):

from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]

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

ans=[-1 for i in range(N)]
queue=deque()
queue.append(0)

while len(queue)>0:
    u=queue.popleft()
    near_u=G[u]
    for k in range(len(near_u)):
        if ans[near_u[k]]==-1:
            ans[near_u[k]]=u+1
            queue.append(near_u[k])

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

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


v = [[i,-1] for i in range(n+1)]
v[1][1] = 0
for i in range(m):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
dq = deque([])
dq.append(v[1])

while dq:
    t = list(deque.popleft(dq))
    
    for i in t[1:]:
        if v[i][1] == -1:
            v[i][1] = t[0]
            dq.append(v[i])
print("Yes")
for i in range(n-1):
    print(v[i+2][1])

Solution (Python):
import queue
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
x = [[] for _ in range(n+1)]
ans = [0]*(n+1)
for _ in range(m):
  ai,bi = map(int,input().split())
  x[ai].append(bi)
  x[bi].append(ai)
q = queue.Queue()
q.put(1)
while not q.empty():
  i = q.get()
  for nx in x[i]:
    if ans[nx] == 0:
      ans[nx] = i
      q.put(nx)
print("Yes")
for i in range(2,n+1):
  print(ans[i])

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

def bfs(x):
  qu=deque([])
  qu.append(x)
  ans=[0]*(n+1)
  ans[1]=1
  while qu:
    now=qu.popleft()
    
    for i in edge[now]:
      if ans[i]==0:
        qu.append(i)
        ans[i]=now
  return ans
ans=bfs(1)
ans.pop(0)
if 0 in ans:
  print("No")
else:
  print("Yes")
  for i in range(1,len(ans)):
    print(ans[i])

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

from collections import deque
que = deque([])
dist= [-1]*n
dist[0] = 0
que.append(0)
par = [-1] * n
while len(que)>0:
    node = que.popleft()
    for next_node in edge[node]:
        if dist[next_node] != -1:
            continue 
        dist[next_node] = dist[node] + 1
        par[next_node] = node  + 1
        que.append(next_node)
if -1 in dist:
    print("No")
else:
    print("Yes")
    print(*par[1:],sep = "\n")

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

cnt=0
next={1}
while len(next)>0:
    tmp=set()
    for p in next:
        for q in x[p]:
            if lift[q]==-1:
                tmp.add(q)
                lift[q]=p
            x[q].remove(p)

    next=tmp

if -1 in x[2:]: print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(lift[i])

Solution (Python):
import queue
import numpy as np
from scipy import sparse


N, M = list(map(int, input().split()))
links = {}
for i in range(M):
    A, B = list(map(int, input().split()))
    A -= 1
    B -= 1
    if A not in links:
        links[A] = []
    links[A].append(B)

    if B not in links:
        links[B] = []
    links[B].append(A)

que = queue.Queue()
que.put(0)
nearest = np.ones(N, np.int) * -1
while not que.empty():
    p = que.get()
    for q in links[p]:
        if q == 0 or nearest[q] != -1:
            continue
        que.put(q)
        nearest[q] = p

if (nearest[1:] != -1).all():
    print("Yes")
    for i in range(1, N):
        print(nearest[i] + 1)
else:
    print("No")

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

v = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in v:
        v[a] = [b]
    else:
        v[a].append(b)

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

st = [1]

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

while True:
    buf = set()
    updates = {}
    for s in st:
        nex = v[s]
        for to in nex:
            if ans[to-1] != -1:
                continue
            else:
                buf.add(to)
                
                updates[to-1] = s
    for u in updates.keys():
        ans[u] = updates[u]
    st = buf
    
    if len(buf) == 0:
        break

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

Solution (Python):
import queue

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


dist=[-1]*n
dist[0]=0
q=queue.Queue()
q.put(0)

while not q.empty():
    now=q.get()
    for next in G[now]:
        if dist[next]>=0:
            continue
        dist[next]=now
        q.put(next)

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

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

q = [0]
i = 1
ans = [-1 for _ in range(n)]
while(len(q) > 0):
  qq = []
  for v in q:
    for u in e[v]:
      if ans[u] == -1:
        ans[u] = v
        qq.append(u)
  q = qq[:]
  i += 1

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

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

def main():
    N, M = map(int, input().split(' '))
    lines = sys.stdin.read().split('\n')
    A = []
    B = []
    for line in lines:
        if not line:
            continue
        a, b = map(int, line.split(' '))
        A.append(a)
        B.append(b)
    adj = defaultdict(list)
    for val in zip(A,B):
        a, b = val
        adj[a].append(b)
        adj[b].append(a)

    source = defaultdict(int)
    start = 1
    source[1] = 1
    queue = deque([1])
    while len(queue) > 0:
        room = queue.pop()
        for adj_room in adj[room]:
            if adj_room in source:
                continue
            source[adj_room] = room
            queue.appendleft(adj_room)
    if len(source) != N:
        print('No')
        return
    print('Yes')
    for i in range(2, N+1):
        print(source[i])



if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
X = defaultdict(list)
for i in range(M):
    Ai, Bi = map(lambda s: int(s) - 1, input().split())
    X[Ai].append(Bi)
    X[Bi].append(Ai)

V = [False] * N
P = [0] * N
A = [0] * N
Q = deque([0])
V[0] = True
while len(Q) > 0:
    r = Q.popleft()
    for nr in X[r]:
        if V[nr] == True:
            continue
        V[nr] = True
        P[nr] = P[r] + 1
        A[nr] = r + 1
        Q.append(nr)

print('Yes')
for i in range(1, N):
    print(A[i])

Solution (Python):

import sys

YES = "Yes"  


def bfs(N, edges):
    from collections import deque
    par = [None] * (N + 1)
    que = deque([(1, 1)])
    while que:
        p, n = que.popleft()
        if par[n] is not None:
            continue
        par[n] = p
        for nn in edges[n]:
            if par[nn] is not None:
                continue
            que.append((n, nn))
    return par

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    edges = [[] for _ in range(N+1)]
    for a, b in zip(A, B):
        edges[a].append(b)
        edges[b].append(a)
    par= bfs(N, edges)
    return par[2:]



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))
    print('Yes')
    print(*solve(N, M, A, B), sep='\n')

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
from collections import deque

N,M = map(int,input().rstrip().split(" "))
A = [[] for i in range(N)]
closest = [-1 for i in range(N)]
closest[0] = 0
ans = [-1 for i in range(N)]
que = deque([[0,0]])
for i in range(M):
    q,qq = map(int,input().rstrip().split(" "))
    A[q - 1].append(qq -1)
    A[qq - 1].append(q - 1)
while len(que) != 0:
    for i in A[que[0][0]]:
        if closest[i] == -1:
            closest[i] = que[0][1] + 1
            ans[i] = que[0][0] + 1
            que.append([i,que[0][1] + 1])
    que.popleft()
print("Yes")
for i in range(N - 1):
    print(ans[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())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
q = deque()
q.append(0)

ans = [-1 for _ in range(n)]
ans[0] = 0

visited = set({})

while q:
    start = q.popleft()
    visited.add(start)
    for i in graph[start]:
        if ans[i] == -1:
            q.append(i)
            ans[i] = start
                
if -1 not in ans:
    print('Yes')
    for i in range(1, n):
        print(ans[i] + 1)
else:
    print('No')

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

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

for x,y in a:
    b[x-1].append(y-1)
    b[y-1].append(x-1)


import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    ans=[0]*n
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    ans[y]=x+1


        return ans
    return bfs()

x=tree(0)

for i in range(1,n):
    if x[i]==0:
        print('No')
        exit()

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

Solution (Python):
from collections import deque

def bfs(g_list, visited):
    q = deque([1])
    visited[1] = 0
    while q:
        curr_room = q.popleft()
        for next_room in g_list[curr_room]:
            if visited[next_room] >= 0:
                continue
            visited[next_room] = curr_room
            q.append(next_room)


def main():
    n, m = map(int, input().split()) 
    g_list = [ [] for _ in range(n+1)]
    visited = [-1] * (n+1)
    visited[0] = 0
    
    for i in range(m):
        a, b = map(int, input().split()) 
        g_list[a].append(b)
        g_list[b].append(a)
    bfs(g_list,visited)
    
    ans = visited[2:]
    if -1 in ans:
        print('No')
    else:
        print('Yes')
        for a in ans:
            print(a)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
n, m = map(int, input().split())

G = defaultdict(lambda:[])

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

ddd = {}
for i in range(n):
    ddd[i] = False

parent = [-1]*n 
order = []

def bfs(i):
    parent[i] = -1
    stack = deque()
    u = i
    stack.append(u)
    ddd[i] = True
    while stack:
        x = stack.popleft()
        order.append(x)
        for v in G[x]:
            if v == parent[x]:
                continue
            if parent[v] != -1:
                continue
            parent[v] = x
            ddd[v] = True
            stack.append(v)
            
bfs(0)

b = True
for i in range(n):
    if ddd[i]:
        continue
    else:
        b = False
        print(i)
if not b:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        print(parent[i]+1)

Solution (Python):
import queue
N,M = map(int,input().split())
adj = [[]for i in range(N+1)]
parent = [-1] * (N+1)
for m in range(M):
    a,b = map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)
q = queue.Queue()
q.put((1,0)) 
while(not q.empty()):
    x, p = q.get()
    if parent[x] != -1:
        continue
    parent[x] = p
    for next in adj[x]:
        if parent[next] == -1:
            q.put((next,x))


print ('Yes')
for p in parent[2:]:
    print(p)

Solution (Python):
import sys


import math
import collections





import copy

import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
MOD2 = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n, m = ns()

    edge = [[] for _ in range(n)]
    for i in range(m):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)

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

    que = queue.Queue()
    que.put(0)
    visited[0] = 0

    while que.qsize() > 0:
        current = que.get()

        for next in edge[current]:
            if visited[next] == -1:
                visited[next] = current
                que.put(next)

    if min(visited) > -1:
        print("Yes")
        for i in range(1, n):
            print(visited[i] + 1)
    else:
        print("No")


if __name__ == '__main__':
    main()

Solution (Python):
from queue import Queue
N, M = [int(i) for i in input().split()]
al = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = [int(i) for i in input().split()]
    al[A].append(B)
    al[B].append(A)
q = Queue()
q.put(1)
seen = [False] * (N + 1)
seen[1] = True
while not q.empty():
    v = q.get()
    for nv in al[v]:
        if not seen[nv]:
            q.put(nv)
            seen[nv] = v
print("Yes")
for i in seen[2:]:
    print(i)

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

d=deque()
d.append(0)

while d:
    room = d.popleft()
    for i in g[room]:
        if v[i]==1:
            continue

        d.append(i)
        v[i]=1
        f[i]=room

for i in range(n):
    if v[i]==0:
        print('No')
        exit()
print('Yes')
for i in range(1,n):
    print(f[i]+1)

Solution (Python):
import queue

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

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

for ab in AB:
    a,b = ab[0], ab[1]
    nexts[a].append(b)
    nexts[b].append(a)

ans = [0] * (N+1)

q = queue.Queue()
q.put(1)
while q.qsize() > 0:
    k = q.get()
    for i in nexts[k]:
        if ans[i] == 0:
            q.put(i)
            ans[i] = k

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

Solution (Python):

import heapq


def dijkstra(n, s, edge):
    d = [(float('inf'), i, -1) for i in range(n + 1)]
    d[s] = (0, s, 0)
    q = [(0, s, 0)]
    
    while q:
        dist, curr, prev = heapq.heappop(q)
        if d[curr][0] < dist:
            continue
            
        for e in edge[curr]:
            if d[e][0] > dist + 1:
                d[e] = (dist + 1, e, curr)
                heapq.heappush(q, d[e])
    
    return d


def submit():
    n, m = [int(e) for e in input().split()]
    edge = {i: [] for i in range(1, n + 1)}
    for _ in range(m):
        a, b = [int(e) for e in input().split()]
        edge[a].append(b)
        edge[b].append(a)

    
    d = dijkstra(n, 1, edge)
    
    print("Yes")
    for i in range(2, n + 1):
        print(d[i][-1])


if __name__ == "__main__":
    submit()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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


USED = [False] * (N + 1)
MARK = [None] * (N + 1)

Q = [1]
Q = deque(Q)

while Q:
    node = Q.popleft()

    for v in PATH[node]:
        if USED[v]:
            continue

        MARK[v] = node
        USED[v] = True
        Q.append(v)

print("Yes")
print("\n".join(map(str, MARK[2:])))

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

q = deque([0])
counts = [-1] * N
counts[0] = 0
while q:
    state = q.popleft()
    c = counts[state]
    for np in P[state]:
        if counts[np] < 0:
            counts[np] = state
            q.append(np)

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

Solution (Python):
from heapq import heappop,heappush
N,M = map(int,input().split())
T = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)

INF = float("inf")
D = [INF]*N
A = [0]*N
Q = [[0,0,-1]]
while Q:
    d,v,p = heappop(Q)
    if d >= D[v]:continue
    A[v] = p
    D[v] = d
    d += 1
    for c in T[v]:
        if c == p:continue
        if d >= D[c]:continue
        heappush(Q,[d,c,v])
if INF in D:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(A[i]+1)

Solution (Python):
n,m=map(int,input().split())
parent=[]
distances=[]
edges=[]
visited=set()
visited.add(1)
for i in range(n):
  edges.append([])
for i in range(m):
  edges.append([])
  a,b=map(int,input().split())
  edges[a].append(b)
  edges[b].append(a)
for i in range(n+1):
  parent.append(0)
  distances.append(-1)
parent[0]=-1
parent[1]=-1
nextdistancelist=[1]
distancelistcopy=[]
for currentdistance in range(1,n+1):
  distancelistcopy=[]
  for k in nextdistancelist:
    visited.add(k)
    for r in edges[k]:
      if r in visited:
        continue
      if parent[r]!=0:
        continue
      parent[r]=k
      distancelistcopy.append(r)
  nextdistancelist=distancelistcopy.copy()
failflag=0
for i in range(2,n+1):
  if parent[i]==0:
    failflag=1
    break
if failflag==1:
  print('No')
else:
  print('Yes')
  for i in range(2,n+1):
    print(parent[i])

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

ans = [-1]*(n)

q = deque([])

q.append((0,-1))
while q:
    now,bef = q.popleft()

    for nex in e[now]:
        if nex == bef:
            continue
        if ans[nex] == -1:
            ans[nex] = now+1
            q.append((nex,now))
print("Yes")
for i in ans[1:]:
    print(i)

Solution (Python):
import queue

n,m=map(int,input().split())
path=[[] for i in range(n+1)]
used=[False]*(n+1)
parent=[0]*(n+1)
parent[0]=1
parent[1]=1

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

q=queue.Queue()
q.put(1)

while not q.empty():
    a=q.get()
    for p in path[a]:
        if not used[p]:
            used[p]=True
            parent[p]=a
            q.put(p)

if 0 in parent:
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(parent[i])

Solution (Python):
from collections import deque


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


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

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

q = deque([1])
done = [True for _ in range(N + 1)]
done[1] = False

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

while q:
    num = q.popleft()
    for e in edge[num]:
        if done[e]:
            ans[e] = num
            done[e] = False
            q.append(e)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def f(data):
    tmp=links[data[0]]
    for x in tmp:
        if ans[x]==-1:
            ans[x]=data[0]
            q.append([x, data[0]])

from collections import deque

N, M=map(int, input().split())
links=[[] for _ in range(N+1)]
for _ in range(M):
    A, B=map(int, input().split())
    links[A].append(B)
    links[B].append(A)
    
q=deque()
q.append([1, -1])
ans=[-1]*(N+1)
ans[0]=0
ans[1]=0
while len(q)>0:
    data=q.popleft()
    f(data)
    
print('Yes')
print(*ans[2:], sep='\n')

Solution (Python):
from collections import deque, defaultdict

n, m = list(map(int, input().split()))
d = defaultdict(list)
for i in range(m):
    data = list(map(int, input().split()))
    d[data[0]].append(data[1])
    d[data[1]].append(data[0])

mindist = defaultdict(lambda: 1000000)
mindist[1] = 0
sign = defaultdict(int)

dq = deque()
dq.append([1, 0])
while len(dq) > 0:
    room, dist = dq.popleft()
    for nroom in d[room]:
        if dist + 1 < mindist[nroom]:
            mindist[nroom] = dist + 1
            sign[nroom] = room
            dq.append([nroom, dist + 1])

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