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


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


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

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

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



ans[0] = -1
d = deque()


for i in ar[0]:
    d.append(i)
    ans[i-1] = 1



while d:
    i = d.popleft()
    
    
    for x in ar[i-1]:
        if(ans[x-1] == 0):
            ans[x-1] = i
            d.append(x)




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

Solution (Python):
from collections import deque
INF = 100001000100
n, m = [int(i) for i in input().split()]
room = [[] for _ in range(n)]
room_dis = [INF for _ in range(n)]
sign_post = [0 for _ in range(n)]


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


d = deque([0])
dist = 1
room_dis[0] = 0

while len(d) != 0:
	tmp = d.popleft()
	for next in room[tmp]:
		if room_dis[next] > room_dis[tmp]+1:
			sign_post[next] = tmp
			room_dis[next] = room_dis[tmp]+1
			d.append(next)

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

Solution (Python):
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys
nm = [int(s) for s in stdin.readline().rstrip().split()]
n = nm[0]
m = nm[1]
ab = []
for el in range(m):
    tmp = [int(s) for s in stdin.readline().rstrip().split()]
    ab.append(tmp)

data = []
for el in range(n):
    if el == 0:
        data.append({'index': el + 1, 'diff': 0, 'connection': [], 'num': 0})
    else:
        data.append({'index': el + 1, 'diff': 0, 'connection': []})
for el in ab:
    data[el[0]-1]['connection'].append(el[1])
    data[el[1]-1]['connection'].append(el[0])
poss = [1]
count = 1

for elt in range(n):
    tmp = []
    for el in poss:
        for el2 in data[el - 1]['connection']:
            if not 'num' in data[el2-1]:
                tmp.append(el2)
                data[el2-1]['num'] = el
    else:
        poss = tmp
        count += 1

check = True
for el in data:
    if not 'num' in el:
        check = False
if check:
    print('Yes')
    tmp = 0
    for el in data:
        if tmp != 0:
            print(el['num'])
        tmp += 1
if not check:
    print('No')

Solution (Python):
from collections import deque



n,m=map(int,input().split())
g = [[] for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([(0,-1)])
d=[-1]*n
d[0]=0
res={}
while len(q)>0:
    u,r = q.popleft()
    for v in g[u]:
        if d[v] == -1 and r != v:
            d[v] = d[u] + 1
            q.append((v,u))
            if not v-1 in res:
                res[v-1] = u+1
res = sorted(res.items())
if len(res) != n-1:
    print("No")
    exit()
print("Yes")
for i,j in res:
    print(j)

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


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    
    def sp(self, goal):
        path = []
        node = goal
        for _ in range(2):
            path.append(node)
            node = self.prev[node]
        return path[1]

n, m = map(int, input().split())
g = Graph()
for i in range(m):
    a, b = map(int, input().split())
    g.add_edge(a-1, b-1, 1)
    g.add_edge(b-1, a-1, 1)

d = Dijkstra(g, 0)
A = []

for i in range(n):
    a = d.shortest_distance(i)
    if a == float('inf'):
        print("No")
        break
    else:
        A.append(d.shortest_distance(i))

if len(A) == n:
    print("Yes")
    for i in range(1, n):
        print(d.sp(i) + 1)

Solution (Python):
import numpy as np
import heapq

if __name__ == "__main__":
    N, M = map(int, input().split())
    nodes = [[] for i in range(N)]
    costs = [N+1 for i in range(N)]
    costs[0] = 0
    parents = [None for i in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        nodes[a-1].append(b-1)
        nodes[b-1].append(a-1)
    
    open_list = [(costs[0]+1, c, 0) for c in nodes[0]]
    heapq.heapify(open_list)

    while True:
        
        
        
        
        
        
        
        
        if len(open_list) == 0:
            break
        cost, node, parent = heapq.heappop(open_list)
        if parents[node] is not None:
            
            continue
        else:
            
            costs[node] = cost
            parents[node] = parent
            for child in nodes[node]:
                
                if child == 0 or parents[child] is not None:
                    continue
                else:
                    t = (costs[node]+1, child, node)
                    heapq.heappush(open_list, t)
        
    
    
    for i in range(N):
        if i == 0:
            print('Yes') 
        else:
            print(parents[i]+1)

Solution (Python):




import sys
from io import StringIO
import unittest

sys.setrecursionlimit(100000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def xxx(t,memo,ans,kyori):
    for a in memo[t]:
        if ans[a] == -1 or kyori[a] > (kyori[t]+1):
            ans[a]=t
            kyori[a]=kyori[t]+1
            xxx(a,memo,ans,kyori)


def resolve():
    readline=sys.stdin.readline

    n,m=map(int, readline().rstrip().split())
    memo=[[] for i in range(n)]
    ans=[-1]*n
    kyori=[-1]*n
    ans[0]=0
    kyori[0]=0
    for i in range(m):
        a,b=map(int, readline().rstrip().split())
        memo[a-1].append(b-1)
        memo[b-1].append(a-1)
    
    tt=[0]
    while 1:
        nx=[]
        for t in tt:
            for a in memo[t]:
                if ans[a] == -1 or kyori[a] > (kyori[t]+1):
                    nx.append(a)
                    ans[a]=t
                    kyori[a]=kyori[t]+1
        if len(nx)==0:
            break
        else:
            tt=nx
        
    

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


    
    
    
    

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

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


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    
    def sp(self, goal):
        path = []
        node = goal
        for _ in range(2):
            path.append(node)
            node = self.prev[node]
        return path[1]

n, m = map(int, input().split())
g = Graph()
for i in range(m):
    a, b = map(int, input().split())
    g.add_edge(a-1, b-1, 1)
    g.add_edge(b-1, a-1, 1)

d = Dijkstra(g, 0)
A = []

for i in range(n):
    a = d.shortest_distance(i)
    if a == float('inf'):
        print("No")
        break
    else:
        A.append(d.shortest_distance(i))

if len(A) == n:
    print("Yes")
    for i in range(1, n):
        print(d.sp(i) + 1)

Solution (Python):
import collections

def BFS(G, s):
    visited = {s: None}
    unvisited = collections.deque([s])
    while unvisited:
        u = unvisited.popleft()
        for v in G[u - 1]:
            if not(v in visited):
                unvisited.append(v)
                visited[v] = u
    
    return visited

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

g = [set([]) for _ in range(n)]

for abi in ab:
    g[abi[0] - 1].add(abi[1])
    g[abi[1] - 1].add(abi[0])

ans = [0] * (n - 1)

for k, v in BFS(g, 1).items():
    if k == 1:
        continue
    else:
        ans[k - 2] = v

print("Yes")
for num in ans:
    print(num)

Solution (Python):
from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
R = [-1] * N



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

d = deque()
d.append(0)

while d:
    v = d.popleft()
    for g in G[v]:
        if g != 0 and R[g] == -1:
            d.append(g)
            R[g] = v + 1

if -1 in R[1:]:
    print("No")
else:
    print("Yes")
    for r in R[1:]:
        print(r)

Solution (Python):


from collections import deque
n,m = map(int,input().split())
g = {key:[] for key in range(n)}
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

d = deque([(0,g[0])])
C = {0:"Yes"}

while d != deque([]):
    
    c = d.popleft()
    for i in c[1]:
        if i in C:
            continue
        else:
            d.append((i,g[i]))
            C[i] = c[0]+1

for i in range(n):
    if len(C) != n:
        print("No")
        break
    if i == 0:
        print("Yes")
    else:
        print(C[i])

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

n,m=map(int,input().split())
edges=[[] for i in range(n)]
table=[-1]*n
for i in range(m):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)
l=[0]
print()
from collections import deque as que
q=que([(-1,0)])
p=que()
flag=1
ok=0
while flag:
    flag=0
    while len(q):
        flag=1
        pre,now=q.pop()
        if table[now]==-1:
            ok+=1
            table[now]=pre+1
            for i in edges[now]:
                if table[i]==-1:
                    p.append((now,i))
    p,q=q,p






if ok==n:
    print("Yes")
    for i in range(1,n):
        print(table[i])
else:print("No")

Solution (Python):

import collections

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

linked_room = [[] for i in [1] * n]
sign = [0] * n
sign[0] = 1
arrivable_rooms = 0

for mi in range(m):
    tmp_a, tmp_b = map(int, input().split())
    linked_room[tmp_a-1].append(tmp_b)
    linked_room[tmp_b-1].append(tmp_a)

work_q = collections.deque([1])

while len(work_q) > 0:
    past_room = work_q.pop()

    next_rooms = linked_room[past_room-1]
    for nri in next_rooms:
        if sign[nri - 1] == 0:
            sign[nri - 1] = past_room
            arrivable_rooms += 1
            work_q.appendleft(nri)

if arrivable_rooms == n-1:
    print('Yes')
    for si in sign[1:n]:
        print(si)
else:
    print('No')

Solution (Python):
import math
from queue import Queue

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

gh = {}
for i in range(m):
    p1, p2 = map(int, input().split(" "))
    if p1 in gh:
        gh[p1].append(p2)
    else:
        gh[p1] = [p2]

    if p2 in gh:
        gh[p2].append(p1)
    else:
        gh[p2] = [p1]

_mp = [-1 for _ in range(n)]
_mp[0] = 0
q = Queue()
q.put(1)

while q.qsize() != 0:
    cp = q.get()
    for p in gh[cp]:
        if _mp[p - 1] != -1: continue
        q.put(p)
        _mp[p - 1] = cp

for k, v in gh.items():
    if len(v) == 0:
        print("No")
        exit()

print("Yes")
for mpi in _mp[1:]:
    print(mpi)

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


used = [False] * N
d = [0] * N
now_list = [(0,0,-1)]
next_list = set()
while len(now_list) > 0:
    for _ in range(len(now_list)):
        c, v, pv = now_list.pop()
        if used[v]: continue
        d[v] = pv
        used[v] = True
        for nc, nv in edge[v]:
            if used[nv]: continue
            if v == nv: continue
            next_list.add((nc+c, nv, v))
    now_list = list(next_list)
    next_list = set()

judge = all(d[i] > -1 for i in range(1,N))
if judge:
    print("Yes")
    for i in d[1:]:
        print(i+1)
else:
    print("No")

Solution (Python):

from collections import deque
def q4():
    class Room:
        def __init__(self, i):
            self.id = i
            self.d = -1
            self.next = []
            self.sign = -1

        def add_next(self, n):
            self.next.append(n)

        def print(self, tab=0, printed=[]):
            if self.id in printed:
                return
            printed.append(self.id)
            print("  " * tab + str(self.id) + f"({self.sign})")
            for n in self.next:
                n.print(tab + 1, list(printed))
    
        
    N, M = [int(i) for i in input().split(" ")]
    room_dict = {}

    def get_room(i):
        if i in room_dict:
            return room_dict[i]
        else:
            room = Room(i)
            room_dict[i] = room
            return room

    for i in range(M):
        A, B = [int(i) for i in input().split(" ")]
        get_room(A).add_next(get_room(B))
        get_room(B).add_next(get_room(A))


    d = 0
    sign = -1
    queue = deque([[get_room(1), d, sign]])
    while queue:
        room, d, sign = queue.popleft()
        if room.sign != -1:
            continue
        room.sign = sign
        room.d = d
        for n in room.next:
            queue.append([n, d + 1, room.id])

    print("Yes")
    for i in range(2, N + 1):
        print(get_room(i).sign)

q4()

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
AB = []
d = defaultdict(set)
for _ in range(M):
    a, b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
    AB.append([a, b])

ans = [0] * N
ans[0] = -1
a = [1]
dis_to_goal = [0] * N
dis_to_goal[0] = 0
dis = 0
mem = set()
while True:
    b = []
    dis += 1
    for k in a:
        if k in mem:
            continue
        mem.add(k)
        for n in d[k]:
            if ans[n - 1] == 0:
                ans[n - 1] = k
                dis_to_goal[n - 1] = dis
                b.append(n)
    if len(mem) == N:
        break
    a = b.copy()




for i, u in enumerate(ans[1:]):
    if dis_to_goal[i+1] - dis_to_goal[u-1] == 1:
        continue
    else:
        print('No')
        exit()
print('Yes')
for k in ans[1:]:
    print(k)

Solution (Python):
N, M = map(int, input().split())
nlist = [[] for i in range(N+1)]

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




def bfs():
    nstep = 1
    queue = [1]
    min_dist = [0]*N
    
    while True:
        if len(queue)==0:
            break
        ncurrent = queue[0]
        queue.pop(0)
        
        for i in nlist[ncurrent]:
            if min_dist[i-1]!=0:
                continue
            queue.append(i)
            min_dist[i-1] = min_dist[ncurrent-1] + 1
    return min_dist
ret=bfs()

if 0 in ret:
    print("No")
else:
    print("Yes")
    dist2n = {r:i+1 for i, r in enumerate(ret)}
    for i in range(1,len(ret)):
        if ret[i]==1:
            print(1)
        else:
            print(dist2n[ret[i]-1])

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


room_set = set()
aisle_dict = dict()

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

    if a in room_set:
        aisle_dict[a].append(b)
    else:
        room_set.add(a)
        aisle_dict[a] = [b]

    if b in room_set:
        aisle_dict[b].append(a)
    else:
        room_set.add(b)
        aisle_dict[b] = [a]


visit_room = {1}
signpost = dict()
now_rooms= [1]

while len(visit_room) < n:
    tmp_now_rooms = []

    for now_room in now_rooms:
        for connect_room in aisle_dict[now_room]:
            if connect_room not in visit_room:
                signpost[connect_room] = now_room
                tmp_now_rooms.append(connect_room)
                visit_room.add(connect_room)

    now_rooms = tmp_now_rooms

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

Solution (Python):
from collections import deque

N, M = map(int, input().split())
g = [[int(i) for i in input().split()] for j in range(M)]

G = [[] for i in range(N)]
for i in range(M):
    a, b = g[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

marks = [-1 for i in range(N)]
node = deque([[0, 0]])
while len(node) > 0:
    v = node.popleft()
    if marks[v[0]] == -1:
        marks[v[0]] = v[1]
        for i in G[v[0]]:
            if marks[i] == -1:
                node.append([i, v[0]])

if -1 not in marks:
    print("Yes")
    for i in range(1, N):
        print(marks[i]+1)
else:
    print("No")

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

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

from collections import deque
def bfs(start):
    dist = [INF] * N
    dist[start] = 0
    seen = [0] * N
    shirube = [None] * N
    shirube[0] = 'Yes'
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for next_room in graph[v]:
            if seen[next_room]:
                continue
            if dv + 1 < dist[next_room]:
                dist[next_room] = dv + 1
                shirube[next_room] = v + 1
            seen[next_room] = 1
            q.append(next_room)
    if all(shirube):
        for x in shirube:
            print(x)
    else:
        
        print('No')
bfs(0)

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10



N, M = [int(x) for x in stdin.readline().rstrip().split()]

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

for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    route[A].append(B)
    route[B].append(A)


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

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

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



que = deque([1])


while len(que) != 0:
    now = que.popleft()
    
    if is_visited[now]:
        continue

    is_visited[now] = True

    for place in route[now]:
        que.append(place)

        if kyori_to_1[now]+1 < kyori_to_1[place]:
            kyori_to_1[place] = kyori_to_1[now]+1
            miti[place] = now

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

Solution (Python):
from collections import deque
import sys
if __name__ == "__main__":
    n, m = map(int, input().split())
    distance = [float('inf')] * n
    prev_node = [-1] * n
    visit = [False] * n
    graph = []
    for i in range(n):
        graph.append([])
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    
    que = deque()
    que.appendleft((0, 0))
    distance[0] = 0
    visit[0] = True

    while que:
        now, cost = que.pop()
        for nei in graph[now]:
            if not visit[nei]:
                prev_node[nei] = now
                distance[nei] = cost + 1
                que.appendleft((nei, cost + 1))
                visit[nei] = True

    for i in range(1, n):
        if distance == float('inf'):
            print("No")
            sys.exit(0)
    print("Yes")
    for i in range(1, n):
        print(prev_node[i] + 1)

Solution (Python):
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
connections = [[] for _ in range(N)]
for a, b in AB:
    connections[a - 1].append(b - 1)
    connections[b - 1].append(a - 1)
    
markers = [-1] * N
    
queue = [0]
steps = [-1] * N
steps[0] = 0
while len(queue) >= 1:
    room = queue.pop(0)
    for r in connections[room]:
        if steps[r] >= 0:
            continue
        queue.append(r)
        steps[r] = steps[room] + 1
        markers[r] = str(room + 1)
    
print("Yes")
print("\n".join(markers[1:]))

Solution (Python):
from collections import defaultdict, deque

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

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

graph = defaultdict(set)

check = set([i + 1 for i in range(N)])

for a, b in AB:
    graph[a].add(b)
    graph[b].add(a)

    if a in check:
        check.remove(a)
    if b in check:
        check.remove(b)

if len(check) != 0:
    print('No')
    exit()

dq = deque([])
dq.append(1)


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

visited = set()
visited.add(1)
while dq:
    node = dq.popleft()

    for c in graph[node]:
        if c in visited:
            continue

        ans[c] = node
        visited.add(c)
        dq.append(c)


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

Solution (Python):
from collections import deque
n,m = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(m)]
r = [[] for _ in range(n)]
v = [0]*n
for ab in AB:
    r[ab[0]-1].append(ab[1])
    r[ab[1]-1].append(ab[0])
ans = [1]*(n-1)
d = deque()
d.append(1)
v[0] = 1
while d:
    p = d.popleft()
    for i in r[p-1]:
        if v[i-1]==0:
            d.append(i)
            ans[i-2] = p
            v[i-1] = 1
print('Yes')
for an in ans:
    print(an)

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

siru=[-1]*(N-1)
que=[0]

while len(que)>0:
    
    now=que.pop(0)
    nexlist=G[now]
    for nex in nexlist:
        if nex==0:
            continue
        if siru[nex-1]==-1:
            siru[nex-1]=now
            que.append(nex)
X=siru.count(-1)
if X>=1:
    print("No")
else:
    print("Yes")
    for num in siru:
        print(num+1)

Solution (Python):
from collections import deque

N, M = [int(s) for s in input().split()]
edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(N)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

dq = deque([0])
visited = [False] * N
visited[0] = True
parent = [0]*N
while(dq):
    search_obj = dq.pop()
    for candidate_obj in graph[search_obj]:
        if not visited[candidate_obj]:
            dq.appendleft(candidate_obj)
            parent[candidate_obj] = search_obj
            visited[candidate_obj] = True

total_visited = sum(visited)
if total_visited < N:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(parent[i]+1)

Solution (Python):



import sys
from collections import deque

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    tree = [set() for _ in range(N + 1)]
    sign = [None] * (N + 1)
    cnt = 0
    for _ in range(M):
        A, B = i2nn()
        tree[A].add(B)
        tree[B].add(A)
    que = deque([1])
    while que:
        
        seek = que.popleft()
        for n in tree[seek]:
            if sign[n] is not None:
                continue
            cnt += 1
            sign[n] = seek
            tree[n].discard(seek)
            que.append(n)
    if cnt < N - 1:
        print('No')
        return
    print('Yes')
    for s in sign[2:]:
        print(s)
    return

main()

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


dist = [-1] * (n + 1)
roots = [[] for i in range(n + 1)]

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

ans = [-1] * (n + 1)
ans[1] = 0
dist[1] = 0
q = deque()
q.append(1)

while q:
    now = q.popleft()

    for next_v in roots[now]:
        if not dist[next_v] == -1:
            continue
        dist[next_v] = dist[now] + 1
        ans[next_v] = now
        q.append(next_v)

if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in range(2, len(ans)):
        print(ans[i])

Solution (Python):
from collections import deque

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

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

def bfs(u):
    
    q = deque()
    q.append(u)
    while q:
        r = q.popleft()
        for v in R[r]:
            if S[v] == -1:
                S[v] = r
                q.append(v)

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

bfs(0)

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

Solution (Python):
def main():
    N, M = map(int, input().split())
    root_dict = dict()
    ans = [0] * N
    remaining_set = {i for i in range(2, N+1, 1)}
    for i in range(1, N+1, 1):
        root_dict[i] = set()
    for i in range(M):
        AB = list(map(int, input().split()))

        root_dict[AB[0]].add(AB[1])
        root_dict[AB[1]].add(AB[0])

    next_nodes = dict()
    next_nodes[1] = root_dict[1].copy()
    
    org_node = 1
    while(next_nodes):
        next_next_nodes = dict()
        if(len(remaining_set) == 0):
            break
        for org_node, nodes in next_nodes.items():
            for node in nodes:

                if(node in remaining_set):
                    ans[node-1] = org_node
                    remaining_set.remove(node)
                    if(node in next_next_nodes):
                        next_next_nodes.clear(node)
                    next_next_nodes_set = root_dict[node].intersection(remaining_set).difference(nodes)
                    if(len(next_next_nodes_set) != 0):
                        if(node in next_next_nodes):
                            next_next_nodes[node] = next_next_nodes[node].union(next_next_nodes_set)
                        else:
                            next_next_nodes[node] = next_next_nodes_set.copy()
                else:
                    continue
        next_nodes = next_next_nodes.copy()
    
    if(len(remaining_set) != 0):
        print("No")
    else:
        for i in range(N):
            if(i==0):
                print("Yes")
            else:
                print(ans[i])
    



main()

Solution (Python):
from collections import deque

''' Breadth First Search (BFS) '''
def bfs(x):
    q = deque([x])
    visited[x] = True
    while q:
        x = q.popleft()
        for y in adj[x]:
            if not visited[y]:
                q.append(y)
                visited[y] = True
                parent[y] = x

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
parent = [i for i in range(n + 1)]
visited = [False] * (n + 1)

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

bfs(1)
check = True
if i in range(2, n + 1):
  if parent[i] == i:
    check = False
if check:
  print("Yes")
  for i in range(2, n + 1):
    print(parent[i])
else:
  print("No")