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):
n, m = map(int, input().split())

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

queue = [1]
res = [0] * (n+1)
while queue != []:
    p = queue[0]
    del queue[0]
    for i in dic[p]:
        if res[i] == 0:
            res[i] = p
            queue.append(i)
            
print('Yes')
for elem in res[2:]:
    print(elem)

Solution (Python):
from collections import deque, defaultdict


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(m)]

    R = defaultdict(set)
    for ab in AB:
        a, b = ab
        R[a].add(b)
        R[b].add(a)

    A = [0] * (n + 1)
    Q = deque(R[1])
    Qa = deque([1] * len(R[1]))
    while len(Q) > 0:
        qe = Q.pop()
        arrow = Qa.pop()
        if A[qe] == 0:
            A[qe] = arrow
            for r in R[qe]:
                Q.appendleft(r)
                Qa.appendleft(qe)

    if A[2:].count(0) > 0:
        print('No')
        exit()

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

def bfs(loads):
    visit = [-1] * len(loads)
    d = deque([0])
    visit[0] = 0
    
    while d:
        num = d.popleft()
        
        for l in loads[num]:
            if visit[l] != -1:
                continue
            
            d.append(l)
            visit[l] = num
        
        
    return visit

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

for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    loads[a].append(b)
    loads[b].append(a)
    
visit = bfs(loads)

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

Solution (Python):
import numpy as np
import networkx as nx
g = nx.Graph()

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

for _ in range(m):
    a, b = map(int, input().split())
    g.add_edge(a, b)

res = np.array([0] * 2 + [-1] * (n-1))

from collections import deque
q = deque([1])

while q:
    vis = q.popleft() 
    
    cands = list(nx.all_neighbors(g, vis)) 

    if cands:
        for c in cands:
            if res[c] == -1:
                res[c] = vis 
                q.append(c) 

if (res == -1).sum():
    print('No')
else:
    print('Yes')
    for i in res[2:]:
        print(i)

Solution (Python):
import sys
import collections
import heapq


def main():

    input = sys.stdin.readline

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

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

    ans_list = [0] * (N + 1)

    syori_list = []

    adjacent_dict = collections.defaultdict(list)

    
    for frm, to in edges:
        adjacent_dict[frm].append(to)
        adjacent_dict[to].append(frm)

    tmp_list = []
    tmp_list = adjacent_dict[1]
    for i in tmp_list:
        syori_list.append(i)
        ans_list[i] = 1

    for i in syori_list:
        tmp_list = adjacent_dict[i]
        for j in tmp_list:
            if ans_list[j] == 0:
                syori_list.append(j)
                ans_list[j] = i
    
    check_list = ans_list[2:]

    if check_list.count(0) > 0:
        print("No")
        return
    else:
        print("Yes")
    
    for i in check_list:
        print(i)

if __name__ == "__main__":
    main()

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

c = [set([]) for i in range(n)]

d = [n for i in range(n)]
d[0] = 0
dist = [set([]) for i in range(n+1)]
dist[0].add(1)
ans = [n for i in range(n)]
ans[0] = 0

for i in range(m):
    a,b = list(map(int, input().split(" ")))
    c[a-1].add(b)
    c[b-1].add(a)
    if a==1:
        d[b-1] = 1
        dist[1].add(b)
        ans[b-1] = 1
    if b==1:
        d[a-1] = 1
        dist[1].add(a)
        ans[a-1] = 1

for i in range(1, n):
    for one in dist[i]:
        
        
        for one2 in c[one-1]:
            
            if i<d[one2-1]:
                dist[i+1].add(one2)
                d[one2-1] = i+1
                ans[one2-1] = one

if n in d:
    print("No")
else:
    print("Yes")
    for i, one in enumerate(ans):
        if i!=0:
            print(one)

Solution (Python):
def check_road(start, road_array, mark_array):
    search_target = []
    search_target.append(start)

    while len(search_target) > 0:
        target = search_target[0]
        if len(road_array[target]) != 0:
            for road in road_array[target]:
                if road is not None and mark_array[road] is None and road != 1:
                    
                    
                    
                    mark_array[road] = target
                    search_target.append(road)
        del search_target[0]



N, M = map(int, input().split())
road_array = [[None] for i in range(N+1)]



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

mark_array = [None] * (N+1)
check_road(1, road_array, mark_array)
mark_array = mark_array[2:]

if None in mark_array:
    print('No')
else:
    print('Yes')
    for mark in mark_array:
        print(mark)

Solution (Python):
import queue
n,m=map(int,input().split())
road_list=[set() for i in range(n)]
mitisirube=[0]*n
mitisirube[0]=1
for i in range(m):
    a,b=map(int,input().split())
    road_list[a-1].add(b)
    road_list[b-1].add(a)

q = queue.Queue()

counter_set=set()
counter_set.add(1)
for i in road_list[0]:
    q.put(i)
    mitisirube[i-1]=1
    counter_set.add(i)

while not q.empty():
    tmp=q.get()
    for i in road_list[tmp-1]:
        if i not in counter_set:
            q.put(i)
            counter_set.add(i)
            if mitisirube[i-1]==0:
                mitisirube[i-1]=tmp

if mitisirube.count(0)>0:
    print("No")
else:
    print("Yes")
    for i in range(1,len(mitisirube)):
        print(mitisirube[i])

Solution (Python):
from collections import deque

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

d = deque()

dic = dict()
for i in range(m):
    p = path[i]
    if p[0] not in dic:
        dic[p[0]] = [p[1]]
    else:
        dic[p[0]].append(p[1])
    if p[1] not in dic:
        dic[p[1]] = [p[0]]
    else:
        dic[p[1]].append(p[0])
        
sign = [0]*n
done = [0]*n
done[0] = 1

for i in dic[1]:
    d.appendleft(i)
    sign[i-1] = 1
    done[i-1] = 1

while len(d) > 0:
    x = d.pop()
    for i in dic[x]:
        if done[i-1] == 0:
            d.appendleft(i)
            sign[i-1] = x
            done[i-1] = 1
        
print("Yes")
for i in range(n-1):
    print(sign[i+1])

Solution (Python):
from collections import deque

n,m=list(map(int,input().split()))
R=[[] for _ in range(n)]
sign=[0 for _ in range(n-1)]
dp=[0 for _ in range(n)]

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

start=deque()
start.append(0)
dp[0]=1

while start:
  s=start.popleft()
  for r in R[s]:
    if dp[r-1]:
      continue
    sign[r-2] = s + 1
    start.append(r-1)
    dp[r-1]=1

if 0 in sign:
  print("No")
else:
  print("Yes")
  for s in sign:
    print(s)

Solution (Python):
from collections import deque

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

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

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





queue = deque([1])
d = [None] * (N+1) 
d[1] = 0 
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = v
      queue.append(i)





















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

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



print('Yes')

ans = [None]*N

q = deque([0])

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

while q:
    now = q.popleft()
    
    for v in edge[now]:
        if ans[v] == None:
            ans[v] = now
        if tmp[v] != -1:
            if tmp[now]+1 < tmp[v]:
                tmp[v] = tmp[now]+1
                ans[v] = now
            continue
        tmp[v] = tmp[now] + 1
        q.append(v)
    
for c in ans[1:]:
    print(c+1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
 
for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)



check = [-1]*(N)
check[0] = 0

q = deque([0])

while q:
	
	p = q.popleft()
	
	for x in graph[p]:
		
		if check[x] == -1:
			check[x] = p+1
			q.append(x)


if -1 in check:
	print("No")
	exit()
else:
	print("Yes")

for i in range(1, N):
	print(check[i])

Solution (Python):


import queue
ans = [0]*1000001
done = [0]*100001
dict = {}
next = []
q = queue.Queue()

def nanka(before, now):
    
    if ans[now-1] == 0:
        ans[now-1] = before
        done[now] = 1
        for tt in dict[now]:
            if done[tt] == 1:
                continue
            elif tt not in next:
                q.put([now,tt])

def main():
    N ,M  =  [int(i) for i in input().split()]

    road = []
    for i in range(M):
        a, b = [int(i) for i in input().split()]
        if a not in dict.keys():
            dict[a] = [b]
        else:
            dict[a].append(b)
        if b not in dict.keys():
            dict[b] = [a]
        else:
            dict[b].append(a)
    

    mins = [1000000] * N

    for j in dict[1]:
        before = 1
        now = j
        nanka(1,j)
    while not q.empty():
        kk = q.get()
        nanka(kk[0],kk[1])
        
    if 0 in ans[1:N]:
        print("No")
    else:
        print("Yes")
        for i in ans[1:N]:
            print(i)
    


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
ans=[-1]*n
visited=[True]*n
stack=deque([0])
visited[0]=False
while stack:
    x=stack.popleft()
    for nx in edge[x]:
        if visited[nx]:
            visited[nx]=False
            stack.append(nx)
            ans[nx]=x
for i in range(1,n):
    if visited[i]:
        print("No")
        exit()
print("Yes")
for i in ans[1:]:
    print(i+1)

Solution (Python):
from collections import defaultdict as dd

N,M = map(int,input().split())
A2B = dd(list)
B2A = dd(list)
for a in range(M):
    A,B = input().split()
    A2B[A].append(B)
    B2A[B].append(A)
    

nodes_seek = set([str(x) for x in range(1,N+1)])


disc_nodes = set([])


shortest_path = dd(list)

shops = dd(int)

sprev = dd(str)



nxt_nodes = dd(list)
nxt_nodes["1"] = A2B["1"]
nxt_nodes["1"] += B2A["1"]


shops["1"] = 0
shortest_path["1"] = []
sprev["1"]=[]
disc_nodes.add("1")




count = 0

while len(disc_nodes) < N:
    
    nnxt_nodes = dd(list)
    for key in nxt_nodes.keys():
        
        tnxt_nodes = set(nxt_nodes[key]) - disc_nodes
    
        for n in tnxt_nodes:
            
            
            shops[n] = shops[key]+1
            sprev[n] = str(key)            
            
            
            disc_nodes.add(n)
            
            
            nnxt_nodes[n] += A2B[n]
            nnxt_nodes[n] += B2A[n]
    nxt_nodes = nnxt_nodes





ans = 'Yes'
       






    


    




for i in range(1,N+1):
    if i == 1:
        print(ans)
    else:

        print(sprev[str(i)])

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

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
nodes = [[] for _ in range(n)]
costs = [n+1 for i in range(n)]
costs[0] = 0
oyas = [None for _ in range(n)]

for tmp in ab:
    nodes[tmp[0]-1].append(tmp[1]-1)
    nodes[tmp[1]-1].append(tmp[0]-1)


op_l = [(costs[0]+1, no, 0) for no in nodes[0]]
heapify(op_l)

while True:
    if len(op_l) == 0:
        break
    cost, node, oya = heappop(op_l)
    if oyas[node] is not None:
        continue
    else:
        costs[node] = cost
        oyas[node] = oya
        for ko in nodes[node]:
            if ko == 0 or oyas[ko] is not None:
                continue
            else:
                tmp = (costs[node]+1, ko, node)
                heappush(op_l, tmp)

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

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

to = [[] for _ in range(110000)]
ans = [0] * 110000
queue = []
passed = [0] * 110000
passed[1] = 1

def search(i):
  global queue
  global passed
  global ans
  for j in to[i]:
    if passed[j] == 0:
      queue.append(j)
      passed[j] = 1
      ans[j] = i
  


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

search(1)
queue.append(1)

while queue:
  que = queue.pop(0)
  search(que)


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

Solution (Python):
from collections import OrderedDict, defaultdict, deque
from enum import Enum
from typing import Dict, Optional


class State(Enum):
    UNVISITED = 0
    VISITED = 1


class Node(object):
    def __init__(self, key: int) -> None:
        self.adj_nodes: Dict[int, Node] = {}  
        self.key: int = key
        self.state = State.UNVISITED

    def __repr__(self):
        return "<Node {}>".format(self.key)

    def add_adj_node(self, key) -> None:
        if key not in self.adj_nodes.keys():
            self.adj_nodes[key] = Node(key)


class Graph:
    def __init__(self) -> None:
        self.nodes: Dict[int, Node] = {}

    def add_node(self, key) -> None:
        if key not in self.nodes.keys():
            self.nodes[key] = Node(key)

    def add_edge(self, source: int, dest) -> None:
        if not self.get_node(source):
            self.add_node(source)
        if not self.get_node(dest):
            self.add_node(dest)

        self.get_node(source).add_adj_node(dest)

    def get_node(self, key) -> Optional[Node]:
        try:
            return self.nodes[key]
        except KeyError:
            return None


class BFS:
    def __init__(self, g: Graph, start_key: int):
        self.graph = g
        self.start_key = start_key
        self.history: Dict[int, int] = {}

    def solve(self):
        n = self.graph.get_node(self.start_key)
        n.state = State.VISITED
        queue = deque()
        queue.append(n.key)
        while queue:
            n_key = queue.popleft()
            n = self.graph.get_node(n_key)

            for adj_node_key in n.adj_nodes:
                adj_node = self.graph.get_node(adj_node_key)
                if adj_node.state == State.UNVISITED:
                    self.history[adj_node_key] = n.key
                    adj_node.state = State.VISITED
                    self.visit_func(adj_node_key)
                    queue.append(adj_node_key)

    def visit_func(self, node_key):
        raise NotImplementedError


class Ans(BFS):
    def __init__(self, g, n, start_key=1):
        super().__init__(g, start_key)
        self.n = n
        self.dist = {x: -1 for x in range(1, n + 1)}
        self.dist[self.start_key] = 0

    def visit_func(self, node_key):
        if node_key != self.start_key:
            prev_dist = self.dist[self.history[node_key]]
            self.dist[node_key] = prev_dist + 1

    def show_results(self, n):
        if -1 in set(self.dist.values()):
            print("No")
            return
        print("Yes")
        for i in range(2, n + 1):
            print(self.history[i])


if __name__ == "__main__":
    n, m = map(int, input().split(" "))
    G = Graph()
    for i in range(n):
        G.add_node(i + 1)

    for _ in range(m):
        a, b, = map(int, input().split(" "))
        
        G.add_edge(a, b)
        G.add_edge(b, a)

    a = Ans(G, n)
    a.solve()
    
    a.show_results(n)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = LI()
A,B = LIR(M,2)

pt = edges_to_pt(A,B,N)
par = [0]*N
s = 0

n = len(pt)
d = [-1]*n
d[s] = 0
q = [s]
c = 1
while q:
    q1 = []
    for v in q:
        for u in pt[v]:
            if d[u] == -1:
                d[u] = c
                par[u] = v
                q1.append(u)
    q = q1
    c += 1

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

Solution (Python):
from collections import deque

class Cave():
    def __init__(self):
        self.graph = {}
    def add_room(self, r):
        self.graph[r] = []
    def add_passage(self, r1, r2):
        self.graph[r1].append(r2)
        self.graph[r2].append(r1)
    def next_rooms(self, r):
        return self.graph[r]
    def __str__(self):
        return self.graph.__str__()

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

    cave = Cave()
    for i in range(1, N+1):
        cave.add_room(i)
    for r1, r2 in AB:
        cave.add_passage(r1, r2)

    q = deque()
    q.append(1)
    visited = [0]*(N+1)
    visited[1] = -1

    while q:
        r_now = q.popleft()
        for r_next in cave.next_rooms(r_now):
            if visited[r_next] == 0:
                visited[r_next] = r_now
                q.append(r_next)

    print('Yes')
    for i in visited[2:]:
        print(i)
main()

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10000000)
N, M = map(int, input().split())
class tree():
    def __init__(self):
        self.num = 0
        self.flag = 0
        self.step = -1
        self.leaf = []

li = [tree() for i in range(N)]
def saiki(que, step):
    pop = que.popleft()
    li[pop].flag = 2


    for i in range(len(li[pop].leaf)):
        if li[li[pop].leaf[i]].flag == 0:
            que.append(li[pop].leaf[i])
            li[li[pop].leaf[i]].flag = 1
            if li[li[pop].leaf[i]].step != -1:
                if li[li[pop].leaf[i]].step > li[pop].step + 1:
                    li[li[pop].leaf[i]].step = li[pop].step + 1
                    li[li[pop].leaf[i]].num = pop
            else:
                li[li[pop].leaf[i]].step = li[pop].step + 1
                li[li[pop].leaf[i]].num = pop


    
    if len(que) != 0:
        saiki(que, li[pop].step)
for i in range(M):
    A, B = map(int, input().split())
    li[A-1].leaf.append(B-1)
    li[B-1].leaf.append(A-1)

que = deque()
que.append(0)
li[0].step = 0
saiki(que, 0)
flag = 1

for i in range(len(li)):
    if li[i].flag == 0:
        flag = 0
        break
if flag == 0:
    print("No")
else:
    print("Yes")
for i in range(1, len(li)):
    print(li[i].num+1)

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

def bfs(start):
    queue = deque()
    visited = [False] * n
    visited[start-1] = True
    queue.append(start)
    while queue:
        target = queue.popleft()
        for i in g[target]:
            if not visited[i-1]:
                ans[i-2] = target
                visited[i-1] = True
                queue.append(i)

ans = [0] * (n-1)
g = dict()
for a, b in AB:
    if a in g:
        g[a].append(b)
    if b in g:
        g[b].append(a)
    if a not in g:
        g[a] = [b]
    if b not in g:
        g[b] = [a]
start = 1
bfs(start)
if len([i for i in ans if i == 0]) == 0:
    print("Yes")
    print(*ans, sep="\n")
else:
    print("No")

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

for i in range(m):
    aa, bb = map(int,input().split())

    if aa not in dic:
        dic[aa] = set()
        dic[aa].add(bb)
    else:
        dic[aa].add(bb)

    if bb not in dic:
        dic[bb] = set()
        dic[bb].add(aa)
    else:
        dic[bb].add(aa)

dist = 0
visited = set()

sirube = {}

queue = deque([1])
dist_dic = {}
dist_dic[1] = 0

while len(queue) != 0:
    v = queue.popleft()
    visited.add(v)
    
    for i in dic[v]:
        if i not in visited:
            visited.add(i)
            queue.append(i)
            dist_dic[i] = dist_dic[v] + 1
            sirube[i] = v

print("Yes")

sirube_sorted = sorted(sirube.items(), key=lambda x:x[0])

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

Solution (Python):
from collections import deque

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

tree=[[0] for _ in range(N)]

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

dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
ans=[0 for _ in range(N)]
for i in range(1,N):
    for t in tree[i]:
        if dist[t]==dist[i]-1:
            ans[i]=t+1
            break

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

Solution (Python):
N,M = map(int,input().split())
ans = {i:0 for i in range(1,N+1)}
ans[1] = 10000000
route = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    route[a].add(b)
    route[b].add(a)
x = {1}
for _ in range(N+1):
    tmp = set()
    count = 0
    for i in x:
        for j in route[i]:
            
            if ans[j] == 0:
                ans[j] = i
                count += 1
                tmp.add(j)
    x = tmp
    
    if count == 0:
        break
check = 0
for i in ans.keys():
    if i != 1:
        if ans[i] == 0:
            check = 1
if check == 1:
    print('No')
else:
    print('Yes')
    for i in ans.keys():
        if i != 1:
            print(ans[i])

Solution (Python):


import sys
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, M = iim()
    it = map(int, sys.stdin.read().split())

    d1 = defaultdict(list)

    for i, j in zip(it, it):
        d1[i].append(j)
        d1[j].append(i)

    ans = [0] * (N+1)
    dq = [1]
    visited = set([1])

    updated = True
    while updated:
        updated = False
        dq2 = []
        for i in dq:
            for j in d1[i]:
                if j in visited:
                    continue
                ans[j] = i
                dq2.append(j)
                visited.add(j)
                updated = True
        dq = dq2

    if len(visited) == N:
        print("Yes", *ans[2:], sep="\n")
    else:
        print("No")






if __name__ == "__main__":
    resolve()

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

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

ps = [-1] * n
ps[0] = 0
tmps = {}
for _ in range(m):
    a,b=map(int,input().split())
    ai,bi=a-1,b-1
    if ai not in tmps:
        tmps[ai] = []
    tmps[ai].append(bi)
    if bi not in tmps:
        tmps[bi] = []
    tmps[bi].append(ai)



if 0 not in tmps:
    print("No")
    exit()


def puts(ks):
    nks = []
    for k in ks:
        _nks = tmps[k]
        for nk in _nks:
            if ps[nk] == -1:
                ps[nk] = k
                nks.append(nk)
    if nks == []:
        return None
    
    return nks

ks = [0]
while True:
    nks = puts(ks)
    if nks is None:
        break
    else:
        ks = nks



if -1 in ps:
    print("No")
    exit()

print("Yes")
for p in ps[1:]:
    print(p+1)

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

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

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

que = [0]
while que:
    for i in tunagari[que[0]]:
        if sirusi[i] == -1:
            sirusi[i] = que[0]
            que.append(i)
    que.pop(0)

sirusi.pop(0)
print("Yes")
for i in sirusi:
    print(i+1)

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

s=0
d=[10**20]*n
used=[False]*n
used[s]=True
d[s]=0
edgelist=[]
fromv=[-1]*n

for e in edge[s]:
  e.append(s)
  heapq.heappush(edgelist,e)
while len(edgelist):
  minedge=heapq.heappop(edgelist)
  v=minedge[1]
  if used[v]:
    continue
  d[v]=minedge[0]
  used[v]=True
  fromv[v]=minedge[2]
  for e in edge[v]:
    if not used[e[1]]:
      heapq.heappush(edgelist,[e[0]+d[v],e[1],v])
      fromv[e[1]]=v
if any([x==-1 for x in fromv[1:]]):
  print('No')
else:
  print('Yes')
  for x in fromv[1:]:
    print(x+1)

Solution (Python):
from heapq import heappop, heappush
from collections import deque


def solve():
    N, M = map(int, input().split())
    loadmap = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        loadmap[A].append(B)
        loadmap[B].append(A)

    dbrmap = [[float('inf'), -1, 0] for _ in range(N + 1)]  

    
    rooms = deque()
    rooms.append([0, 1, 0])
    dbrmap[1][2] = 1
    while rooms:
        
        br, r, d = rooms.popleft()
        if d <= dbrmap[r][0]:
            
            dbrmap[r][0] = d
            dbrmap[r][1] = br
            
            for load in loadmap[r]:
                
                if dbrmap[load][2] == 0:
                    rooms.append([r, load, d + 1])
                    dbrmap[load][2] = 1

    if min([db[1] for db in dbrmap[1:]]) <= -1:
        print('No')
    else:
        print('Yes')
        for db in dbrmap[2:]:
            print(db[1])


if __name__ == '__main__':
    solve()

Solution (Python):

import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


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

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

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

OK_flag = True

dic = {}
for i in range(n):
    if d[i] == float("inf"):
        OK_flag = False
    dic[d[i]] = i


if OK_flag == True:
    print("Yes")
    for i in range(1, n):
        print(dic[d[i]-1]+ 1)
else:
    print("No")

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

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


next_visited = [1]
visited = {1:None}
temp_next = []

visit_num = {}
count = 0

while True:
  temp_next = []
  for room in next_visited:
    ava_room = road[room]
    for r in ava_room:
      try:
        visited[r]
      except:
        visit_num[r] = room
        temp_next.append(r)
        visited[r] = None
        
  if temp_next == []:
    break
  next_visited = temp_next

if len(visit_num) != n-1:
  print('No')

else:
  print('Yes')
  for v in sorted(visit_num.items()):
    print(v[1])

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

import sys

input = sys.stdin.readline
R = [[] for _ in range(n)]
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0

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

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

if min(Dis)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])