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 Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)




ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))




def bfs(s,n,node):
    check=[False for _ in range(n)]
    check[s]=True
    queue=[n for _ in range(n)]
    now=0
    queue[now]=s
    ans=[-1 for _ in range(n)]
    ans[0]=[0]
    last_ind=1
    while last_ind<n:

        
        if now>=n or queue[now]==n:
            return []

        for i in node[queue[now]]:
            edge=i[0]
            
            ind=i[1]
            if check[edge]:
                continue

            queue[last_ind]=edge
            last_ind+=1
            
            
            ans[edge]=queue[now]
            check[edge]=True
        now+=1
        
        
        
    return ans



n,m=input_list()
node=[[] for _ in range(n)]
for i in range(m):
    u,v=input_list()
    u-=1
    v-=1
    node[u].append([v,i])
    node[v].append([u,i])



ans=bfs(0,n,node)
if len(ans)==0:
    print("No")
    exit()

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

Solution (Python):
from collections import deque

def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited



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

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

visited = bfs(graph,N,0)

if all(visited[1:]):
    print("Yes")
    print(*visited[1:], sep="\n")
else:
    print("No")

Solution (Python):
from collections import deque

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

checked = [False for _ in range(N)]
queue = deque([0])
checked[0] = True
ans = [0 for _ in range(N)]
while queue:
    now = queue.popleft()
    for i in X[now]:
        if not checked[i]:
            ans[i] = now +1
            queue.append(i)
            checked[i] = True
for i in range(N):
    if i == 0:
        print('Yes')
    else:
        print(ans[i])

Solution (Python):
import heapq

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

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

ds = [float('inf')]*(N+1)
ds[1] = 0
h = []
heapq.heappush(h,[0,1])

while(len(h) > 0):
  tmp = heapq.heappop(h)
  v = tmp[1]
  if ds[v] < tmp[0]:
    continue
  for j in nl[v]:
    if ds[j] > ds[v] + 1:
      ds[j] = ds[v] + 1
      rlt[j] = v
      heapq.heappush(h,[ds[j],j])

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

Solution (Python):
from collections import deque

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

graph = [[] for _ in range(n + 1)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    graph[a].append(b)
    graph[b].append(a)

inf = 100100100
ans = [[inf, inf] for _ in range(n + 1)]
ans[0] = [0, 0]
ans[1] = [0, 0]

q = deque([1])
while q:
    now = q.popleft()
    depth = ans[now][1]
    for x in graph[now]:
        if ans[x][0] == inf:
            q.append(x)
            if ans[x][1] > depth + 1:
                ans[x][0] = now
                ans[x][1] = depth + 1

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

Solution (Python):
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])

for x in s:
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)

if len(di)!=n:
    print("No")
    exit()

print("Yes")
for x in range(2,n+1):
    print(di[x][0])

Solution (Python):

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
graph = [[] for _ in range(N+1)]  
for _ in range(M):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

def bfs(x):
    dist = [None] * (N+1)
    que = deque([1])
    dir = [None] * (N+1)
    popleft = que.popleft; append = que.append    
    while que:
        x = popleft()
        d = dist[x]
        for next in graph[x]:
            if dir[next] != None:
                continue
            dir[next] = str(x)
            append(next)
    return dir

dir = bfs(1)
print('Yes')
print('\n'.join(dir[2:]))

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

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    l = [[] for _ in range(n)] 
    dic = {}
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                l[i].append(v)
                dic[i] = v
    return d,l,dic
d,l,dic = bfs(0)
if None in d:
    print("No")
else:
    print("Yes")
    l.remove(l[0])
    [print(i[0]+1) for i in l]

Solution (Python):

import sys
from collections import deque

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

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

for i in range(M):
    A, B = map(int, input().split())
    link[A-1].append(B-1)
    link[B-1].append(A-1)
visited = [False for _ in range(N)]
visited[0] = True

Q = [0]
mark = [0 for i in range(N)]

while Q:
    
    v = Q.pop(0)
    for i in link[v]:
        if not visited[i]:
            visited[i] = True
            mark[i] = v
            Q.append(i)

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

Solution (Python):
from collections import deque

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

que = deque([0])
dist = [-1] * N
dist[0] = 0
pre = [0] * N

while que:
    c = que.popleft()
    for i in arr[c]:
        if dist[i] != -1:
            continue
        dist[i] = 0
        pre[i] = c
        que.append(i)

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

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

N, M = map(int, input().split())
graph = defaultdict(list)


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


visited = [False] * (N + 1)


visited[0] = True
visited[1] = True


que = deque([1])

while que:
    
    node = que.popleft()

    
    for n in graph[node]:
        if not visited[n]:
            visited[n] = node
            que.append(n)


visited = visited[2:]


if all(visited):
    print("Yes")
    print(*visited, sep="\n")
else:
    print("No")

Solution (Python):
from collections import deque

N, M = map(int, input().split())
arr = [[] for n in range(N)]
que = deque([1])

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

dist = [-1] * N
dist[0] = 0
arr2 = [0] * (N - 1)

print("Yes")
while que:
    c = que.popleft()
    for i in arr[c - 1]:
        if dist[i - 1] != -1:
            continue

        dist[i - 1] = 0
        arr2[i - 2] = c
        que.append(i)

for i in arr2:
    print(i)

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

n, m = list(map(int, input().split()))
edge = {}
for i in range(m):
    ai, bi = list(map(int, input().split()))
    if ai in edge:
        edge[ai].append(bi)
    else:
        edge[ai] = [bi,]
    if bi in edge:
        edge[bi].append(ai)
    else:
        edge[bi] = [ai,]


is_visited = np.zeros((n+1,), dtype=np.bool)
parent = np.zeros((n+1,), dtype=np.int)

q = deque()
q.append(1)
is_visited[1] = True
while len(q) != 0:
    node = q.popleft()
    for child in edge[node]:
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)

print('Yes')
print('\n'.join(list(map(str, list(parent[2:])))))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
q = deque([1])
p = [0]*(n+1)
while q:
    v = q.popleft()
    for u in G[v]:
        if p[u] == 0:
            p[u] = v
            q.append(u)
print("Yes\n"+"\n".join(map(str, p[2:])))

Solution (Python):
from collections import defaultdict

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

graph = defaultdict(set)

for _ in range(m):
    a, b = list(map(int, input().split()))
    graph[a].add(b)
    graph[b].add(a)



seen = [False for _ in range(n + 1)]  
todo = set()  
ans = defaultdict(int)
seen[1] = True
todo.update(graph[1])
for d in graph[1]:
    ans[d] = 1  
    seen[d] = True

while len(todo) > 0:
    todo_next = set()
    for v in todo:
        for d in graph[v]:
            if seen[d]:
                continue
            seen[d] = True
            todo_next.add(d)
            ans[d] = v
    todo = todo_next

if not all(seen[1:]):
    print("No")
    exit()

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

Solution (Python):
from collections import deque


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

INF = 10 ** 10
ds = [INF] * (N+1)
marks = [0] * (N+1)

nodes = [None] * (N+1)

for AB in ABs:
    A, B = AB
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)

    B, A = A, B
    if nodes[A] is None:
        nodes[A] = []
    nodes[A].append(B)



queue = deque([1])
visited = [0] * (N+1)
visited[1] = 1



marks = [0] * (N+1)
parent = 1

while len(queue) > 0:
    p = queue.popleft()
    
    
    
    
    for n in nodes[p]:
        if visited[n] == 0:
            visited[n] = 1
            marks[n] = p
            queue.append(n)

print('Yes')
for mark in marks[2:]:
    print(mark)

Solution (Python):
import collections
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
q = collections.deque()
q.append(0)
dist = [-1]*N
dist[0] = 0
while len(q) != 0:
    v = q.popleft()
    for w in graph[v]:
        if dist[w] > -1:
            continue
        dist[w] = v + 1
        q.append(w)
print('Yes')
for i in range(1,N):
    print(dist[i])

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

from collections import defaultdict
from heapq import *

def solve(N, M, AB):
    rs = defaultdict(set)
    for a, b in AB:
        rs[a].add(b)
        rs[b].add(a)
    h = []
    t = {1: 0}
    heappush(h, (0, 1))
    while h:
        d, x = heappop(h)
        for dx in rs[x]:
            if dx not in t:
                t[dx] = x
                heappush(h, (d + 1, dx))
    return t

result = solve(N, M, AB)

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

Solution (Python):
from collections import deque

n, m = list(map(int, input().split(' ')))
graph = {}

for i in range(m):
    a, b = list(map(int, input().split(' ')))

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

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

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

que = deque()

for c in graph[1]:
    ans[c-1] = 1
    que.appendleft(c)

while len(que) != 0:
    target = que.pop()
    candidates = graph[target]

    for c in candidates:
        if c != 1 and ans[c - 1] == -1:
            ans[c - 1] = target
            que.appendleft(c)

ans = ans[1:]

if -1 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)

Solution (Python):
n, m = list(map(int, input().split()))
root = [[] for _ in range(n)]
answer = [-1]*n
answer[0]=0
for i in range(m):
    c = list(map(int, input().split()))
    root[c[1]-1].append(c[0]-1)
    root[c[0]-1].append(c[1]-1)
count = 1  
queue = [0]

newqueue = []
while(count < n and len(queue) != 0):
    for j in queue:
        for rootnum in root[j]:
            if(answer[rootnum] == -1):
                answer[rootnum] = j
                newqueue.append(rootnum)
                count += 1
	
    queue = newqueue[:]
    newqueue = []
if(count < n):
    print('No')
else:
    print('Yes')
    for l in range(n-1):
        print(answer[l+1]+1)

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


def main():
    n, m = map(int, input().split())
    lst = [[] for _ in range(n + 1)]
    ans = [0] * (n + 1)
    que = dq()
    for _ in range(m):
        a, b = map(int, input().split())
        lst[a].append(b)
        lst[b].append(a)

    limit = 10 ** 5
    d = {i: limit + 1 for i in range(1, n + 1)}
    d[1] = 0
    que.append(1)
    while que:
        visit = que.popleft()
        for next_v in lst[visit]:
            if d[next_v] > d[visit] + 1:
                d[next_v] = d[visit] + 1
                que.append(next_v)
                ans[next_v] = visit

    if all([i != 0 for i in ans[2:]]):
        print('Yes')
        print(*ans[2:], sep='\n')
    else:
        print('No')


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
l=[[] for _ 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)

from collections import deque

p=[0]*n
ans=[0]*n
d=deque()
d.append(0)
while len(d)!=0:
    now=d.popleft()
    for to in l[now]:
        if p[to]==0:
            p[to]=p[now]+1
            d.append(to)
            ans[to]=now
print("Yes")
for i in range(1,n):
    print(ans[i]+1)

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

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

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

Solution (Python):
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
c = []
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    near[t[0][i]] = 0
    c.append(t[0][i])
while len(c) > 0:
    e = c[0]
    for j in range(len(t[e])):
      if near[t[e][j]] == -1:
        near[t[e][j]] = e
        c.append(t[e][j])
    del c[0]
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
q = deque([1])
p = [0]*(n+1)
while q:
    v = q.popleft()
    for u in G[v]:
        if p[u] == 0:
            p[u] = v
            q.append(u)
print("Yes\n"+"\n".join(map(str, p[2:])))

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

def main():
    n,m = map(int,input().split())
    arr = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        arr[a-1].append(b-1)
        arr[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = {i:0 for i in range(1, n)}
    while q:
        now = q.popleft()
        for i in arr[now]:
            if i == 0:
                continue
            if ans[i] == 0:
                ans[i] = now+1
                q.append(i)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

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


class BreadthFirstSearch:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.adj_list = [[] for _ in range(self.n)]

    
    def add_edge(self, start, end, undirected=True):
        self.adj_list[start].append(end)
        if undirected:
            self.adj_list[end].append(start)

    
    def search(self, start_node):
        order = [-1] * self.n  
        parent = [-1] * self.n  
        depth = [-1] * self.n  
        q = deque([(start_node, -1, 0)])  
        num = 0  
        while len(q) > 0:
            v, p, d = q.popleft()
            if order[v] < 0:  
                order[v] = num
                parent[v] = p
                depth[v] = d
                num += 1
                for u in self.adj_list[v]:
                    if order[u] >= 0:
                        continue
                    q.append((u, v, d+1))
        return order, parent, depth


def get_result(data):
    N, M = data[0]
    A = data[1:]
    solver = BreadthFirstSearch(N)
    for val in A:
        solver.add_edge(val[0]-1, val[1]-1)
    order, parent, depth = solver.search(0)
    print('Yes')
    for p in parent[1:]:
        print(p+1)
    return None


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)

Solution (Python):
from collections import deque

def bfs(maze, a):
  queue = deque([1])

  while queue:
    x = queue.popleft()
    for i in maze[x - 1]:
      if(a[i - 1] == -1):
        a[i - 1] = x
        queue.append(i)
      
if __name__ == '__main__':
  n, m = map(int, input().split())
  maze = [[] for i in range(n)]
  for i in range(m):
    a, b = map(int, input().split())
    maze[a - 1].append(b)
    maze[b - 1].append(a)

  visit = [(-1)] * n
  visit[0] = 0

  bfs(maze, visit)

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

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

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

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)

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

stack=deque([1])
visited=[-1 for i in range(N+1)]
visited2=[-1 for i in range(N+1)]
visited[1]=0

while stack:
    x=stack.popleft()
    for i in graph[x]:
        if visited[i]==-1:
            visited[i]=visited[x]+1
            visited2[i]=x
            stack.append(i)
print('Yes')
print(*visited2[2:],sep='\n')

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

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])

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

N, M = map(int, input().split())
graph = defaultdict(list)


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


visited = [False] * (N + 1)


visited[0] = True
visited[1] = True


que = deque([1])

while que:
    
    node = que.popleft()

    
    for n in graph[node]:
        if not visited[n]:
            visited[n] = node
            que.append(n)


visited = visited[2:]

if all(visited):
    print("Yes")
    print(*visited, sep="\n")
else:
    print("No")

Solution (Python):
from collections import deque

def main():
    n,m = map(int,input().split())
    arr = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        arr[a-1].append(b-1)
        arr[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.popleft()
        for i in arr[now]:
            if ans[i] == -1:
                ans[i] = now+1
                q.append(i)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

Solution (Python):
from collections import deque
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
q = deque()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    c = t[0][i]
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if near[c] == -1:
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)

Solution (Python):
from collections import deque

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

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


queue = deque([0])
d = [None] * n 
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i] = v
            queue.append(i)
print('Yes')
for i in range(1, n):
    print(d[i]+1)

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

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

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

que = deque()
dist = [-1]*n
ans = [0]*n

que.append(0)
while len(que) != 0:
    now = que.popleft()
    for to in adj[now]:
        if dist[to] != -1: continue
        dist[to] = dist[now]+1
        que.append(to)
        ans[to]=now

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

Solution (Python):
from collections import deque


r, p = map(int, input().split())
graph = [[] for _ in range(r)]

for x in range(p):
    x1, x2 = map(int, input().split())
    graph[x1-1].append(x2-1)
    graph[x2-1].append(x1-1)

q = [0]
res = [-1]*r
res[0] = 0
while q:
    l = q.pop(0)
    for x in graph[l]:
        if res[x] == -1:
            res[x] = l
            q.append(x)
if -1 in res[1:]:
    print("No")
    exit()
print("Yes")
for x in res[1:]:
    print(x+1)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
graph=[[] for i in range(n)]
sirusi=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
D=deque([0])
visited=[False]*n
visited[0]=True
while D:
    v=D.popleft()
    for i in graph[v]:
        if visited[i]:continue
        visited[i]=True
        sirusi[i]=v
        D.append(i)
print("Yes")
for i in range(1,n):
    print(sirusi[i]+1)

Solution (Python):
from collections import deque

def main():
    RoomNum,PathNum=map(int,input().split())

    G=[[] for _ in range(RoomNum)]

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

    dist=[-1]*RoomNum
    que=deque([])
    dist[0]=0
    que.append(0)

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

        for i in G[v]: 
            if dist[i]!=-1: 
                continue
            dist[i]=v 
            que.append(i)

    if (-1 in dist): 
        print("No")
    else:
        print("Yes")
        for i in dist[1:]:
            print(i+1)

if __name__=="__main__":
    main()

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

e = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
visited = [0]*N
visited[0] = 1
que = [0]
while que:
    x = que.pop(0)
    for i in e[x]:
        if visited[i] == 0:
            visited[i] = x+1
            que.append(i)

print("Yes")


print(*visited[1:], sep="\n")

Solution (Python):
from _collections import deque


def bfs(init, n, gi):
    queue = deque([init])
    d = [-1] * n
    d[init] = 0
    while queue:
        popped = queue.popleft()
        for ii in gi[popped]:
            if d[ii] == -1:
                d[ii] = popped + 1
                queue.append(ii)
    return d


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

get = bfs(0, N, g)
ans = [0] * N
if -1 in get:
    print('No')
else:
    print('Yes')
    for i in range(1, len(get)):
        print(get[i])

Solution (Python):
from collections import deque

def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q = deque()
    q.append(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.popleft()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.append(next)
        if len(q) == 0:
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

Solution (Python):
import queue
n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
dic = {}
for i in range(1, n+1):
    dic[i] = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    dic[a[i]].append(b[i])
    dic[b[i]].append(a[i])
res = 0
INF = 100010
l = [0 for i in range(n+1)]
l[1] = 1
michi = [INF for i in range(n+1)] 
michi[1] = 0
p = [1]
shi = 1
while True:
    tmp = []
    for i in p:
        for j in dic[i]:
            if l[j] == 0:
                l[j] = 1
                tmp.append(j)
    if not tmp:
        break
    for i in tmp:
        michi[i] = shi
    p = tmp
    shi = p[0]
flag = True
for i in range(2, n+1):
    if michi[i] == INF:
        flag = False
if flag:
    print("Yes")
    for i in range(2, n+1):
        print(michi[i])
else:
    print("No")

Solution (Python):
N, M = map(int, input().split())
AB = []
cons = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    cons[a - 1].append(b - 1)
    cons[b - 1].append(a - 1)
visited = [False for _ in range(N)]
visited[0] = True
Q = [0]
sirusi = [0 for _ in range(N)]
while Q:
    v = Q.pop(0)
    for i in cons[v]:
        if not visited[i]:
            visited[i] = True
            sirusi[i] = v
            Q.append(i)
print("Yes")
for i in range(1, N):
    print(sirusi[i] + 1)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
arr=[[] for n in range(N)]
que=deque([1])

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

dist=[-1]*N
dist[0]=0
arr2=[0]*(N-1)

print("Yes")
while que:
  c=que.popleft()
  for i in arr[c-1]:
    if dist[i-1]!=-1:
      continue
    
    dist[i-1]=0
    arr2[i-2]=c
    que.append(i)
       
for i in arr2:
  print(i)

Solution (Python):
from collections import deque

INF = float("inf")

N, M, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

dist = [INF] * (N + 1)
ans = [-1] * (N + 1)

Q = deque([1])
dist[1] = 0
while Q:
    v = Q.popleft()
    d = dist[v] + 1
    for u in E[v]:
        if dist[u] > d:
            dist[u] = d
            ans[u] = v
            Q.append(u)

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