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

Solution (Python):
import copy
import queue
q = queue.Queue()
N, M = map(int, input().split())
nodes = [[] for i in range(N)]
idxStock = []
for i in range(M):
    a, b = map(int, input().split())
    nodes[a - 1].append(b - 1)
    nodes[b - 1].append(a - 1)

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

q.put(0)
while not q.empty():
    now = q.get()
    for i in nodes[now]:
        if dist[i] != -1:
            continue
        dist[i] = dist[now] + 1
        q.put(i)
        ans[i] = now
print("Yes")
for i in range(1, N):
    print(ans[i]+1)

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

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

from collections import deque
arrow = [0]*n
def bfs(u, n):
    queue = deque([u]) 
    d = [False]*n
    d[u] = 1
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i]:continue
            d[i] = True
            arrow[i] = v
            queue.append(i)
    return arrow

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

Solution (Python):
from collections import deque
n, m = map(int, input().split(' '))
c = [[] for i in range(n)]
r = [0] * n
q = deque()
for i in range(m):
    a, b = map(int, input().split(' '))
    c[a - 1].append(b - 1)
    c[b - 1].append(a - 1)
q.append(0)
while len(q) > 0:
    ix = q.popleft()
    for i in c[ix]:
        if r[i] == 0:
            r[i] = ix + 1
            q.append(i)

jg = 'Yes' if r.pop(0) > 0 else 'No'
print(jg)
for i in r:
    print(i)

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


visited=[0]*(n+1)
que=deque()
que.append(1)
while que:
  node=que.popleft()
  for i in adjacent_list[node]:
    if visited[i]==0:
      visited[i]=node
      que.append(i)
      
print('Yes')
for i in range(2,n+1):
  print(visited[i])

Solution (Python):
import heapq

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

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


gw = [0]*(N+1)
gw[1] = 1
ng=1
hq = []
heapq.heapify(hq) 
heapq.heappush(hq,(0,1))
while hq:
  c, n = heapq.heappop(hq)
  for i in node[n]:
    if gw[i] == 0:
      gw[i] = n
      ng += 1
      heapq.heappush(hq,(c+1,i))

if ng < N:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(gw[i])

Solution (Python):
from collections import deque
n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
que = deque()
que.append(1)
rote = [0]*(n+1)
rote[1] = -1
while que:
    now = que.popleft()
    nx = g[now]
    for next_room in nx:
        if  rote[next_room] == 0:
            rote[next_room] = now
            que.append(next_room)

flag = True
for i in range(2,n+1):
    if rote[i] == 0:
        flag = False
if flag:
    print("Yes")
    for j in range(2,n+1):
        print(rote[j])
    exit()
else:
    print("No")

Solution (Python):
from collections import deque

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

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

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

queue = deque([0])
d = [None]*n
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] == None:
            d[i] = v + 1
            queue.append(i)
            
if all(type(i) is int for i in d):
    print('Yes')
    for i in d[1:]:
        print(i)
else:
    print('No')

Solution (Python):

from collections import deque

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

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

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

queue = deque([0])
d = [None]*n
d[0] = 0
while queue:
    v = queue.popleft()
    for i in g[v]:
        if d[i] == None:
            d[i] = v + 1
            queue.append(i)
            
if all(type(i) is int for i in d):
    print('Yes')
    for i in d[1:]:
        print(i)
else:
    print('No')

Solution (Python):
from collections import deque


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

q = deque([0])
dist = [1000000000] * n
pre = [-1] * n
dist[0] = 0 
q.append(0)
while q:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != 1000000000:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        q.append(i)
print("Yes")
for i in range(n):
    if i == 0:
        continue
    ans = pre[i]
    ans += 1
    print(ans)

Solution (Python):
from collections import deque

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

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

for i in range(m):
    a,b = map(int, input().split())
    path[a-1].append(b)
    path[b-1].append(a)
    
d = deque([0])
dis = [-1 for _ in range(n)]
dis[0] = 0

while d:
    hop = d.popleft()
    for i in path[hop]:
        if dis[i-1] == -1:
            d.append(i-1)
            dis[i-1] = hop+1
            
if -1 in dis:
    print('No')
else:
    print('Yes')
    for i in range(1,len(dis)):
        print(dis[i])

Solution (Python):
N, M = map(int, input().split())
node =[[] for _ in range(N)]

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

ct = [-1]*N

i = 0
stack = []
ct[0] = 0
stack.append(0)
while len(stack) != 0:
  v = stack.pop(0)
  for e in node[v]:
    if ct[e] == -1:
      ct[e] = v
      stack.append(e)

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
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)

ans = [-1]*(n+1)
que = deque([1])
while que:
    q = que.popleft()
    for i in ab[q]:
        if ans[i] == -1:
            que.append(i)
            ans[i] = q
print('Yes')
for i in range(2, n+1):
    print(ans[i])

Solution (Python):
N, M = map(int, input().split())
node =[[] for _ in range(N)]

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

ct = [-1]*N

i = 0
queue = []
ct[0] = 0
queue.append(0)
while len(queue) != 0:
  v = queue.pop(0)
  for e in node[v]:
    if ct[e] == -1:
      ct[e] = v
      queue.append(e)

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

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

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

for _ in range(m):
    u,v = [int(x) for x in input().split()]
    g[u].append(v)
    g[v].append(u)


vis = [0]*(n+1)

d = deque()
for x in g[1]:
    vis[x] = 1
    d.append(x)


while d:
    cur = d.popleft()

    for x in g[cur]:
        if vis[x] == 0:
            vis[x] = cur
            d.append(x)


vis[0],vis[1] = 1,1

if all(vis):
    print("Yes")
    for i in range(2,n+1):
        print(vis[i])
else:
    print('No')

Solution (Python):
from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [None] * (N+1)
    signpost[0] = signpost[1] = 0
    q = deque([1])
    dist = [0 for i in range(N+1)]
    while q:
        node = q.popleft()
        for e in edge[node]:
            if signpost[e] is None:
                dist[e] = dist[node] + 1
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

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)

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

N,M,*AB=map(int,open(0).read().split())
to=[[] for _ in range(N)]

for a,b in zip(*[iter(AB)]*2):
  to[a-1].append(b-1)
  to[b-1].append(a-1)
  
q=deque([0])
r=[None]*N

while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print("Yes",*r[1:],sep="\n")

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)
    q=deque([1])
    s=[0]*(N+1)
    s[1]=1
    while q:
        u=q.popleft()
        for v in g[u]:
            if not s[v]:
                s[v] = u
                q.append(v)
    print("Yes")
    print("\n".join(map(str, s[2:])))
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N+1)]
	for a,b in zip(*[iter(AB)]*2):
		to[a].append(b)
		to[b].append(a)
	q=deque([1])
	r=[None]*(N+1)
	while q:
		x=q.popleft()
		for i in to[x]:
			if r[i] is None:
				q.append(i)
				r[i]=x
	print("Yes",*r[2:],sep="\n")
if __name__=='__main__':
	main()

Solution (Python):
from collections import deque
N,M,*AB=map(int,open(0).read().split())
to=[[] for _ in range(N+1)]
for a,b in zip(*[iter(AB)]*2):
  to[a].append(b)
  to[b].append(a)
q=deque([1])
r=[None]*(N+1)
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x
print("Yes",*r[2:],sep="\n")

Solution (Python):
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N)]
	for a,b in zip(*[iter(AB)]*2):
		to[a-1].append(b-1)
		to[b-1].append(a-1)
	q=deque([0])
	r=[0]*N
	while q:
		x=q.popleft()
		for i in to[x]:
			if not r[i]:
				q.append(i)
				r[i]=x+1
	print("Yes",*r[1:],sep="\n")
if __name__=='__main__':
	main()

Solution (Python):
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N)]
	for a,b in zip(*[iter(AB)]*2):
		to[a-1].append(b-1)
		to[b-1].append(a-1)
	q=deque([0])
	r=[None]*N
	while q:
		x=q.popleft()
		for i in to[x]:
			if not r[i]:
				q.append(i)
				r[i]=x+1
	print("Yes",*r[1:],sep="\n")
if __name__=='__main__':
	main()

Solution (Python):
from collections import deque
def main():
	N,M,*AB=map(int,open(0).read().split())
	to=[[] for _ in range(N)]
	for a,b in zip(*[iter(AB)]*2):
		to[a-1].append(b-1)
		to[b-1].append(a-1)
	q=deque([0])
	r=[None]*N
	while q:
		x=q.popleft()
		for i in to[x]:
			if r[i] is None:
				q.append(i)
				r[i]=x+1
	print("Yes",*r[1:],sep="\n")
if __name__=='__main__':
	main()

Solution (Python):
n,m=[int(x) for x in input().rstrip().split()]
l=[[] for x in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True:
        continue
      ans[i]=now+1
      done[i]=True
      stack.append(i)

bfs()
print("Yes")
print(*ans[1:])

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    rooms = list([] for _ in range(n))

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

        rooms[a-1].append(b-1)
        rooms[b-1].append(a-1)
    
    q = deque()
    q.append(0)

    dist = [False for _ in range(n)]
    dist[0] = 0

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

        for nextRoom in rooms[now]:
            if dist[nextRoom] != False:
                continue
            else:
                dist[nextRoom] = now + 1
                q.append(nextRoom)
    
    if False not in dist:
        dist[0] = 'Yes'

        for i in range(len(dist)):
            if i == 0:
                print(dist[i])
            else:
                print(dist[i])
    else:
        print('No')

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import math
import collections
import fractions
import itertools

def solve():
    n, m = map(int, input().split())
    cave = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n)]
    for i in cave:
        g[i[0]-1].append(i[1])
        g[i[1]-1].append(i[0])
    que = collections.deque()
    ans = [-1]*n
    que.append(1)
    ans[0] = 0
    while(len(que)!=0):
        state = que.popleft()
        for i in g[state-1]:
            if ans[i-1] == -1:
                ans[i-1] = state
                que.append(i)
    if -1 in ans:
        print("No")
    else:
        print("Yes")
        for i in range(1,n):
            print(ans[i])
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited
 
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda n: int(n) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = bfs(graph, N, 0)[1:]
if all(visited):
    print("Yes")
    print(*visited, sep="\n")
else:
    print("No")

Solution (Python):
from collections import deque
N,M,*AB=map(int,open(0).read().split())
to=[[] for _ in range(N)]
for a,b in zip(*[iter(AB)]*2):
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Solution (Python):
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print('Yes')
print('\n'.join(map(str,r[1:])))

Solution (Python):
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Solution (Python):
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[-1]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i]==-1:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Solution (Python):
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
q=deque([0])
r=[None]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
print("Yes",*r[1:],sep="\n")

Solution (Python):
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)

q=deque([0])
r=[None]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print('Yes')
for i in range(N):
  if r[i]!=0:
    print(r[i])

Solution (Python):
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)

q=deque([0])
r=deque([None]*N)
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print('Yes')
r.popleft()
for i in range(N-1):
  print(r.popleft())

Solution (Python):
from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)

q=deque([0])
r=[None]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print('Yes')
for i in range(N):
  if r[i]!=0:
    print(r[i])

Solution (Python):
from collections import deque
import sys


INF = float('inf')


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


class Graph:
    def __init__(self, n, is_directed=False):
        self.graph = [[] for _ in range(n)]
        self.is_directed = is_directed

    def add_edge(self, u, v):
        """頂点uから頂点vに辺を作る
        無向グラフの場合、uからvの方向の辺のみを記録する
        """
        self.graph[u].append(v)
        if not self.is_directed:
            self.graph[v].append(u)

    def bfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [INF] * len(self.graph)
        queue = deque([start])
        distances[start] = 0
        ans = [0] * len(self.graph)

        while queue:
            now = queue.popleft()
            for to in self.graph[now]:
                if distances[to] != INF:
                    continue
                queue.append(to)
                
                ans[to] = now
                distances[to] = distances[now] + 1
        return distances, ans


def main():
    n, m = LI()
    g = Graph(n)
    for _ in range(m):
        a, b = LI()
        a, b = a - 1, b - 1
        g.add_edge(a, b)

    bfs_res, ans = g.bfs(0)
    for d in bfs_res:
        if d == INF:
            print('No')
            return

    print('Yes')
    print(*map(lambda x: x + 1, ans[1:]), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys


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


INF = float('inf')


class Graph:
    def __init__(self, n, is_directed=False):
        self.graph = [[] for _ in range(n)]
        self.is_directed = is_directed

    def add_edge(self, u, v):
        """頂点uから頂点vに辺を作る
        無向グラフの場合、uからvの方向の辺のみを記録する
        """
        self.graph[u].append(v)
        if not self.is_directed:
            self.graph[v].append(u)

    def bfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [INF] * len(self.graph)
        queue = deque([start])
        distances[start] = 0
        ans = [0] * len(self.graph)

        while queue:
            now = queue.popleft()
            for to in self.graph[now]:
                if distances[to] != INF:
                    continue
                queue.append(to)
                ans[to] = now
                distances[to] = distances[now] + 1
        return distances, ans

    def dfs(self, start):
        """幅優先探索を行い始点から各頂点までの距離の配列を返す
        """
        distances = [INF] * len(self.graph)
        queue = deque([start])
        distances[start] = 0
        ans = [0] * len(self.graph)

        while queue:
            now = queue.pop()
            for to in self.graph[now]:
                if distances[to] != INF:
                    continue
                queue.append(to)
                
                ans[to] = now
                distances[to] = distances[now] + 1
        return distances, ans


def main():
    n, m = LI()
    g = Graph(n)
    for _ in range(m):
        a, b = LI()
        a, b = a - 1, b - 1
        g.add_edge(a, b)

    bfs_res, ans = g.bfs(0)
    for d in bfs_res:
        if d == INF:
            print('No')
            return

    print('Yes')
    print(*map(lambda x: x + 1, ans[1:]), sep='\n')


if __name__ == '__main__':
    main()

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

adjacent_list = [[] for _ in range(n + 1)]

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

signs = [-1 for _ in range(n + 1)]

que = deque()
que.append(1)

while que:
    node = que.popleft()
    for i in adjacent_list[node]:
        if signs[i] == -1:
            que.append(i)
            signs[i] = node


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

Solution (Python):
from collections import deque

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

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

for i in range(m):
    a,b = map(int,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
pre = [-1] * (n+1)
dist = [-1] * (n+1)
dist[1] = 0
que = deque([1])

while que:
    now = que.popleft()
    for i in adjacent_list[now]:
        if pre[i] == -1:
            que.append(i)
            dist[i] = dist[now] + 1
            pre[i] = now
print("Yes")
for i in range(2,n+1):
    print(pre[i])

Solution (Python):
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, con, val=None):
        
        self.con = con
        self.val = val
        self.N = len(self.con)
        
        self.dist = [-1]*self.N
        self.que = deque()

        
        self.dist[0] = 0
        self.que.append(0)

    def bfs(self):
        while self.que:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = v+1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  
    A_B_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  
        A_B_arr.append(_)
    
    con = [[] for i in range(N)]
    for A,B in A_B_arr:
        A -= 1
        B -= 1
        con[A].append(B)
        con[B].append(A)

    bfs = BFS(con)
    bfs.bfs()
    
    if -1 in bfs.dist[1:]:
        print('No')
    else:
        print('Yes')
        for _ in bfs.dist[1:]:
            print(_)

Solution (Python):
from collections import deque

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

flug = [0 for i in range(N+1)]

to[0].append(1)


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

q = deque([0])
while (len(q) != 0):
    i = q.popleft()
    for j in to[i]:
        if flug[j] == 0:

            flug[j] = i
            q.append(j)

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

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

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

dist = [100001 for i in range(N+1)]
flug = [1 for i in range(N+1)]

to[0].append(1)
dist[0] = 0
flug[0] = 0

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

q = []
q.append(0)
while (len(q) != 0):
    i = q.pop(0)
    for j in to[i]:
        if dist[j] == 100001:
            dist[j] = dist[i] +1
            flug[j] = i
            q.append(j)

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

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


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

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


dist = [-1] * n
dist[0] = 0

pre = [-1] * n


q = deque()
q.append(0)

while len(q) != 0:
    V = q.popleft()
    for v in G[V]:
        if pre[v] == -1:
            dist[v] = dist[V] + 1
            pre[v] = V
            q.append(v)

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())
graph = [0] + [[] for _ in range(n)]
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

from collections import deque

def bfs(graph, queue, dist, prev):
    while queue:
        current = queue.popleft()

        for c in graph[current]:
            if dist[c] != -1:
                continue
            dist[c] = dist[current] + 1
            prev[c] = current
            queue.append(c)

queue = deque([1])
dist = [0] + [-1] * n
dist[1] = 0
prev = [0] + [-1] * n
prev[1] = 0

bfs(graph, queue, dist, prev)
if -1 in prev:
    print('No')
else:
    print('Yes')
    for n in prev[2:]:
        print(n)

Solution (Python):
from collections import deque

n,m = map(int,input().split())
INF = 114514191981036436433-4

r = [[] for _ in range(n)]
aa,bb = [] , []

for i in range(m):
    a,b = map(int,input().split())
    aa.append(a-1)
    bb.append(b-1)
    r[a-1].append(b-1)
    r[b-1].append(a-1)
    
q = deque()
q.append(0)
d = [INF]*n
d[0] = 0

while q:
    p = q.popleft()
    for i in r[p]:
        if d[i] == INF:
            q.append(i)
            
        d[i] = min(d[p] + 1 , d[i])
    
ans = [0]*n
for i in range(m):
    if d[aa[i]] - d[bb[i]] == 1:
        ans[aa[i]] = bb[i] + 1
    elif d[bb[i]] - d[aa[i]] == 1:
        ans[bb[i]] = aa[i] + 1
        
print("Yes")
for i in ans[1:]:
    print(i)

Solution (Python):
def solve(n, m, a, b):
    V = [i+1 for i in range(n)]
    E = {v: [] for v in V}
    for i in range(m):
        E[a[i]].append(b[i])
        E[b[i]].append(a[i])
    parent = {}
    que = [1]
    while que:
        s = que.pop(0)
        for t in E[s]:
            if not t in parent:
                parent[t] = s
                que.append(t)
    if len(parent) < n - 1:
        ans = ["No"]
    else:
        ans = ["Yes"] + [str(parent[v]) for v in range(2,n+1)]
    return "\n".join(ans)

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
print(solve(n, m, a, b))

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

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

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

que = deque([])
que.append(0)

f_inf = float("inf")
dist = [f_inf for _ in range(n)]
dist[0] = 0

pre = [-1 for _ in range(n)]

while que:
    v = que.popleft()
    for u in to[v]:
        if dist[u] != f_inf: continue
        dist[u] = dist[v] + 1
        pre[u] = v
        que.append(u)

print("Yes")
for i in range(n):
    if i == 0: continue
    ans = pre[i]
    ans += 1
    print(ans)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b)
    g[b-1].append(a)
q=deque()
q.append(1)
check=[0]*n
check[0]=1
ans=[0]*n
while len(q)!=0:
    v=q.popleft()
    for u in g[v-1]:
        if check[u-1]==0:
            check[u-1]=1
            ans[u-1]=v
            q.append(u)
print("Yes")
for i in range(1,n):
    print(ans[i])

Solution (Python):
from collections import deque

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


q = deque([0]) 
while q: 
    p = q.popleft() 
    for i in tree[p]:
        if ans[i] < 0: 
            ans[i] = p
            q.append(i) 

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

Solution (Python):
n, m = map(int, input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ans = [-1 for _ in range(n)]
ans[0] = 0
tree=[[]for _ in range(n)]
for a,b in ab:
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
visited={0}
q=[0]
for i in q:
    for j in tree[i]:
        if ans[j] < 0:
            q.append(j)
            ans[j]=i+1
print("Yes")
for i in ans[1:]:
    print(i)

Solution (Python):
import queue

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

a = []
b = []

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


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

for i in range(m):
	c[a[i]].append(b[i])
	c[b[i]].append(a[i])

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


inf = 10**8
d = [inf]*n
d[0] = 0
ans = [0]*n

while not q.empty():
	x = q.get()
	for i in c[x]:
		if d[i]==inf:
			q.put(i)
			d[i] = d[x]+1
			ans[i] = x+1

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b)
  g[b-1].append(a)
q=deque()
q.append(1)
check=[0]*n
check[0]=1
ans=[0]*n
while len(q)!=0:
  v=q.popleft()
  for u in g[v-1]:
    if check[u-1]==0:
      check[u-1]=1
      ans[u-1]=v
      q.append(u)
print("Yes")
for i in range(1,n):
  print(ans[i])