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):
mNM = map(int, input().split())
lNM = list(mNM)

mWay = [map(int, input().split()) for i in range(lNM[1])]
lWay = [list(mWay[i]) for i in range(lNM[1])]

maps = [-1 for i in range(lNM[0])]
deep = [-1 for i in range(lNM[0])]
ways = [[] for i in range(lNM[0])]

for i in range(lNM[1]):
    ways[lWay[i][0] - 1].append(lWay[i][1])
    ways[lWay[i][1] - 1].append(lWay[i][0])

maps[0] = 0
deep[0] = 0
nexts = [0]

for i in range(lNM[0]):
    try:
        index = nexts     
        nexts = []
        
        for x in index:
            for w in ways[x]:
                if(deep[w - 1] == -1):
                    deep[w - 1] = i + 1
                    maps[w - 1] = x + 1
                    nexts.append(w - 1)
        
    except:
        pass
    
if(-1 in maps):
    print('No')
else:
    print('Yes')
    for i in maps[1:]:
        print(i)

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

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

while q:
	item = q.popleft()
	for i in ab[item]:
		if put[i]:
			flg[i-1]=item
			q.append(i)
			put[i]=0
 
if -1 in flg:
	print("No")
	exit()
 
print("Yes")
for i in range(1,len(flg)):
	print(flg[i])

Solution (Python):
from collections import deque
import math
N,M=map(int,input().split())
"""
BFSする。探索される側をメモ。
"""
dist = [-1 for i in range(N)]
graph = [[] for i in range(N+1)]
for i in range(M):
  A,B=map(int,input().split())
  graph[A].append(B)
  graph[B].append(A)
  



ans = [-1]*(N+1)
q = deque()
q.append(1)
while len(q)>0:
  
  node = q.popleft()
  for j in graph[node]:
    if ans[j] == -1:
      ans[j]=node
      q.append(j)
print("Yes")
print("\n".join(list(map(str,ans[2:]))))

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

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

    q = [(0,1,-1)]
    heapify(q)
    node[1] = 0

    while q:
        d,v,f = heappop(q)
        node[v] = d
        ans[v] = f
        for u in root[v]:
            if node[u] <= d+1: continue
            node[u] = d+1
            heappush(q,(d+1,u,v))

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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys


readline = sys.stdin.readline
readall = sys.stdin.read
ins = lambda: readline().rstrip()
ini = lambda: int(readline().rstrip())
inm = lambda: map(int, readline().split())
inl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')


n,m = inm()
W = [[] for _ in range(n)]
for _ in range(m):
    a,b = inm()
    W[a-1].append(b-1)
    W[b-1].append(a-1)

res = [0] * n
dis = [n] * n
dis[0] = 0

q = deque()
q.append(0)
while q:
    c = q.popleft()
    for i in W[c]:
        if dis[i] > dis[c] + 1:
            dis[i] = dis[c] + 1
            res[i] = c + 1
            q.append(i)

print('Yes')
prl(res[1:])

Solution (Python):
from collections import deque
N, M = map(int, input().split())
root = [set() for i in range(N + 1)]
ans = [0 for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    root[a].add(b)
    root[b].add(a)
task = deque([1])
itta = {1}
while len(task) > 0:
    now = task.popleft()
    additional = root[now] - itta
    for i in additional:
        ans[i] = now
        itta.add(i)
    task.extend(list(additional))
print("Yes")
for i in range(2, N + 1):
    print(ans[i])

Solution (Python):

import sys
import collections

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
adj = [[] for _ in range(N)]
for i in range(M):
    a, b = nm()
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def solve():
    q = collections.deque([(0, 0, -1)])
    visited = [False] * N
    prev = [None] * N
    while q:
        l, node, pnode = q.popleft()
        if visited[node]:
            continue
        visited[node] = True
        prev[node] = pnode
        for nxt in adj[node]:
            if not visited[nxt]:
                q.append((l + 1, nxt, node))
    print("Yes")
    for i in range(1, N):
        print(prev[i] + 1)


if __name__ == "__main__":
    solve()

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

def readInt():
	return int(input())
def readInts():
	return map(int, input().split())
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): 
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): 
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} 
def bitArr(n):
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): 
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq

n,m = map(int, input().split())
puted = [True]*(n+1)

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

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

while q:
	item = q.popleft()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.append(i)
			puted[i]=False

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

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

Solution (Python):
from collections import deque

n,m = list(map(int, input().split()))
puted = [True]*(n+1)

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

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

while q:
	item = q.popleft()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.append(i)
			puted[i]=False

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

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

Solution (Python):
from collections import deque

n,m = list(map(int, input().split()))
puted = [1]*(n+1)

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

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

while q:
	item = q.popleft()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.append(i)
			puted[i]=0

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

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

Solution (Python):
import queue

n,m = list(map(int, input().split()))
puted = [1]*(n+1)

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

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.put(i)
			puted[i]=0

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

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

Solution (Python):
import queue

n,m = list(map(int, input().split()))
puted = [1]*(n+1)

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

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]:
			flg[i-1]=item
			q.put(i)
			puted[i]=0

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

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

Solution (Python):
import queue

n,m = list(map(int, input().split()))
puted = [0]*(n+1)

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

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

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

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

Solution (Python):
import queue

n,m = list(map(int, input().split()))
puted = [0]*(n+1)

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

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

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

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

Solution (Python):


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)

parent = {i:-1 for i in range(1,n+1)}
parent[1] = 0
q = [1]
while len(q):
    u = q.pop(0)
    for v in graph[u]:
        if parent[v] == -1:
            q.append(v)
            parent[v] = u

if -1 in list(parent.values()):
    print("No")
    exit()
print("Yes")
for i in range(2,n+1):
    print(parent[i])

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
print("Yes")
for i in range(1,len(mitisirube)):
    print(mitisirube[i])

Solution (Python):
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

from collections import deque

def bfs(graph,s,n):
    visited=[False for _ in xrange(n+1)]
    ans = [None for _ in xrange(n+1)]
    stack=deque([s])
    while stack:
        node=stack.popleft()
        for nodes in graph[node]:
            if not visited[nodes]:
                if ans[nodes] is None:
                    ans[nodes] = str(node)
                stack.append(nodes)
                visited[nodes] = True
    return ans


n,m = (int(x) for x in input().split())
graph = dict()
for x in xrange(m):
    a,b = (int(x) for x in input().split())
    try:
        graph[a].append(b)
    except:
        graph[a] = [b]
    try:
        graph[b].append(a)
    except:
        graph[b] = [a]
ans = bfs(graph,1,n)
print('Yes')
print('\n'.join(ans[2:]))

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
print("Yes")
for i in range(1,len(mitisirube)):
    print(mitisirube[i])

Solution (Python):

from collections import deque
inf = float("INF")
 
N,M = map(int,input().split())
path = [[] for i in range(N)]
dist = [inf for i in range(N)]
visited = [0 for i in range(N)]
 
for _ in range(M):
    a,b = map(int,input().split())
    a = a - 1
    b = b - 1
    path[a].append(b)
    path[b].append(a)
 
def bfs(path,root,visited):
    
    dist[root] = 0
    
    visited[root] = 1
    
    queue = deque([root])
    
    while queue:
        
        current = queue.popleft()
        for i in path[current]:
            
            if visited[i] == 1:
                continue
            else:
                
                dist[i] = current + 1
                visited[i] = 1
                queue.append(i)
 
    if all([i == 1 for i in visited]):
        return "Yes"
    else:
        return "No"
 
flag = bfs(path,0,visited)
print(flag)
 
if flag == "Yes":
    for i in range(1,N):
        print(dist[i])

Solution (Python):

from collections import deque
from typing import List


def bfs(source, graph: List[List[int]], signposts: List[int]) -> None:
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not signposts[v]:
                signposts[v] = u
                queue.append(v)


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

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

    signposts = [0] * (N + 1)
    signposts[1] = 1
    bfs(1, graph, signposts)

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

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


way = [[] for i in range(N)]
depth = [float("inf") for i in range(N)]
visited = [False for i in range(N)]
que=[0]

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

for i in que:
  for j in way[i]:
    if visited[j]:
      continue
    que.append(j)
    visited[j]=True
    depth[j] = min(i+1,depth[j])
print("Yes")
for i in range(1,N):
  print(depth[i])

Solution (Python):

from collections import deque


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

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

    
    queue = deque([1])
    signposts = [0] * (N + 1)
    signposts[1] = 1
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not signposts[v]:
                signposts[v] = u
                queue.append(v)

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


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

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

    
    queue = deque([1])
    signposts = [0] * (N + 1)
    signposts[1] = 1
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not signposts[v]:
                signposts[v] = u
                queue.append(v)

    if all(signposts[2:]):
        print("Yes")
        print("\n".join(map(str, signposts[2:])))
    else:
        print("No")


if __name__ == "__main__":
    main()

Solution (Python):
import queue
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    p = q.get()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.put(c)
print('Yes')
for i in range(2,n+1): print(ans[i])

Solution (Python):

from collections import deque


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

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

    
    depth = [1 << 30] * (N + 1)
    depth[1] = 0
    queue = deque([(1, 0)])
    while queue:
        u, cur_depth = queue.popleft()
        next_depth = cur_depth + 1
        for v in graph[u]:
            if depth[v] > next_depth:
                depth[v] = next_depth
                queue.append((v, next_depth))

    
    signposts = [0] * (N + 1)
    for u, cur_depth in enumerate(depth[2:], 2):
        prev_depth = cur_depth - 1
        for v in graph[u]:
            if depth[v] == prev_depth:
                signposts[u] = v
                break

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


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

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

    
    depth = [1 << 30] * (N + 1)
    depth[1] = 0
    queue = deque([(1, 0)])
    while queue:
        u, cur_depth = queue.popleft()
        next_depth = cur_depth + 1
        for v in graph[u]:
            if depth[v] > next_depth:
                depth[v] = next_depth
                queue.append((v, next_depth))

    
    signposts = [0] * (N + 1)
    for u, cur_depth in enumerate(depth[2:], 2):
        prev_depth = cur_depth - 1
        for v in graph[u]:
            if depth[v] == prev_depth:
                signposts[u] = v
                break
        if not signposts[u]:
            print("No")
            return

    print("Yes")
    print("\n".join(map(str, signposts[2:])))


if __name__ == "__main__":
    main()

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

def main():
  N, M = map(int, readline().split())
  dist = {}
  pre = {}
  A = {}
  for i in range(N):
    dist[i+1] = -1
    pre[i+1] = -1
    A[i+1] = []
  dist[1] = 0
  pre[1] = 0
  for i in range(M):
    ai, bi = map(int, readline().split())
    A[ai].append(bi)
    A[bi].append(ai)
  cnt = 1
  depth = 1
  D = [1]
  while cnt < N:
    next = []
    for i in range(len(D)):
      for j in range(len(A[D[i]])):
        if dist[A[D[i]][j]] == -1:
          dist[A[D[i]][j]] = depth
          pre[A[D[i]][j]] = D[i]
          next.append(A[D[i]][j])
          cnt += 1
    D = next
    depth += 1
    if len(next) == 0:
      break
    elif depth > N:
      break
  if cnt == N:
    print('Yes')
    for i in range(1, N):
      print(pre[i+1])
  else:
    print('No')

if __name__ == '__main__':
  main()

Solution (Python):

from collections import defaultdict
CH = defaultdict(list)

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

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



def bfs(s):
    d = [-1] * N
    d_pre = [0] * N
    d[s-1] = 0
    p_old = [s]
    cnt = 1
    
    while p_old:
      p_new = []
      for i in p_old:
        for j in P[i-1]:
          if d[j-1] == -1:
            d[j-1] = cnt
            d_pre[j-1] = i
            p_new.append(j)
      p_old = p_new
      cnt += 1
      
    return d_pre

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

Solution (Python):
from collections import deque

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

room_q = deque()
room_q.append(1)
michihsirube_room = [-1 for _ in range(N + 1)]
while room_q:
    node = room_q.popleft()
    for near_room_id in relation_list[node]:
        if michihsirube_room[near_room_id] == -1:
            michihsirube_room[near_room_id] = node
            room_q.append(near_room_id)
print('Yes')
for i in range(2, N + 1):
    print(michihsirube_room[i])

Solution (Python):
n,m = map(int,input().split())
g = [[] for _ in range(n)] 
 
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
from collections import deque
 
def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    l = [[] for _ in range(n)] 
    dic = {}
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                l[i].append(v)
                dic[i] = v
    return d,l,dic
d,l,dic = bfs(0)
if None in d:
    print("No")
else:
    print("Yes")
    l.remove(l[0])
    [print(i[0]+1) for i in l]

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10 ** 9)
inf = float("inf")
readline = sys.stdin.buffer.readline
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
nt = lambda: tuple(map(int, readline().split()))


def main():
    N, M = nm()
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = nm()
        a, b = a-1, b-1
        edges[a].append(b)
        edges[b].append(a)

    ans = [-1] * N
    deq = deque([0])
    while deq:
        node = deq.popleft()
        for next_node in edges[node]:
            
            if ans[next_node] == -1:
                ans[next_node] = node
                deq.append(next_node)
    print("Yes")
    [print(i+1) for i in ans[1:]]

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

is_reachable = True

d = deque()
is_visited = [False] * N
rooms = [-1] * N
distance = [0] * N

d.append(0)
is_visited[0] = 1

while (d):
    v = d.popleft()

    for u in adj[v]:
        if is_visited[u]:
            continue

        is_visited[u] = 1
        rooms[u] = v+1
        distance[u] = distance[v] + 1
        d.append(u)

for i in range(1, N):
    d1 = distance[i]
    sign1 = rooms[i]-1
    if d1 <= distance[sign1]:
        is_reachable = False

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

Solution (Python):
from collections import deque

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

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

while len(q):
    node = q.popleft()

    for i in range(len(e[node])):
        nex = e[node][i]
        if t[nex] == -1:
            q.append(nex)
            t[nex] = node
print("Yes")
for i in range(2,n+1):
    print(t[i])

Solution (Python):
def resolve():
    N, M = [int(i) for i in input().split()]
    path = [[] for _ in range(N)]
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        path[A - 1].append(B - 1)
        path[B - 1].append(A - 1)
    visited = [-1] * N
    que = [0]
    visited[0] = 0

    while que:
        v = que.pop(0)
        for nv in path[v]:
            if visited[nv] != -1:
                continue
            visited[nv] = v + 1
            que.append(nv)

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


resolve()

Solution (Python):
from collections import deque

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

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

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

todo=deque([[0,0]])
seen=[-1]*n
seen[0]=0

while todo:
    node,parent=todo.popleft()
    
    for to in edges[node]:
        if seen[to]!=-1:
            continue

        todo.append([to,node])
        seen[to]=node

print('Yes')

for parent in seen[1:]:
    print(parent+1)

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




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



Ans = [-1]*N;
visited = [False]*N;
Queue = deque([0])


while(Queue):
    t = Queue.popleft()
    for v in edge[t]:
        if visited[v]:
            continue
        Queue.append(v)
        Ans[v]=t
        visited[v]=True
    


for i in range(1,N):
    if Ans[i]==-1:
        print("No")
        sys.exit()
    

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

Solution (Python):
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)




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




def bfs(s,n,node):
    
    check=[False for _ in range(n)]
    check[s]=True

    
    queue=deque([s])

    visited_num=1

    
    ans=[-1 for _ in range(n)]
    ans[0]=0
    while visited_num<n:
        
        if len(queue)==0:
            
            
            return []

        now_vertex=queue.popleft()
        
        
        for each_node_arr in node[now_vertex]:
            
            next_vertex=each_node_arr[0]
            next_ind=each_node_arr[1]

            if check[next_vertex]==True:
                continue
            queue.append(next_vertex)
            check[next_vertex]=True

            
            ans[next_vertex]=now_vertex+1
            visited_num+=1

    return ans



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



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

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

Solution (Python):
n,m=[int(j)for j in input().split()]
l=[[]for i in range(n+1)]
for i in range(m):
    a,b=[int(j)for j in input().split()]
    l[a].append(b)
    l[b].append(a)
ans=[0]*(n+1)
from collections import deque
q=deque([1])
s=set([1])
while q:
    i=q.popleft()
    for k in l[i]:
        if k not in s:
            ans[k]=i
            q.append(k)
            s.add(k)

if 0 not in ans[2:]:
    print("Yes")
    print('\n'.join(map(str,ans[2:])))
else:
    print("No")

Solution (Python):

from collections import deque
inf = float("INF")

N,M = map(int,input().split())
path = [[] for i in range(N)]
dist = [inf for i in range(N)]
visited = [0 for i in range(N)]

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

def bfs(path,root,visited):
    
    dist[root] = 0
    
    visited[root] = 1
    
    queue = deque([root])
    
    while queue:
        
        current = queue.popleft()
        for i in path[current]:
            
            if visited[i] == 1:
                continue
            else:
                
                dist[i] = current + 1
                visited[i] = 1
                queue.append(i)

    if all([i == 1 for i in visited]):
        return "Yes"
    else:
        return "No"

flag = bfs(path,0,visited)
print(flag)

if flag == "Yes":
    for i in range(1,N):
        print(dist[i])

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

from collections import deque

node = 0
q = deque([0])

check = [0]*N
check[0] = 1
while len(q) > 0:
  node = q.popleft()
  for i in AB[node]:
    if check[i] == 0:
      q.append(i)
      check[i] = 1
      ans[i] = node
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

Solution (Python):
n,m=[int(j)for j in input().split()]
l=[[]for i in range(n+1)]
for i in range(m):
    a,b=[int(j)for j in input().split()]
    l[a].append(b)
    l[b].append(a)
ans=[0]*(n+1)
from collections import deque
q=deque([1])
s=set([1])
while q:
    i=q.popleft()
    for k in l[i]:
        if k not in s:
            ans[k]=i
            q.append(k)
            s.add(k)

if 0 not in ans[2:]:
    print("Yes")
    print('\n'.join(map(str,ans[2:])))
else:
    print("No")