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())
 
graph=[[]for _ in range(N+1)]
 
for _ in range(M):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)
 
dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
 
D=deque()
D.append(1)
 
while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)
 
print('Yes')
for j in dist[2:]:
    print(j)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
tuna = [[] for i in range(n+1)]
ans = [0 for i in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    tuna[a].append(b)
    tuna[b].append(a)
q = deque()
q.append(1)
while q:
    now = q.popleft()
    saki = tuna[now]
    for i in saki:
        if ans[i] == 0:
            q.append(i)
            ans[i] = now
print("Yes")
for i in range(2,n+1):
    print(ans[i])

Solution (Python):
from heapq import heappush, heappop

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

INF = 10 ** 9
dist = [INF] * n
prev = [-1] * n
def dijkstra(s):
    q = [(0, s)]
    dist[s] = 0
    while q:
        v = heappop(q)[1]
        for cost, to in edges[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                prev[to] = v
                heappush(q, (dist[to], to))

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

Solution (Python):
from collections import deque

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

def bfs(v):
    q = deque()
    prev[v] = -99999
    q.append(v)
    while q:
        v = q.popleft()
        for u in edges[v]:
            if prev[u] == -1:
                prev[u] = v
                q.append(u)

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

Solution (Python):
def resolve():
    N, M = [int(i) for i in input().split()]
    AB = [[] for _ in range(N + 1)]
    AB[0] = [1]
    for _ in range(M):
        A, B = [int(i) for i in input().split()]
        AB[A].append(B)
        AB[B].append(A)
    from collections import deque
    dq = deque([1])
    ans = [-1] * (N + 1)
    while len(dq) > 0:
        p = dq.popleft()
        c = AB[p]
        for cc in c:
            if ans[cc] == -1:
                ans[cc] = p
                dq.append(cc)
    if -1 in ans[2:]:
        print("No")
        print(ans, file=sys.stderr)
    else:
        print("Yes")
        for a in ans[2:]:
            print(a)


resolve()

Solution (Python):
from collections import deque

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

def bfs(v):
    q = deque()
    prev[v] = -99999
    q.append(v)
    while q:
        v = q.popleft()
        for u in edges[v]:
            if prev[u] == -1:
                prev[u] = v
                q.append(u)

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

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

s=[-1]*N
d=[-1]*N
next=[[] for _ in range(N)]
next[0].append(0)

s[0]=0
d[0]=0


for i in range(N):
  finish=1
  for j in next[i]:
    if d[j]==i:
      for saki in graph[j]:
        if d[saki]==-1:
          d[saki]=i+1
          s[saki]=j
          next[i+1].append(saki)
          finish=0
  if finish==1:
    break

print("Yes")
for i in range(N-1):
  print(s[i+1]+1)

Solution (Python):
from collections import deque

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

def bfs(v):
    q = deque()
    visited[v] = True
    q.append(v)
    while q:
        v = q.popleft()
        for child in edges[v]:
            if not visited[child]:
                visited[child] = True
                prev[child] = v
                q.append(child)

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

Solution (Python):
from collections import deque

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

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

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

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if paths[i] == -1:
            paths[i] = rnum
            q.append(i)
print("Yes")
for i in paths[2:]:
    print(i)

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

import collections

seen = [-1]*(n+1)
todo = collections.deque()

for i in info[1]:
    todo.append(i)
    seen[i] = 1

while len(todo) != 0:
    now = todo.popleft()
    for i in info[now]:
        if seen[i] == -1:
            todo.append(i)
            seen[i] = now

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

Solution (Python):
'''
参考
https://www.charter-blog.com/entry/2020/05/18/163000
https://atcoder.jp/contests/abc168/submissions/13442966
BFS（幅優先探索について）
https://qiita.com/drken/items/996d80bcae64649a6580
'''
import collections

N, M = map(int, input().split())
'''
グラフ入力を受け取るためのリストを準備（部屋数分のリスト要素）
（2次元配列の初期化方法に注意）
https://note.nkmk.me/python-list-initialize/
'''
graph = [[] for _ in range(N+1)]    

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

q = collections.deque([1])          
dest = [-1] * (N+1)                 
dest[0] = 1                         
dest[1] = 1                         

while q:
    room = q.popleft()              
    for n_room in graph[room]:      
        if dest[n_room] == -1:
            dest[n_room] = room     
            q.append(n_room)        

if -1 in dest:
    print('No')
else:
    print('Yes')
    print('\n'.join(map(str, dest[2:])))

Solution (Python):
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        

    queue = deque([1])
    d = [None] * (N + 1)
    d[0] = 0
    d[1] = 0

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

    if None in d:
        print("No")
    else:
        print("Yes")
        print("\n".join(map(str, d[2:])))


if __name__ == '__main__':
	main()

exit()

Solution (Python):
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

    queue = deque([1])
    d = [None] * (N + 1)
    d[0] = 0
    d[1] = 0

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

    if None in d:
        print("No")
    else:
        print("Yes")
        print("\n".join(map(str, d[2:])))


if __name__ == '__main__':
	main()

exit()

Solution (Python):
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

    queue = deque([1])
    d = [0] * (N + 1)
    d[0] = 1
    d[1] = 1

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

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


if __name__ == '__main__':
	main()

exit()

Solution (Python):
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

    queue = deque([1])
    d = [0] * (N + 1)
    d[0] = 1
    d[1] = 1

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

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


if __name__ == '__main__':
	main()

exit()

Solution (Python):

from collections import deque


def main():
    
    N, M, *AB = map(int, open(0).read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        

    queue = deque([1])
    d = [0] * (N + 1)
    d[0] = 1
    d[1] = 1

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

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


if __name__ == '__main__':
	main()

exit()

Solution (Python):
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        

    queue = deque([1])
    d = [0] * (N + 1)
    d[0] = 1
    d[1] = 1

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

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


if __name__ == '__main__':
	main()

exit()

Solution (Python):
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        

    queue = deque([1])
    d = [-1] * (N + 1)
    d[0] = 0
    d[1] = 0

    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] == -1:
                
                d[i] = v
                queue.append(i)

    if -1 in d:
        print("No")
    else:
        print("Yes")
        print("\n".join(map(str, d[2:])))


if __name__ == '__main__':
	main()

exit()

Solution (Python):
import sys
from collections import deque


def main():
    N, M, *AB = map(int, sys.stdin.buffer.read().split())
    
    g = [[] for _ in range(N + 1)]

    for A, B in zip(*[iter(AB)] * 2):
        g[A].append(B)
        g[B].append(A)

        

    queue = deque([1])
    d = [None] * (N + 1)
    d[0] = 0
    d[1] = 0

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

    if None in d:
        print("No")
    else:
        print("Yes")
        print("\n".join(map(str, d[2:])))


if __name__ == '__main__':
	main()

exit()

Solution (Python):
from collections import deque

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

links=[[] for _ in range(N+1)]
for a,b in AB:
  links[a].append(b)
  links[b].append(a)
  
result=[-1]*(N+1)
q=deque([1])
while q:
  i=q.popleft()
  for j in links[i]:
    if result[j]==-1:
      result[j]=i
      q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

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


dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
 
D=deque()
D.append(1)

while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)

print('Yes')
for j in dist[2:]:
    print(j)

Solution (Python):
n, m = map(int, input().split())
way_list = [ [] for _ in range(n)]
ans = [0] * n

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

marked = {0}
que = [0]
for q in que:
    for i in way_list[q]:
        if i in marked:
            continue
        que.append(i)
        marked.add(i)
        ans[i] = q+1
        
if ans.count(0) > 1:
    print("No")
else:
    print("Yes")
    for i in ans[1:]:
        print(i)

Solution (Python):
from collections import deque
 
N,M=map(int,input().split())
 
graph=[[]for _ in range(N+1)]
 
for _ in range(M):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)
 
dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
 
D=deque()
D.append(1)
 
while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)
 
print('Yes')
for j in dist[2:]:
    print(j)

Solution (Python):
from collections import deque
from sys import maxsize
from copy import deepcopy


class Graph:
    def __init__(self, No_of_nodes):
        self.n = No_of_nodes
        self.adj = [[] for i in range(self.n)]

    def addEdge(self, a, b, w):
        self.adj[a].append([b, w])

    def BFS(self, start):
        visited = [False] * self.n
        depth = [0 for i in range(self.n)]
        que = deque()
        q = [start]
        que.append(start)
        visited[start] = True
        ans = ''
        f = 0
        while que:
            s = que.popleft()
            ans += str(s) + ' '
            for i in self.adj[s]:
                if not visited[i[0]]:
                    depth[i[0]] = s
                    que.append(i[0])
                    visited[i[0]] = True
        return depth

    def dijkstra(self, start):
        nxtpoint = [None for i in range(self.n)]
        distance = [maxsize for i in range(self.n)]
        distance[start] = 0
        q = deque()
        q.append(start)
        while len(q) != 0:
            a = q.pop()
            for u in self.adj[a]:
                b, w = u
                if distance[a] + w < distance[b]:
                    distance[b] = distance[a] + w
                    nxtpoint[b] = a
                    q.append(b)
        return nxtpoint


n, m = map(int, input().split())
ls = []
g = Graph(n)
ans = 'Yes\n'
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g.addEdge(a, b, 1)
    g.addEdge(b, a, 1)
point = g.BFS(0)
for i in range(1, n):
    if point[i] is None:
        ans = 'No'
        break
    else:
        ans += str(point[i] + 1) + '\n'
print(ans)

Solution (Python):
from collections import deque

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

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

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

dist=[-1]*(N+1)
dist[0]=0
dist[1]=0

D=deque()
D.append(1)

while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)

print('Yes')
for j in dist[2:]:
    print(j)

Solution (Python):
(n,m),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*-~n)
for a,b in t:e[a]+=b,;e[b]+=a,
q=[1]
d=[0]*-~n
for v in q:
 for w in e[v]:
  if d[w]<1:d[w]=v;q+=w,
print('Yes',*d[2:])

Solution (Python):
(n,m),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*-~n)
for a,b in t:e[a]+=b,;e[b]+=a,
q=[1]
d=[0]*-~n
for v in q:
 for w in e[v]:
  if d[w]<1:d[w]=v;q+=w,
print('Yes',*d[2:])

Solution (Python):

from collections import deque

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

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

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Solution (Python):
_input = input
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)


import queue


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

t=[[] for i in range(n+1)]


for route in s:
	t[route[0]].append(route[1])
	t[route[1]].append(route[0])


saitan = [n+10 for i in range(n+1)]
shirube=[[] for i in range(n+1)]
itta=[0 for i in range(n+1)]


q = queue.Queue()
q.put(1)
saitan[1]=0
while not q.empty():
	i=q.get()
	for j in t[i]:
		itta[j]=1
		if saitan[i]+1 < saitan[j]:
			saitan[j] = saitan[i]+1
			q.put(j)
			shirube[j] = i

if sum(itta) == n:
	print("Yes")
	for i in shirube[2:n+1]:
		print(i)
else:
	print("No")
	
input = _input

Solution (Python):
(n,m),*t=[map(int,t.split())for t in open(0)]
e=[[]for _ in range(n+1)]
for a,b in t:
  e[a]+=b,
  e[b]+=a,
q=[1]
d=[0]*-~n
for v in q:
  for w in e[v]:
    if d[w]<1:
      d[w]=v
      q+=w,
print('Yes',*d[2:])

Solution (Python):
from collections import deque

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

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

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

Solution (Python):
N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
prev = [0] * N
to_list = [ [] for _ in range(N)]

for a,b in AB:
  to_list[a - 1].append(b - 1)
  to_list[b - 1].append(a - 1)

marked = {0}
que = [0]

for i in que:
    for j in to_list[i]:
        if j in marked: continue
        que.append(j)
        marked.add(j)
        prev[j] = i+1

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

Solution (Python):
import sys
from collections import deque

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N, M = LI()
G = [[] for _ in range(N+1)] 

for _ in range(M):
    a, b = LI()
    G[a].append(b)
    G[b].append(a)

par = [None] * (N + 1)

def bfs(u):
    queue = deque([u])
    d = [None] * (N+1)
    
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in G[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                par[i] = v
                queue.append(i)
    return d

d = bfs(1)
print('Yes')
print(*par[2:], sep='\n')

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

G = [[] for _ in range(N + 1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)

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

Solution (Python):
it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
while d:
    l = d.pop(0)
    for k in p[l-1]:
        if con[k-2]==0:
            d.append(k)
            con[k-2] = l
print('Yes')
for i in range(n-1):
    print(con[i])

Solution (Python):
import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

dist = [-1] * (N + 1)
que = collections.deque()
 
dist[1] = 0
que.append(1)
 
while len(que):
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = v
        que.append(nv)
if -1 in dist[2:]:
    print('No')
else:
    print('Yes')
    for value in dist[2:]:
        print(value)

Solution (Python):
n, m = map(int, input().split())
d_net = {}  
d_path = {}  

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

    if b in d_net:
        d_net[b].append(a)
    else:
        d_net[b] = [a]

start_list = d_net[1]
tmp_list = []
for no in start_list:
    d_path[no] = 1
    tmp_list.append(no)

while True:
    next_list = []
    for no in tmp_list:
        for next_no in d_net[no]:
            if next_no not in d_path:
                d_path[next_no] = no
                next_list.append(next_no)
    tmp_list = next_list
    if(tmp_list == []):
        break
print("Yes", end="\n")
for i in range(2, n+1):
    print(d_path[i], end="\n")

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
C = [list(map(int, input().split())) for i in range(M)]

def bfs(now):
    plan = deque([])
    plan.append(now)
    visited[now][0] = True
    while plan:
        now = plan.popleft()
        for i in PATH[now]:
            if visited[i][0] == True:
                continue
            else:
                plan.append(i)
                visited[i][0] = True
                visited[i][1] = now

if __name__ == '__main__':
    PATH = [deque([]) for i in range(N+1)]
    
    for i in range(M):
        PATH[C[i][0]].append(C[i][1])
        PATH[C[i][1]].append(C[i][0])
    visited = [[False,0] for i in range(N+1)]
    bfs(1)
    print("Yes")
    for i in range(2,N+1):
        print(visited[i][1])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
C = [list(map(int, input().split())) for i in range(M)]

def bfs(room, now):
    
    plan = deque([])
    
    
    plan.append(now)
    
    visited[1][0] = True
    while plan:
        now = plan.popleft()
        
        for i in PATH[now]:
            if visited[i][0] == True:
                
                continue
            else:
                
                
                plan.append(i)
                
                visited[i][0] = True
                visited[i][1] = now

if __name__ == '__main__':
    PATH = [deque([]) for i in range(N+1)]
    
    for i in range(M):
        PATH[C[i][0]].append(C[i][1])
        PATH[C[i][1]].append(C[i][0])
    
    visited = [[False,0] for i in range(N+1)]
    bfs(PATH[1], 1)
    
    print("Yes")
    for i in range(2,N+1):
        print(visited[i][1])

Solution (Python):

def main():
    import sys
    
    N, M =map(int, sys.stdin.readline().split())
    AB = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    
    edge = [[] for _ in range(N)]
    for ab in AB:
        edge[ab[0]-1] += [ab[1]-1]
        edge[ab[1]-1] += [ab[0]-1]
    
    
    
    L = [-1 for i in range(N)] 
    
    
    def bfs(p):
        from collections import deque
        queue = deque([p])
        L[p] =0
        while queue:
            p = queue.popleft()
            for c in edge[p]:
                if L[c]==-1: 
                    
                    L[c] = p+1 
                    
                    queue.append(c)
        
    
    bfs(0)
    print('Yes')
    for i in L[1:]:
        print(i)


if __name__=='__main__':
    main()

Solution (Python):

from collections import deque
import sys
input = sys.stdin.readline
N,M = (int(x) for x in input().split())
connection ={i:set() for i in range(1,N+1)}


for i in range(1,M+1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b)
    connection[b].add(a)


dq =deque()
dq.append(1)
parent ={i:-1 for i in range(1,N+1)} 
parent[1] =0
while dq:
    now =dq.popleft()
    for next in connection[now]:
        if parent[next] !=-1:
            continue
        else:
            parent[next] =now
            dq.append(next)
if -1 not in parent.values():
    del parent[1]
    print("Yes")
    print(*parent.values(),sep="\n")

Solution (Python):
from collections import deque

def m():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    dp = [10 ** 9] * (N + 1)
    visited = [False] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)


    def bfs(root):
        visited[root] = True
        dp[root] = 0
        queue = deque([])
        for q in g[root]:
            dp[q] = root
            queue.append(q)
            visited[q] = True
        while queue:
            q = queue.popleft()
            for k in g[q]:
                if not visited[k]:
                    queue.append(k)
                    dp[k] = q
                    visited[k] = True
    bfs(1)

    if not all(visited[2:]):
        print('No')
        return

    print('Yes')
    for j in dp[2:]:
        print(j)
    return

m()

Solution (Python):

def m():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    dp = [10 ** 9] * (N + 1)
    visited = [False] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)


    def bfs(root):
        visited[root] = True
        dp[root] = 0
        queue = []
        for q in g[root]:
            dp[q] = root
            queue.append(q)
            visited[q] = True
        while queue:
            q = queue.pop(0)
            for k in g[q]:
                if not visited[k]:
                    queue.append(k)
                    dp[k] = q
                    visited[k] = True
    bfs(1)

    if not all(visited[2:]):
        print('No')
        return

    print('Yes')
    for j in dp[2:]:
        print(j)
    return

m()

Solution (Python):

from collections import deque

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

next_v = deque([0])
INF = 10**18

dist = [INF]*n
dist[0] = 0

prev = [-1]*n
while next_v:
    v1 = next_v.popleft()
    for v2 in edges[v1]:
        if dist[v2] != INF:
            continue
        dist[v2] = dist[v1] + 1
        prev[v2] = v1
        next_v.append(v2)

if min(prev[1:]) == -1:
    print('No')
else:
    print('Yes')
    ans = [x+1 for x in prev[1:]]
    print(*ans, sep='\n')

Solution (Python):
from collections import deque
n, m = map(int, input().split())
d = deque()
shirube = [0 for _ in range(n+1)]
road = [[] for _ in range(n+1)]
for i in range(m):
    r1, r2 = map(int, input().split())
    road[r1].append(r2)
    road[r2].append(r1)
for node in road[1]:
    d.append(node)
    shirube[node] = 1
while len(d) != 0:
    node = d.popleft()
    for next_node in road[node]:
        if shirube[next_node] == 0:
                d.append(next_node)
                shirube[next_node] = node 
print('Yes')
shirube_ans = shirube[2:n+1]
for s in shirube_ans:
    print(s)

Solution (Python):

from collections import defaultdict, deque
import sys

YES = "Yes"  


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    edges = defaultdict(list)
    for i in range(M):
        edges[A[i] - 1].append(B[i] - 1)
        edges[B[i] - 1].append(A[i] - 1)
    queue = deque()
    queue.append(0)
    before_node = [None] * N
    while queue:
        node = queue.popleft()
        for next_node in edges[node]:
            if before_node[next_node] is None:
                queue.append(next_node)
                before_node[next_node] = node + 1
    print("Yes")
    print("\n".join(map(str, before_node[1:])))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)

next_v = deque([0])
prev = [-1]*n
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if prev[v2] != -1:
            continue
        prev[v2] = v+1
        next_v.append(v2)

print('Yes')
for x in prev[1:]:
    print(x)