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())
roads = []
for _ in range(N):
    roads.append([])
for _ in range(M):
    a, b = map(int, input().split())
    roads[a - 1].append(b - 1)
    roads[b - 1].append(a - 1)
visited = [float('inf')] * N
q = deque()
q.append(0)
visited[0] = 0
pre = [-1] * N
while q:
    now_room = q.popleft()
    for next_room in roads[now_room]:
        if visited[next_room] != float('inf'):
            continue
        visited[next_room] = visited[now_room] + 1
        if pre[next_room] == -1:
            pre[next_room] = now_room + 1
        q.append(next_room)



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

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

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())

    graph = [[] for _ in range(N)]
    for i 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")


main()

Solution (Python):
from collections import deque

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

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

print('Yes')

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

while q:
    x = q.popleft()
    for i in route[x]:
        if d[i] == -1:
            d[i] = x + 1
            q.append(i)

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

Solution (Python):
from collections import deque

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

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

print('Yes')

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

while q:
    x = q.popleft()
    for i in route[x]:
        if d[i] == -1:
            d[i] = x + 1
            q.append(i)

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

Solution (Python):
from collections import deque
import sys
N, M = list(map(int, input().split()))
ans = [-1] * N
visited = [False] * N
dq = deque([0])
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
while dq:
   i = dq.popleft()
   if visited[i]:
      continue
   visited[i] = True
   next_rs = path[i]
   for j in range(len(next_rs)):
      if not visited[next_rs[j]]:
         dq.append(next_rs[j])
         if ans[next_rs[j]] == -1:
            ans[next_rs[j]] = i
if sum(visited) == N:
   print('Yes')
   for i in range(N):
      if i == 0:
         continue
      else:
         print(ans[i]+1)
else:
   print(-1)

Solution (Python):

from collections import deque

n,m=map(int,input().split())
lst=[[] for i in range(n)]
visited=[False for i in range(n)]
ans=[0]*n

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

Q=deque()
Q.append((0))
visited[0]=True

while Q:
  v=Q.popleft()
  for i in lst[v]:
        if visited[i]==False:
              visited[i]=True
              ans[i]=v
              Q.append((i))

print('Yes')

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

Solution (Python):
from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])

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

to = [[] for i in range(100010)]

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

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


dist = [0] * N
pre = [0] * N

while len(q) != 0:
    a = q.pop(0)
    for i in to[a]:
        if dist[i-1] == 0:
            dist[i-1] = dist[a-1] + 1
            pre[i-1] = a
            q.append(i)
    

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

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

neighbors = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in neighbors.keys():
    neighbors.update({a:set()})
  if b not in neighbors[a]:
    neighbors[a].add(b)
  if b not in neighbors.keys():
    neighbors.update({b:set()})
  if a not in neighbors[b]:
    neighbors[b].add(a)

lst = [0] * (n - 1) 
visited = set() 
queue = [[0, set([1])]]
while queue:
  
  pre_room, rooms = queue.pop(0) 
  
  for room in rooms:
    if room in visited:
      continue
    if lst[room - 2] == 0 and room != 1: 
      lst[room - 2] = pre_room 
    visited.add(room) 
    next_rooms = set() 
    for nei in neighbors[room]:
      next_rooms.add(nei)
    next_rooms = [room, next_rooms]
    queue.append(next_rooms)
if 0 in lst:
  print('No')
else:
  print('Yes')
  for i in range(n - 1):
    print(lst[i])

Solution (Python):

import collections
n, m = map(int, input().split( ))
lis = [[] for _ in range(n+1)]
for _ in range(m):
  a,b = map(int, input().split( ))
  lis[a].append(b)
  lis[b].append(a)

ans = [0]*(n+1)
q = collections.deque()
q.append(1)
count = [0]*(n+1)

count[1] = 1
while len(q) != 0:
  v = q.popleft()

  
  for u in lis[v]:
    if count[u] == 0:
      count[u] = 1
      ans[u] = v
      q.append(u)
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Solution (Python):
from collections import deque

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

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

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




mark = [-1]*(n+1)
mark[0] - 0
mark[1] = 0


d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if mark[i] != -1:
        
            continue
        mark[i] = v
        
        d.append(i)

if '-1' in mark:
    print('No')
else:
    print('Yes')
    print(*mark[2:], sep='\n')

Solution (Python):
from collections import deque

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

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

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



mark = [-1]*(n+1)
mark[0] = 0
mark[1] = 0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if mark[i] != -1:
            continue
        mark[i] = v
        d.append(i)
if mark.count(-1) > 0:
    print("No")
else:
    print("Yes")
    ans = mark[2:]
    print(*ans, sep="\n")

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

n,m=nii()

tree=[[] for i in range(n)]
for i in range(m):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

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

que=deque()
que.append(0)

while que:
  x=que.popleft()
  for i in tree[x]:
    if ans[i]==-1:
      ans[i]=x
      que.append(i)

if -1 in ans:
  print('No')
else:
  print('Yes')
  for i in ans[1:]:
    print(i+1)

Solution (Python):
from collections import deque

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

for i 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)

if -1 in dist:
    print("No")
else:
    print("Yes")
ans = dist[2:]
print(*ans, sep="\n")

Solution (Python):
from collections import deque

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

G = [[] for _ in range(N+1)]
m = [tuple(map(int, input().split())) for _ in range(M)]

for a, b in 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):


from collections import deque

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

neighbor = [[] for _ in range(n)]
for edge in edges:
    neighbor[edge[0]-1].append(edge[1]-1)  
    neighbor[edge[1]-1].append(edge[0]-1)

queue = deque()
queue.append(0)

back = [-1] * n  
back[0] = 0
while len(queue) > 0:
    vertex = queue.popleft()
    for nei in neighbor[vertex]:
        if back[nei] == -1:
            back[nei] = vertex
            queue.append(nei)
        
print('Yes')
for i in back[1:]:
    print(i+1)

Solution (Python):
from sys import stdin,stdout
from collections import defaultdict
def bfs(src):
    q=[src]
    par=[-1]*(n+1)
    vis=[0]*(n+1)
    ans=[]
    while q:
        cur=q.pop(0)
        for neigh in g[cur]:
            if not vis[neigh]:
                vis[neigh]=1
                q+=[neigh]
                par[neigh]=cur
    for i in range(2,n+1):
        if par[i]==-1:
            print('No')
            return
        ans+=[par[i]]
    print('Yes')
    for v in ans:
        print(v)
for i in range(1):
    
    g=defaultdict(list)
    n,e=list(map(int,stdin.readline().split()))
    for _ in range(e):
        a,b=map(int,stdin.readline().split())
        g[a]+=[b]
        g[b]+=[a]
    bfs(1)

Solution (Python):
import sys
from collections import deque

def input():
  return sys.stdin.readline()

N,M=map(int,input().split())
L=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  L[a-1].append(b)
  L[b-1].append(a)
A=[0]*N
a,b = N,0
d=deque([])
for l in L[0]:
  d.append((1,l))
while a>b:
  i,j=d.popleft()
  if A[j-1]==0:
    b+=1
    A[j-1]=i
    for l in L[j-1]:
      d.append((j,l))
if a==b:
  print("Yes")
  for i in range(1,N):
    print(A[i])
else:
  print("No")

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

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

d = deque()
d.append(1)
ans = [0 for _ in range(n+1)]
while d:
    v = d.popleft()
    for i in route[v]:
        if dist[i] != 0:
            continue
        dist[i] = dist[v]+1
        ans[i] = v
        d.append(i)

if len(dist[2:]) > 0:
    print('Yes')
    print(*ans[2:], sep="\n")
else:
    print('No')

Solution (Python):
from collections import deque

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

def bfs(s):
    seen = [0]*(N+1)
    d = [0]*(N+1)
    prev = [0]*(N+1)
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return prev
  
prev = bfs(1)

print('Yes')
print(*prev[2:])

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

dist[1] = 1
q = deque([1])
while q:
    x = q.popleft()
    for j in graph[x]:
        if dist[j] == -1:
            q.append(j)
            dist[j] = x
ans = dist[2:]
if -1 in ans:
    print("No")
else:
    print("Yes")
    print(*ans, sep = "\n")

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


ikeru = [[] for i in range(N)]
for i in range(M):
    ikeru[AB[i][0]-1].append(AB[i][1]-1)
    ikeru[AB[i][1]-1].append(AB[i][0]-1)




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

out=[10**6]*N
out[0]=0

while que:
    p = que.popleft()
    

    for next in ikeru[p]:
        
        if out[next]==10**6:
            que.append(next)
            out[next]=p+1



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

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

ars = [0] * N
todo = deque([0])
done = {0}
while todo:
    p = todo.popleft()
    for np in G[p]:
        if np in done:
            continue
        todo.append(np)
        ars[np] = p + 1
        done.add(np)

if len(done) == N:
    print("Yes")
    for i in range(1, N):
        print(ars[i])
else:
    print("No")

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

class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def path_list(self, start=1):
        """
        :return: スタート地点から最短経路で進んだ時の、各頂点の一個前に訪問する頂点番号
                訪問しない場合は -1 を返す
        """
        self.distance_list(start)
        if self.decrement:
            start -= 1
        return list(p + self.decrement for p in self.parent[1:])



N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

res = graph.path_list()
if -1 in res:
    print("No")
else:
    print("Yes")
    print(*res, sep="\n")

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist



N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

if -1 in graph.distance_list():
    print("No")
else:
    print("Yes")
    print(*list(p+1 for p in graph.parent[1:]), sep="\n")

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist



N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

if -1 in graph.distance_list():
    print("No")
else:
    print("Yes")
    print(*list(p+1 for p in graph.parent[1:]), sep="\n")

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

Solution (Python):
from collections import deque

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

ans=[0]*(N+1)
d=deque([1])
while d:
  c=d.popleft()
  for g in G[c]:
    if not ans[g]:
      d.append(g)
      ans[g]=c

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

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

ans=[0]*(N+1)
d=[1]
while d:
  c=d.pop(0)
  for g in G[c]:
    if not ans[g]:
      d.append(g)
      ans[g]=c

print('Yes')
for i in range(2, N+1):
  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)]

G = {i:[] for i in range(N+1)}
for a,b in AB:
    G[a].append(b)
    G[b].append(a)
    
parent = [0]*(N+1)
parent[0]==-1
parent[1]==-1
q = deque()
q.append(1)
while len(q)>0:
    room = q.popleft()
    child = G[room]
    
    for i in child:
        if parent[i] == 0:
            parent[i] = room
            q.append(i)
    
    
if min(parent[2:])==0:
    print('No')
else:
    print('Yes')
    for i in parent[2:]:
        print(i)

Solution (Python):
import queue

def main():
    n, m = map(int, input().split())
    graph = [[]for i in range(n + 1)]
    a = None
    b = None
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    sign = [0 for i in range(n + 1)]
    vis = [False for i in range(n + 1)]
    q = queue.Queue(0)
    q.put(1)
    vis[1] = True
    while q.empty() == False:
        u = q.get()
        for val in graph[u]:
            if vis[val] == False:
                vis[val] = True
                q.put(val)
                sign[val] = u
    for i in range(2, n + 1):
        if sign[i] == 0:
            print("No")
            return
    print("Yes")
    for i in range(2, n + 1):
        print(sign[i])



if __name__ == "__main__":
    main()

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)

q = deque([0])
d = [-1]*n
d[0] = 0
ans = [0]*n
print("Yes")

while q:
    p = q.popleft() 
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node) 
        else:
            if d[node] + 1 == d[p]: 
                ans[p] = node + 1

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

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)

q = deque([0])
d = [-1]*n
d[0] = 0
ans = [0]*n
print("Yes")

while q:
    p = q.popleft() 
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node) 
        else:
            if d[node] + 1 == d[p]:
                ans[p] = node + 1

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

Solution (Python):


from collections import deque

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

way=[[] for i in range(N)]

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

visited=[-1 for i in range(N)]
visited[0]=0
dq=deque([0]) 

while dq:
    temp=dq.popleft()
    for item in way[temp]:
        if visited[item]==-1:
            visited[item]=temp
            dq.append(item)

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

Solution (Python):
import sys
from collections import deque

icase=0
if icase==0:
    n,m=map(int,input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
elif icase==1:
    n,m=4,4
    g=[[1], [0, 2, 3], [1, 3], [2, 1]]
elif icase==2:
    n,m=6,9
    g=[[5, 4], [3, 5], [3, 4], [2, 1, 5, 4], [2, 0, 3, 5], [0, 3, 1, 4]]

q=deque([0])

stack=[0]
parent=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()

    for v in g[state]:


        if parent[v] !=-1:
            continue
        else:

            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)

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

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

    print(parent[i]+1)

Solution (Python):
def main():
    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)        
    
    guide = [0] * N
    guide[0] = 1
    q = deque()
    q.append(0)
    while len(q) > 0:
        u = q.popleft()
        for v in to[u]:
            
            if guide[v] != 0:
                continue
            guide[v] = u+1
            q.append(v)

    print("Yes")
    for g in guide[1:]:
        print(g)

if __name__ == '__main__':
    main()

Solution (Python):
import queue

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

Root=[]
Sign=[]

for i in range(N+1):
    Root.append([])
    Sign.append(0)


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

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

while not q.empty():
    r = q.get()
    for nextR in Root[r]:
        if Sign[nextR] == 0:
            q.put(nextR)
            Sign[nextR]=r

if 0 in Sign[1:]:
    print('No')
else:
    print('Yes')
    for i in range(2,N+1):
        print(Sign[i])

Solution (Python):
from collections import deque

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

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

for a,b in ab:
  c[a].append(b)
  c[b].append(a)
seen = [float('inf')]*(n+1)
que=deque()
que.append(1)
seen[1] = 0
while que:
  s=que.popleft()
  for i in c[s]:
    if seen[i] == float('inf'):
      que.append(i)
      seen[i] = s
if sum(seen[2:]) == float('inf'):
  print('No')
else:
  print('Yes')
  for i in seen[2:]:
    print(i)

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

from collections import deque
def solve():
    prev = [-1]*N
    prev[0]='Yes'
    d = deque([(0,0)])
    while len(d):
        v,cnt = d.popleft()
        for u in edge[v]:
            if prev[u]==-1:
                prev[u]=v+1
                d.append((u,cnt+1))
    if -1 in prev:
        return ['No']
    return prev
print(*solve(),sep='\n')