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

Solution (Python):
import bisect,collections,copy,heapq,itertools,math,numpy,string

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LI() for _ in range(M)]
path = [[] for _ in range(N+1)]
mp = []
ans = [0] * (N+1)

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

def bfs(tree, st, endlist, endnum):
	queue = collections.deque()
	queue.append([-1,st])
	endlist[st] -= 1
	now = [-1,-1,-1]
	pre = []
	depth = 0
	histind = -1
	node = -1
	hist = []
	res = []
	allres = []
	while queue:
		pre = now[:]
		now = queue.popleft()
		histind = now[0]
		node = now[1]
		hist.append([histind,node])
		
		res = [node,hist[histind][1]]
		allres.append(res[::])
		endnum -= 1
		if endnum == 0:
			return allres
		for v in path[node]:
			if endlist[v] > 0:
				queue.append([len(hist)-1,v])
				
				endlist[v] -= 1
		continue
	return None


result = bfs(path, 1, [1] * (N+1), N)

if result is None:
	print("No")
	exit(0)
print("Yes")
execnum = N
maxlen = len(result[len(result)-1])
for i in result:
	
	if ans[i[0]] == 0:
		ans[i[0]] = i[1]
		execnum-=1
		if execnum == 0:
			break

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

Solution (Python):
from collections import deque

def main():
    INF = float('inf')

    N, M = (int(x) for x in input().split())
    root = [[] for _ in range(N+1)]
    for i in range(M):
        A,B = (int(x) for x in input().split())
        root[A].append(B)
        root[B].append(A)
    dist = [INF] * (N+1)
    dist[1] = 0
    q = deque([1])

    while q:
        v = q.popleft()
        for r in root[v]:
            if dist[r] == INF:
                dist[r] = v
                q.append(r)
    print('Yes')
    for d in dist[2:]:
        print(d)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
 
n,m = map(int,input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
path = [[] for _ in range(n+1)]
 
for a,b in ab:
    path[a].append(b)
    path[b].append(a)
 
q = deque([1])
ans = [0] * (n+1)
while q:
    v = q.popleft()
    for w in path[v]:
        if ans[w] == 0:
            ans[w] = v
            q.append(w)
 
print('Yes')
print(*ans[2:], sep="\n")

Solution (Python):
from collections import deque

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

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

dist =[0] * (n+1)
sirusi = [0] * (n+1)
dist[1] = -1

que = deque([])
ique = deque([])
x = res.pop(1)

que.append(x)
ique.append(1)

d = 1


while(len(que)>0):
    data = que.popleft()
    index = ique.popleft()
    
    ind = 0
    for i in data:
        

        if dist[int(i)] == 0 :
            
            
            dist[i] = d
            sirusi[i] = index
            que.append(res.pop(i))
            ique.append(int(i))
        ind += 1
    d = d + 1



























print("Yes")
for i in range(2,len(sirusi)):
    print(sirusi[i])

Solution (Python):
from collections import defaultdict, deque

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

d = defaultdict(list)

for i in xrange(m):
    (a, b) = map(int, raw_input().split())
    d[a].append(b)
    d[b].append(a)

pre = [0 for i in xrange(n + 1)]
cnt = 0

q = deque([1])
while q:
    cur = q.popleft()
    for nxt in d[cur]:
        if pre[nxt] == 0:
            cnt += 1
            pre[nxt] = cur
            q.append(nxt)


if cnt < n - 1:
    print 'No'
else:
    print 'Yes'
    for i in xrange(2, n + 1):
        print pre[i]

Solution (Python):
from collections import deque

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

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

q = deque([1])
ans = [0] * (n+1)
while q:
    v = q.popleft()
    for w in path[v]:
        if ans[w] == 0:
            ans[w] = v
            q.append(w)

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

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


d = deque([0])
D = [-1] * n
D[0] = 0
while len(d) > 0 :
    t = d.popleft()
    for i in L[t]:
        if D[i] == -1:
            D[i] = t
            d.append(i)
            

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

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def bfs(graph: list, n: int, start: int, ans: list):
    q = deque([start])
    visited = [INF] * n
    visited[0] = 1
    while len(q) != 0:
        node = q.popleft()
        for leaf in graph[node]:
            if visited[leaf] != INF:
                continue
            ans[leaf] = node + 1
            visited[leaf] = 1
            q.append(leaf)

def create_graph(n: int, l: list) -> list:
    graph = [[] for _ in range(n)]
    for a, b in l:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    return graph

def main():
    n, m = i_map()
    num_list = i_row_list(m)

    graph = create_graph(n, num_list)

    ans = [0] * n

    bfs(graph, n, 0, ans)

    Yes()
    for a in ans[1:]:
        print(a)

if __name__ == '__main__':
    main()

Solution (Python):
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()

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

G.add_edges_from(rows)

preds = dict(bfs_predecessors(G,source=1))

if len(preds)+1 != N:
    print("No")
    exit()

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

Solution (Python):
from collections import deque
N, M = map(int, input().split())
ways = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  ways[a].append(b)
  ways[b].append(a)
searched = [0 for i in range(N)]
searched[0] = 1
ans = [0 for i in range(N)]
d = deque([])
d.append(0)
while d:
  tmp = d.popleft()
  for w in ways[tmp]:
    if searched[w] == 0:
      searched[w] = 1
      ans[w] = tmp
      d.append(w)
print("Yes")
for a in ans[1:]:
  print(a + 1)

Solution (Python):















from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()





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

G.add_edges_from(rows)


preds = bfs_predecessors(G,source=1)



preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

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

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7





















def create_graph(n: int, l: list) -> list:
    graph = [[] for _ in range(n)]
    for a, b in l:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    return graph

def main():
    n, m = i_map()
    num_list = i_row_list(m)

    graph = create_graph(n, num_list)

    q = deque([0])

    visited = [INF] * n
    visited[0] = 1

    ans = [0] * n

    while len(q) != 0:
        node = q.popleft()
        for leaf in graph[node]:
            if visited[leaf] != INF:
                continue
            ans[leaf] = node + 1
            visited[leaf] = 1
            q.append(leaf)

    Yes()
    for a in ans[1:]:
        print(a)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, os

if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

f = lambda:list(map(int,input().split()))

def get_qsa(file_name):
    audio, size = readfile(file_name)
    headers = {
        'Connection': 'keep-alive',
        'Content-Length': str(size)
    }

    
    parameter = {
                "request_id":int(time.time()*100),
                "th":1,
                "tht":"qf492_100fps",
                "the":1.000000,
                "thst":"neural"
                }
    res = requests.post(f"http://{config['ip']}:{config['port']}", timeout=120, data=audio, headers=headers, params = parameter)
    

    res_json = res.json()
    


    if res_json['retmsg']!="success":
        raise Exception
    

    bin_str = res_json["th"][0]["feat"]
    bin_data = base64.b64decode(bin_str)

    bin2qsa_siren(bin_data, file_name)


def solve():
    n,m = f()
    g= []
    for _ in range(n):
        g.append([])

    for _ in range(m):
        a,b = f()
        g[a-1].append(b-1)
        g[b-1].append(a-1)

    import queue
    q = queue.Queue()
    q.put(0)
    vis = set()
    vis.add(0)
    d = {}
    d[0] = 0

    ans = {}
    while not q.empty():
        u = q.get()
        for v in g[u]:
            if v in vis:
                continue
            vis.add(v)
            d[v] = d[u] + 1
            ans[v] = u
            q.put(v)

    ok = 1
    for i in range(1, n):
        if i not in vis:
            ok = 0
    
    if ok == 0:
        print("No")
    else:
        print("Yes")
        for i in range(1, n):
            print(ans[i]+1)



       
    
solve()

Solution (Python):
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].append(B)
    graph[B].append(A)

from collections import deque

dist = [-1] * N
prev = [-1] * N
dist[0] = 0
queue = deque([0])
while queue:
    tmp = queue.popleft()
    for i in graph[tmp]:
        if dist[i] != -1:
            continue
        dist[i] = dist[tmp] + 1
        prev[i] = tmp
        queue.append(i)


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

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

node = [[] for i in range(n)]
for i in range(m):
    node[ab[i][0] - 1].append(ab[i][1])
    node[ab[i][1] - 1].append(ab[i][0])


node_dic = [[] for i in range(n)]
now = [1]
while True:
    
    flag = True
    next_node = []
    for i in range(len(now)):
        next_node_element = node[now[i] - 1]
        
        for j in range(len(next_node_element)):
            if not node_dic[next_node_element[j] - 1]:
                next_node.append(next_node_element[j])
                node_dic[next_node_element[j] - 1].append(now[i])
                flag = False
    
    
    
    
    now = []
    now = next_node
    if flag:
        break

for i in range(n):
    if i == 0:
        print('Yes')
        continue
    print(node_dic[i][0])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

room_and_connecting_room_dict = {i:set() for i in range(1,N+1)}

for i in range(M):
    A,B = map(int, input().split())
    room_and_connecting_room_dict[A].add(B)
    room_and_connecting_room_dict[B].add(A)

def get_child_ans(room_numbers_set): 
    
    next_room_numbers_set = set()
    
    for room_number in room_numbers_set:
        for child_room in room_and_connecting_room_dict[room_number]:
            if child_room not in calculated_room_numbers_set:
                ans_dict[child_room] = room_number 
                next_room_numbers_set.add(child_room)
                calculated_room_numbers_set.add(child_room)
 
    
    if len(calculated_room_numbers_set) == N: 
        return 1
    elif len(next_room_numbers_set) == 0: 
        return -1
    else: 
        return get_child_ans(next_room_numbers_set)

ans_dict = dict()
ans_dict[1] = 0
calculated_room_numbers_set = set()
calculated_room_numbers_set.add(1)

is_there_ans = get_child_ans(set([1]))  

if is_there_ans == 1:
    print("Yes")
    for i in range(2,N+1):
        print(ans_dict[i])
else:
    print("No")

Solution (Python):
from collections import deque

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
conn = [[] for _ in range(n)]
for a,b in ab:
    conn[a-1].append(b)
    conn[b-1].append(a)
q = deque([1])


ans = [-1 for _ in range(n)]
depth = ans[:]
depth[0] = 0
while q:
    v = q.popleft()
    d = depth[v-1]
    
    for w in conn[v-1]:
        if depth[w-1] != -1:
            continue
        depth[w-1] = d + 1
        ans[w-1] = v
        q.append(w)
        

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

Solution (Python):
from collections import*
(n,m),*c=[[*map(int,i.split())]for i in open(0)]
g=[[]for _ in range(n+1)]
for a,b in c:
    g[a]+=[b]
    g[b]+=[a]
q=deque([1])
r=[0]*(n+1)
while q:
    v=q.popleft()
    for i in g[v]:
        if r[i]==0:
            r[i]=v
            q.append(i)
print("Yes",*r[2:],sep="\n")

Solution (Python):

from collections import defaultdict
N,M=map(int,input().strip().split())
G=defaultdict(list)
for i in range(M):
  u,v=map(int,input().strip().split())
  G[u].append(v)
  G[v].append(u)
dist=[]
for i in range(N+1):
    dist.append([0,-1])
valid=False
Q=[1]
visited=[False]*(N+1)
visited[1]=True
while(len(Q)!=0):
  top=Q[0]
  Q.pop(0)
  for u in G[top]:
    if not visited[u]:
      Q.append(u)
      dist[u][0]=1+dist[top][0]
      dist[u][1]=top
      visited[u]=True
for pair in dist[2:]:
  if pair[0]==-1:
    valid=True
    print("No")
if not valid:
  print("Yes")
  for pair in dist[2:]:
    print(pair[1])

Solution (Python):
"""bfs"""
import sys
sys.setrecursionlimit(10**6)
n,m = map(int, input().split())

INF = 1001001001

to = [[] for _ in range(n)]
dist = [INF]*n
dist[0] = 0
ans = [-1]*n
ans[0] = [0]

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

import queue

q = queue.Queue()
searched = [0]*n
q.put(0)


while not q.empty():
    v = q.get()
    for i in range(len(to[v])):
        u = to[v][i]
        if dist[u] != INF: continue

        dist[u] = dist[v]+1
        ans[u] = v
        q.put(u)


if -1 not in ans:
    print('Yes')
    for i in ans[1:]: print(i+1)
else:
    print('No')

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

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

def bfs():
    flg = [True] * n
    ans = [0] * n
    flg[0] = False
    que = deque([0])
    
    while len(que) != 0:
        val = que.popleft()
        
        
        
        

        for i in range(len(d[val])):
            if flg[d[val][i]] == True:
                que.append(d[val][i])
                flg[d[val][i]] = False
                ans[d[val][i]] = val
    return ans
ans = bfs()

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

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

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

def bfs():
    flg = [True] * n
    ans = [0] * n
    flg[0] = False
    que = deque([0])
    
    while len(que) != 0:
        val = que.popleft()
        
        
        
        

        for i in range(len(d[val])):
            if flg[d[val][i]] == True:
                que.append(d[val][i])
                flg[d[val][i]] = False
                ans[d[val][i]] = val
    return ans
ans = bfs()

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

Solution (Python):
import queue
N, M = map(int,input().split())
D = [[] for i in range(N)]

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

print("Yes")

dist = [0 for i in range(N)]
prev = [0 for i in range(N)]
prev[0] == 1

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

while not q.empty():
  t = q.get()
  for i in D[t-1]:
    if prev[i-1] == 0:
      prev[i-1] = t
      q.put(i)

for i in prev[1:]:
  print(i)

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

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

AB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for a, b in AB:
    es[a-1].append(b-1)
    es[b-1].append(a-1)

ans = [-1] * N
ans[0] = 0

from collections import deque
que = deque([])
que.append(0)

while que:
    s = que.popleft()
    for v in es[s]:
        if ans[v] == -1:
            ans[v] = s+1
            que.append(v)

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

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

AB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for a, b in AB:
    es[a-1].append(b-1)
    es[b-1].append(a-1)

ans = [-1] * N
ans[0] = 0

from collections import deque
que = deque([])
que.append(0)

while que:
    s = que.popleft()
    for v in es[s]:
        if ans[v] == -1:
            ans[v] = s+1
            que.append(v)

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

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

AB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for a, b in AB:
    es[a-1].append(b-1)
    es[b-1].append(a-1)

ans = [-1] * N
ans[0] = 0

from collections import deque
que = deque([0])

while que:
    s = que.popleft()
    for v in es[s]:
        if ans[v] == -1:
            ans[v] = s+1
            que.append(v)

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

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

AB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for a, b in AB:
    es[a-1].append(b-1)
    es[b-1].append(a-1)

ans = [-1] * N
ans[0] = 0

import queue
que = queue.Queue()
que.put(0)

while que.qsize():
    s = que.get()
    for v in es[s]:
        if ans[v] == -1:
            ans[v] = s+1
            que.put(v)

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

Solution (Python):
import queue

N, M = map(int, input().split())
parent = [-1] * N 
adj = [[] for _ in range(N)] 
for i in range(M):
  a, b = map(int, input().split())
  adj[a-1].append(b)
  adj[b-1].append(a)
q = queue.Queue() 
q.put([1, 0]) 
while not q.empty():
  x, y = q.get()
  if parent[x-1] != -1: 
    continue
  parent[x-1] = y 
  for i in adj[x-1]:
    if parent[i-1] == -1:
      q.put([i, x])
print('Yes')
for j in parent[1:]:
  print(j)

Solution (Python):


import sys
input = sys.stdin.readline

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

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

from collections import deque

def BFS(u): 
    queue = deque([u]) 
    dis = [None] * n 
    dis[u] = 0 
    ans = [-1] * n 
    while queue:
        v = queue.popleft() 
        for i in pic[v]: 
            if ans[i] == -1:
                ans[i] = v
            if dis[i] is None:
                dis[i] = dis[v] + 1
                queue.append(i)
    return ans

tmp = BFS(0) 
print('Yes')
for j in tmp[1:]:
    print(j+1)

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

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


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


from collections import deque

def BFS(u): 
    queue = deque([u]) 
    dis = [None] * n 
    dis[u] = 0 
    ans = [-1] * n
    
    while queue:
        v = queue.popleft() 
        for i in pic[v]: 
            if ans[i] == -1:
                ans[i] = v
            if dis[i] is None:
                dis[i] = dis[v] + 1
                queue.append(i)
    return ans



dis = BFS(0)
print('Yes')
for j in dis[1:]:
    print(j+1)

Solution (Python):
from collections import deque

mi = lambda:list(map(int,input().split()))
mix = lambda x:list(mi() for _ in range(x))

def main(n,m,l):
    
    g = creategraph(n,l)
    
    for i in range(1,len(g)):
        if len(g[i]) == 0:
            print("No")
            return
    
    navi = bfs(n,g)
    
    if min(navi[2:]) == 0:
        print("No")
    else:
        print("Yes")
        for i in navi[2:]:
            print(i)


def bfs(n,g):
    navi = [0]*(n+1)
    navi[1] = -1
    q = deque()
    q.append(1)
    while len(q) > 0:
        
        cp = q.popleft()
        
        np = g[cp]
        
        for i in np:
            if navi[i] == 0:
                navi[i] = cp
                q.append(i)
    return navi


def creategraph(n,l):
    g = {i:[] for i in range(n+1)}
    for a,b in l:
        g[a].append(b)
        g[b].append(a)
    return g

def resolve():
    n,m = mi()
    l = mix(m)
    main(n,m,l)

if __name__ == "__main__":
    resolve()

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

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




q = deque([0])
prev=[-1] * n

while q:
    v = q.popleft()

    for j in r[v]:
        if prev[j]==-1:
            prev[j] = v
            q.append(j)
            
            

for i in range(n):
    if i==0:
        print('Yes')
    else:
        print(prev[i]+1)

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

searched=[0]*N
searched[0]=1
ans=[-1]*N
d=deque()
d.append(0)
while(len(d)!=0):
  tmp=d.popleft()
  for g in G[tmp]:
    if searched[g]==0:
      searched[g]=1
      d.append(g)
      ans[g]=tmp
print('Yes')
for i in ans[1:]:
  print(i+1)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
ways = [tuple(map(int, input().split())) for _ in range(m)]
ans = [None] * (n+1)

hush = {}
hush[1] = True
for i in range(2, n+1):
    hush[i] = False
table = [list() for _ in range(n+1)]
for a, b in ways:
    table[a].append(b)
    table[b].append(a)

que = deque([1])
while len(que) > 0:
    room = que.popleft()
    for next in table[room]:
        if hush[next] == False:
            ans[next] = room
            que.append(next)
            hush[next] = True

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

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

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


rooms = [0 for i in range(n)] 
marks = [0 for i in range(n)] 
rooms_rate = [[0]] 
rooms[0] = 1

turn = 0
for i in rooms_rate:
    newrate = []
    for j in rooms_rate[turn]: 
        for k in routes[j]: 
            if (rooms[k] == 0): 
                rooms[k] = 1
                marks[k] = j 
                newrate.append(k)
    rooms_rate.append(newrate)
    if (len(newrate) == 0): 
        break
    turn = turn + 1


if(all(rooms) == True):
    print('Yes')
    for i in range(1,n):
        print(str(int(marks[i]) + 1))

else:
    print('No')

Solution (Python):
import heapq
def dijkstra(G, s):
    dist = [float("inf")]*len(G)
    ret = [-1]*len(G)
    q = []
    dist[s] = 0
    heapq.heapify(q)
    heapq.heappush(q, [0, s])
    while 0 < len(q):
        pre_cost, p = heapq.heappop(q)
        if dist[p] < pre_cost:
            continue
        for v, d in G[p]:
            if dist[v] > dist[p] + d:
                dist[v] = dist[p] + d
                heapq.heappush(q, [dist[v], v])
                ret[v] = p
    return ret

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append([b, 1])
        G[b].append([a, 1])
    ans = dijkstra(G, 1)
    f = True
    for i in range(2, n+1):
        if ans[i] == -1:
            f = False
    if f:
        print("Yes")
        for i in range(2, n+1):
            print(ans[i])
    else:
        print("No")

if __name__ == "__main__":
    main()

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



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

ans = [-1] * (n+1)
ans[1] = 0




x = [1]
y = []
while x != []:
  for i in x:
    for j in l[i]:
      if ans[j] == -1:
        ans[j] = i
        y.append(j)
  x = y
  y = []
print('Yes')
for i in range(2, n+1):
  print(ans[i])

Solution (Python):
from collections import deque, defaultdict

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

for _ in range(M):
    v1, v2 = map(int, input().split())
    
    outs[v1].append(v2)
    outs[v2].append(v1)


q = deque([1])
depth = defaultdict(int)
depth[1] = 0
visit = [False]*N 
visit[0] = True

while q:
    v1 = q.popleft()
    
    for v2 in outs[v1]: 
        
        if visit[v2-1]==False:
            visit[v2-1] = True
            depth[v2] = v1
            q.append(v2)
            

b = sorted(depth.items())

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

Solution (Python):
from collections import deque

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

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

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

    


def bfs(u):
    queue = deque([u])
    d = [None] * (N + 1)
    d[0] = 0
    d[u] = 0

    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                
                d[i] = v
                queue.append(i)
    
    return d

d = bfs(1)

if None in d:
    print("No")
else:
    print("Yes")
    for i in d[2:]:
        print(i)

Solution (Python):
from collections import defaultdict, deque

V, E = map(int, input().split())

G = defaultdict(lambda: [])

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

INF = 10 ** 18
dist = [INF] * V
parent = [-1] * V  
q = deque()

dist[0] = 0
q.append(0)
while q:
    now = q.popleft()  
    for to in G[now]:  
        if dist[to] != INF:  
            continue
        dist[to] = dist[now] + 1  
        parent[to] = now
        q.append(to)

print("Yes")
for i in range(1, V):
    print(parent[i] + 1)

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

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

q = deque([0])
ans = [-1] * N
while(len(q) > 0):
    now = q.popleft()

    for i in node[now]:
        if ans[i] == -1:
            q.append(i)
            ans[i] = now


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

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
 
l = [[] for i in range(N + 1)]
 
for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    l[a].append(b)
    l[b].append(a)
 
point = [0] * (N + 1)
search = [0] * (N + 1)
search[1] = 1

que = []
que.append(1)
p = 0

while len(que) != N:
    now = que[p]
    for i in range(len(l[now])):
        n = l[now][i]
        if search[n] == 0:
            search[n] = 1
            que.append(n)
            point[n] = now
    p += 1
    
print('Yes')
for i in range(2,N+1):
    print(point[i])

Solution (Python):
import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


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

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)