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
class UnionFind:
    def __init__(self, N):
        self.parents = [-1 for i in range(N)]
        self.unit = [0 for i in range(N)]
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if x > y:
            x, y = y, x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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


lists = [False for i in range(N)]
lists[0] = True
a = N - 1
dicts = {i:[] for i in range(N)}
d = deque([0])

for i in range(M):
    tmpa, tmpb = map(lambda x: int(x) - 1, input().split()) 
    dicts[tmpa] += [tmpb]
    dicts[tmpb] += [tmpa]
    uf.union(tmpa, tmpb)

if -uf.parents[0] == N:
    print('Yes')
    while a > 0:
        tmp = d.popleft()
        for i in dicts[tmp]:
            if not lists[i]:
                if tmp != 0:
                    lists[i] = tmp
                else:
                    lists[i] = -1
                d.append(i)
                a -= 1
    
    for i in range(1, N):
        print(lists[i] + 1 if lists[i] != -1 else 1)
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)]
for a, b in ab:
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

q = deque()
q.append(0)
b = [0] * n
while q:
    r = q.popleft()
    for i in g[r]:
        if b[i] != 0:
            continue
        if i == 0:
            continue
        b[i] = r + 1
        q.append(i)

for i in b[1:]:
    if i == 0:
        print("No")
        exit()
print("Yes")
print(*b[1:], sep="\n")

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

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

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

res = [0]*(n-1)
used = [False]*n

tank = deque([0])
while tank:
    q = tank.popleft()
    if used[q]:
        continue
    used[q] = True

    for go in edge[q]:
        if go == 0 or res[go-1] != 0:
            continue
        res[go-1] = q+1
        tank.append(go)
print("Yes")
print(*res,sep='\n')

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


R = [-1 for i in range(n)]
Q = deque([(0, -2)])
while len(Q) > 0:
    t = Q[0][0]
    b = Q[0][1]
    
    
    Q.popleft()
    if R[t] == -1:
        R[t] = b
        for i in range(len(M[t])):
            if R[M[t][i]] == -1:
                Q.append((M[t][i], t))
            else:
                pass
    else:
        pass


f = 0
for i in range(n):
    if R[i] == -1:
        f = 1
        break  
    else:
        pass

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

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

def bfs(u):
    queue=deque([u])
    d=[0]*n
    ans=[0]*n
    while queue:
        v=queue.popleft()
        for i in road[v]:
            if d[i]==0 and i!=0:
                d[i]=d[v]+1
                ans[i]=v+1
                queue.append(i)
    return d,ans

def main():
    d,ans=bfs(0)
    flg=1
    for i in range(1,n):
        if d[i]==0:
            flg=0
            break
    if flg==0:
        print("No")
    else:
        print("Yes")
        for i in range(1,n):
            print(ans[i])
if __name__=="__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
import collections
henn = collections.defaultdict(list)

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

start_points = [1]
sirushi = {1: 0}

while len(sirushi.keys()) < N:
    next_points = []
    for start_point in start_points:
        for next_point in henn[start_point]:
            if next_point not in sirushi:
                sirushi[next_point] = start_point
                next_points.append(next_point)
    start_points = next_points

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

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

ans = [-1 for _ in range(N)]
def bfs(root):
    if root is None:
        return 
    q = deque()
    q.append(e[root])
    q.append(root)
    while q:
        r = q.popleft()
        i = q.popleft()
        for n in r:
            if ans[n] == -1:
                ans[n] = i + 1
                q.append(e[n])
                q.append(n)
bfs(0)
is_exit = True
for i in ans:
    if i == -1:
        is_exit = False
        break
if is_exit:
    print("Yes")
    for i in ans[1:]:
        print(i)
else:
    print("No")

Solution (Python):
from queue import Queue
n, m = map(int, input().split())
graph = {i:[] for i 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)
ans = [None]*n
visited = [False]*n
visited[0] = True
q = Queue()
q.put(0)
while not q.empty():
    root = q.get()
    for r in graph[root]:
        if not visited[r]:
            ans[r] = root
            visited[r] = True
            q.put(r)
print('Yes')
for a in ans[1:]:
    print(a+1)

Solution (Python):
from _collections import deque
import sys

N,M = map(int,input().split())
T = [ [] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
used_1 = [0]*N
used_2 = [0]*N
ans = [0]*N

P = deque([0])
while(len(P)>0):
    c = P.popleft()
    if used_1[c] == 0:
        used_1[c] = 1
        used_2[c] = 1
        for i in T[c]:
            if used_2[i] == 0:
                ans[i] = c+1
                used_2[i] = 1
                P.append(i)
for i in range(N):
    if used_2[i] == 0:
        print("No")
        sys.exit()

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

Solution (Python):
from collections import defaultdict
from heapq import*
n,m=map(int,input().split())
e = defaultdict(list)
dist = [2**60]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
q = [(0,0)]
dist[0] = 0
prev = [-1]*n
while q:
    s = heappop(q)
    c,v = s
    for u in e[v]:
        if dist[u] > dist[v]+1:
            dist[u] = dist[v]+1
            heappush(q,(dist[u],u))
            prev[u]=v
if -1 in prev[1:]:
    print('No')
else:
    print('Yes')
    for p in prev[1:]:
        print(p+1)

Solution (Python):
from collections import defaultdict

n, m = [int(i) for i in input().split()]
A = [ [int(j)-1 for j in input().split()] for i in range(m)]
G = defaultdict(set)
for i, j in A:
    G[i].add(j)
    G[j].add(i)

visited = [False for i in range(n)]
ans = [-1 for i in range(n)]
def bfs(start):
    Q = []
    visited[start] = True
    Q.append(start)
    while Q:
        v = Q.pop(0)
        for w in G[v]:
            if not visited[w]:
                ans[w] = v
                Q.append(w)
                visited[w] = True
bfs(0)
terminate_flag = False
for i in range(1,n):
    if ans[i] == -1:
        print("No")
        terminate_flag = True
        break
if not terminate_flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i]+1)

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


n,m=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m))
node=[[] for _ in range(n)]
d=deque()
ans=[-1]*n
ans[0]=0
d.append(0)
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
while True:
    if not d:
        break
    a=d.popleft()
    l=node[a]
    for i in l:
        if ans[i]==-1:
            d.append(i)
            ans[i]=a+1
if -1 in ans:
    print("No")
    exit()
print("Yes")
for i in range(1,n):
  print(ans[i])

Solution (Python):
def main():
    n,m = map(int,input().split())
    graph = {}
    for i in range(n):
        graph[i+1]=[]
    for i in range(m):
        a,b = map(int,input().split())
        graph[a]+=[b]
        graph[b]+=[a]
    dist = [-1 for i in range(n)]
    ans = [0 for i in range(n)]
    dist[0]=0
    que = [1]
    while len(que)>0:
        q = que.pop(0)
        for v in graph[q]:
            if dist[v-1]!=-1:
                continue
            dist[v-1] = dist[q-1]+1
            ans[v-1] = q
            que.append(v)
    print('Yes')
    for i in range(n-1):
        print(ans[i+1])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def sol():
  n,m=map(int,input().split())
  neighbors={i+1:set() for i in range(n)}
  for i in range(m):
    a,b=map(int,input().split())
    neighbors[a].add(b)
    neighbors[b].add(a)
  res=[0 for _ in range(n)]
  que=deque([1])
  while len(que)>0:
    
    a=que.popleft()
    for b in neighbors[a]:
      if res[b-1]==0:
        res[b-1]=a
        que.append(b)
  
  print('Yes')
  for b in res[1:]:
    print(b)
    
sol()

Solution (Python):
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


















def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n, m = map(int, input().strip().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a_temp,b_temp = map(lambda x: int(x) - 1, input().strip().split())
        g[a_temp].append(b_temp)
        g[b_temp].append(a_temp)
    
    usedlist=[-100 for _ in range(n)]
    Q=Queue()

    
    Q.put(0)
    usedlist[0] = -1
    while not(Q.empty()):
        u=Q.get()
        for v in g[u]:
            if usedlist[v]==-100:
                usedlist[v] = u 
                Q.put(v)
            else:
                pass
    eprint('g ',end=':\n')
    eprint(g)
    eprint('usedlist ',end=':\n')
    eprint(usedlist)
    print("Yes")
    for i in range(1,n):
        print( usedlist[i]+1)
    
        

if __name__ == '__main__':
    main()

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

start = 0

from collections import deque
que = deque([start])
done = {start}
depth = [1e9]  * n
depth[start] = 0
parents = [-1] * n
while True:
    if len(que) == 0:
        break
    now = que.popleft()
    dep = depth[now]
    
    for node in edge[now]:
        if node not in done:

            depth[node] = dep + 1
            parents[node] = now
            que.append(node)
        done.add(node)


if max(depth) == 1e9:
    print("No")
else:
    print("Yes")
    for k in range(1, n):
        print(parents[k] + 1)

Solution (Python):
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

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

stack = deque()
stack.append((1,1))
not_visit = [True]*(N+1)
ans = [0]*(N+1)
while stack:
    now = stack.popleft()
    if not_visit[now[0]]:
        not_visit[now[0]] = False
        ans[now[0]] = now[1]
        for room in lines[now[0]]:
            if not_visit[room]:
                stack.append((room,now[0]))

flag = 0
for i in not_visit[1:]:
    if i:
        flag = 1
        break

if flag == 1:
    print("No")
else:
    print("Yes")
    for i in ans[2:]:
        print(i)

Solution (Python):
from collections import deque
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m=INTM()
    roots=[[]for i in range(n)]
    visit=[0]*n
    visit[0]=1
    q=deque([0])
    for i in range(m):
        a,b=INTM()
        roots[a-1].append(b-1)
        roots[b-1].append(a-1)
    while q:
        temp=q.popleft()
        for root in roots[temp]:
            if visit[root]!=0:
                continue
            else:
                q.append(root)
                visit[root]=temp+1
    
    print('Yes')
    for i in visit[1:]:
        print(i)
        

                
if __name__ == '__main__':
    do()

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


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

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


ans = [0] + [0] * n
queue = deque([(1, 0)])
visited = set()
dist = 0

while queue:
    for _ in range(len(queue)):
        node, pre_node = queue.popleft()
        if node in visited:
            continue
        ans[node] = pre_node
        visited.add(node)
        for n in g[node]:
            if n in visited:
                continue
            queue.append((n, node))
    dist += 1

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

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


def bfs(s):
    queue = deque([s])
    cv = [0] * n
    cv[s] = 1
    dist[0] = 0
    while queue:
        u = queue.popleft()
        for nxt in adj[u]:
            if not cv[nxt]:
                queue.append(nxt)
                cv[nxt] = 1
                if dist[u] + 1 < dist[nxt]:
                    dist[nxt] = dist[u] + 1
                    parent[nxt] = u


def dfs(u):
    st = [u]
    cv = [0] * n
    dist[0] = 0
    while st:
        u = st.pop()
        if cv[u]:
            continue
        cv[u] = 1
        for nxt in adj[u]:
            if dist[u] + 1 < dist[nxt]:
                parent[nxt] = u
                dist[nxt] = dist[u] + 1
            st.append(nxt)


n, m = [int(item) for item in input().split()]
parent = [-1] * n
dist = [float('inf')] * n
parent[0] = 0
adj = defaultdict(list)
for i in range(m):
    u, v = [int(item) - 1 for item in input().split()]
    adj[u].append(v)
    adj[v].append(u)
bfs(0)

if -1 in parent:
    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())
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)

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

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

while not q.empty():
  i = q.get()
  for j in link[i]:
    if j != 0 and mark[j] == -1:
      mark[j] = i
      q.put(j)

flag = True
for i in range(1, n):
  if mark[i] == -1:
    flag = False

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

Solution (Python):


import sys
import pprint
from collections import deque

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, m = map(int, sys.stdin.readline().split())
	graph = [[] for i in range(n)]
	for i in range(m):
		ai, bi = map(int, sys.stdin.readline().split())
		graph[ai-1].append(bi-1)
		graph[bi-1].append(ai-1)
	stack = deque([0])
	dist = [-1]*len(graph)
	ans = [-1]*n
	log.print(graph)
	while len(stack) != 0:
		v = stack.popleft()
		d = dist[v]
		nexts = graph[v]
		for next in nexts:
			if dist[next] != -1:
				continue
			dist[next] = d + 1
			ans[next] = v
			stack.append(next)
	if -1 in ans:
		print("No")
	else:
		print("Yes")
		for i in range(1, n):
			print(ans[i]+1)

	


main()

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

res = [-1]*n
res[0] = 0
q = []
q.append(0)
while len(q) > 0:
    current = q.pop(0)

    for nex in d_list[current]:
        if res[nex] == -1:

            res[nex] = current
            q.append(nex)
if -1 not in res:
    print('Yes')
    for ans in res[1:]:
        print(ans+1)
else:
    print("No")

Solution (Python):
import queue
q = queue.Queue()
n, m = map(int, input().split())
mat = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  mat[a-1].append((a-1,b-1))
  mat[b-1].append((b-1,a-1))

d_list = [(-1,-1)]*n

d_list[0] = (0,0)
while len(mat[0]) > 0:
  q.put(mat[0].pop())

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

  if d_list[v][1] != -1 and d_list[v][1] <= d_list[u][1]+1:
    pass
  else:
    d_list[v] = (u, d_list[u][1]+1)
    while len(mat[v]) > 0:
      q.put(mat[v].pop())
print("Yes")
for i in range(1,n):
  print(d_list[i][0]+1)

Solution (Python):
N, M =  map(int, input().split())
path = [[] for _ in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
ans = [-1]*N
def bfs():
  que = [0]
  while len(que)>0:
    a = que.pop(0)
    for i in path[a]:
      if ans[i] == -1:
        ans[i] = a+1
        que.append(i)
  if -1 in ans:
    print("No")
  else:
    print("Yes")
    for i in range(1, N):
      print(ans[i])
if  __name__ == "__main__":
  bfs()

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M = map(int, readline().split())
    path = [[] for _ in range(N+1)]
    path[0].append(1)
    for _ in range(M):
        a, b = map(int, readline().split())
        path[a].append(b)
        path[b].append(a)
    d = deque([0])
    parents = [0] * (N+1)
    parents[0] = -1
    while d:
        x = d.popleft()
        for i in path[x]:
            if parents[i] == 0:
                parents[i] = x
                d.append(i)
    ans = parents[2:N+1]
    if 0 in ans:
        print('No')
    else:
        print('Yes')
        for i in range(N-1):
            print(ans[i])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

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


visited = set()
ans = {} 
while q:
    pos, prev = q.popleft()
    if pos in visited:
        continue
    ans[pos] = prev
    visited.add(pos)

    for next_pos in edges[pos]:
        q.append((next_pos, pos))

if len(ans) != N:
    print("No")
    sys.exit()

print("Yes")
for (pos, prev) in sorted(ans.items()):
    if pos == 0:
        continue
    print(prev+1)

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

from heapq import heappush, heappop
INF = float("inf")
miti = [-1]*N
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                if miti[t] == -1:
                    miti[t] = v+1
                heappush(que, (dist[t], t))
    return dist

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

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

dist = dijkstra(N,edge,0)

if -1 in miti[1:]:
    print("No")
else:
    print("Yes")
    for t in miti[1:]:
        print(t)

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

n,m = map(int,readline().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
from collections import deque

que = deque()
que.append((0,1))
chk = [False]*n
chk[0] =True
cnt = 1
while que:
    now,p = que.popleft()
    if cnt == n:
      break
    for i in g[now]:
        if not chk[i]:
          ans[i] = p
          chk[i] = True
          cnt += 1
          que.append((i,i+1))

if cnt!=n:
  print('No')
  exit()
  
print('Yes')
for i in ans[1:]:
  print(i)

Solution (Python):
from collections import deque

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)

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

def bfs(graph):
    ch[0]=True
    Q=deque()
    Q.append([graph[0],0])

    while len(Q)>0:
        v,y=Q.popleft()

        for e in v:
            if ch[e]==False:
                ch[e]=True
                ans[e]=y
                Q.append([graph[e],e])



bfs(graph)

for i in range(1,len(ans)):
    if ans[i]==-1:
        print("No")
        exit()
    ans[i]+=1

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

Solution (Python):
import copy
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)
memo = [0]*n
now = [[0,0]]
nxt = []
done = [False]*n
done[0] = True


while now:
    for l in now:
        for j in graph[l[1]]:
            if not done[j]:                
                done[j] = True
                nxt.append([l[1],j])
                memo[j] = l[1]+1
    now = copy.copy(nxt)
    nxt = []
for l in now:
    done[l[1]] = True
if False in done:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(memo[i])

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

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

import queue

next_visit = queue.Queue()
next_visit.put(0)

while not next_visit.empty():
    i = next_visit.get()
    for j in graf[i]:
        if out[j] == 0:
            out[j] = i+1
            next_visit.put(j)
cnt = 1

for i in range(1, n):
    if out[i] == 0:
        cnt = 0
        break
if cnt:
    print("Yes")
    for i in out[1:]:
        print(i)
else:
    print("No")

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

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

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



ans_li = [-1]*n
ans_li[0] = 1

q = deque()

q.appendleft(0)

while len(q) > 0 :
    for i in range(len(q)):
        tmp = q.popleft()
        
        for j in range(len(ab[tmp])):
            if ans_li[ab[tmp][j]] == -1:
                ans_li[ab[tmp][j]] = tmp+1
                q.append(ab[tmp][j])
                

print('Yes')

for i in range(n-1):
    print(ans_li[i+1])

Solution (Python):
from collections import defaultdict, deque
def solve():
    N,M = map(int,input().split())
    G = defaultdict(list)

    for i in range(M):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    visited = [False] * N
    ans = [float('inf')] * N

    q = deque()
    q.append((0,-1))
    visited[0] = True
    while len(q) > 0:
        now,before = q.popleft()
        ans[now] = min(before + 1,ans[now])

        
        for next in G[now]:
            if not visited[next]:
                
                q.append((next,now))
                visited[next] = True


    print('Yes')
    print(*ans[1:],sep='\n')

if __name__ == '__main__':
    solve()

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

visited = [False] * (N+1)
visited[0] = True
visited[1] = True
T = defaultdict(list)
for _ in range(M):
    a, b = list(map(int, input().split()))
    T[a].append(b)
    T[b].append(a)

q = deque()
q.append(1)

route = [0] * (N+1)

while q:
    v = q.popleft()
    for n in T[v]:
        if not visited[n]:
            route[n] = v
            q.append(n)
            visited[n] = True

if visited.count(False) > 0:
    print("No")
    sys.exit(0)

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

Solution (Python):
from collections import deque

N,M = map(int,input().split())
C = [[] for _ in range(N+1)]
for _ in range(M):
    tmp = list(map(int,input().split()))
    C[tmp[0]].append(tmp[1])
    C[tmp[1]].append(tmp[0])
d = [1000000000]*(N+1)
d[1] = 0
visited = [False]*(N+1)
q = deque()
q.append(1)

sirube = [0]*(N+1)
while q:
    node = q.popleft()
    for adj in C[node]:
        if visited[adj] == False:
            sirube[adj] = node
            q.append(adj)
            visited[adj] = True



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

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
def search(l,dic1,dic2):
    if not l:
        return(dic2)
    else:
        x=l.pop()
        for y in dic1[x]:
            if dic2[y]==0:
                l.appendleft(y)
                dic2[y]=x
        return search(l,dic1,dic2)

n,m=map(int,input().split())
l=[i+1 for i in range(n)]
dic1={i:[] for i in l}
dic2={i:0 for i in l}
for _ in range(m):
    a, b = map(int, input().split())
    dic1[a].append(b)
    dic1[b].append(a)
l=deque(dic1[1])
for z in l:
    dic2[z]=1

d=search(l,dic1,dic2)
print('Yes')
for k in range(2,n+1):
    print(dic2[k])

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

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

g = sparse.csr_matrix(([1]*m, (ab[:, 0]-1, ab[:, 1]-1)), shape=(n, n))
_bfo, predecessors = sparse.csgraph.breadth_first_order(g, 0, directed=False)
if all(predecessors[1:] >= 0):
    print('Yes')
    for p in predecessors[1:]:
        print(p+1)
else:
    print('No')

Solution (Python):
from collections import deque
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    li[a-1].append(b)
    li[b-1].append(a)
ans=[0]*n
a=[[]  for _ in range(n)]
d=deque([1])
while len(d)>0:
    x=d.popleft()
    if ans[x-1]==0:
        ans[x-1]+=1
        for v in li[x-1]:
            if ans[v-1]==0:
                d.append(v)
                a[v-1].append(x)
if sum(ans)==n:
    print("Yes")
    for i in range(1,n):
        print(a[i][0])
else:
    print("No")

Solution (Python):
import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
AB = [LI() for _ in range(M)]
graph = {i:collections.deque() for i in range(1,N+1)} 
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,N+1):
    if not graph[i]:
        print('No')
        exit()
else:
    print('Yes')
seen = [0]*(N+1) 
min_dist = [-1]*(N+1) 
queue = collections.deque() 
def bfs():
    c_graph = copy.deepcopy(graph)
    seen[1] = 1
    queue.append(1)
    min_dist[1] = 0
    while queue:
        q_NO = queue.popleft()
        q_dist = min_dist[q_NO]
        if not c_graph[q_NO]:
            continue
        g = c_graph[q_NO]
        for _ in range(len(g)):
            g_NO = g.popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            queue.append(g_NO)
            min_dist[g_NO] = q_dist+1
bfs()
for j in range(2,N+1):
    ans,dist = 0,float('INF')
    for x in graph[j]:
        if dist>=min_dist[x]:
            ans = x
            dist = min_dist[x]
    print(ans)