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


def main():
    n, m = map(int, input().split())
    es = [[] for _ in range(n+1)]
    ans = [0 for _ in range(n+1)]

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

    q = deque([1])
    while len(q) > 0:
        p = q.popleft()

        for t in es[p]:
            if ans[t] > 0:
                continue
            ans[t] = p
            q.append(t)

    if 0 in ans[2:]:
        print("No")
    else:
        print("Yes")
        for a in ans[2:]:
            print(a)


if __name__ == '__main__':
    main()

Solution (Python):
import queue


def main():
    n, m = map(int, input().split())
    es = [[] for _ in range(n+1)]
    ans = [0 for _ in range(n+1)]

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

    q = queue.Queue()
    q.put(1)
    while not q.empty():
        p = q.get()

        for t in es[p]:
            if ans[t] > 0:
                continue
            ans[t] = p
            q.put(t)

    if 0 in ans[2:]:
        print("No")
    else:
        print("Yes")
        for a in ans[2:]:
            print(a)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

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

for _ in range(m):
    x, y = map(int, input().split())
    V[x].append(y)
    V[y].append(x)

d = deque([1])

while d:
    l = d.popleft()
    for v in V[l]:
        if ans[v] != -1:
            continue
        ans[v] = l
        d.append(v)
        

    
if ans.count(-1) > 0:
    print('No')
else :
    print('Yes')
    print(*ans[2:], sep="\n")

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
path = defaultdict(list)

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

prev = [0] * N
dist = [0] * N
q = deque([0])

while (len(q) > 0):
    a = q.popleft()
    for b in path[a]:
        if dist[b] != 0:continue
        q.append(b)
        prev[b] = a
        dist[b] = dist[a] + 1

print('Yes')

for a in prev[1:]:
    a += 1
    print(a)

Solution (Python):
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())

from collections import deque
links = [[] for _ in range(N+1)]
for i in range(M):
    links[A[i]].append(B[i])
    links[B[i]].append(A[i])

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*
(n,m),*c = [[*map(int,i.split())]for i in open(0)]
g = [[]for _ in range(n+1)]

for a,b in c:
    g[a]+=[b]
    g[b]+=[a]

q=deque([1])
r=[0]*(n+1)

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

print("Yes",*r[2:],sep="\n")

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        sign[u] = v
        dfs(u,v)

def bfs(v):
    que = deque([])
    que.append(v)
    while que:
        p = que.popleft()
        if visited[p] == 0:
            visited[p] = 1
            for u in graph[v]:
                que.append(u)

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) 
    cost = [float('inf')] * (N+1) 
    cost[s] = 0 
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: 
            continue
        for u in graph[v]:
            tmp = 1 + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                path[u] = v
                heapq.heappush(hq, (tmp, u))
    return path

N,M = map(int,input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
path = [0]*(N+1)
c = dijkstra(1)
print("Yes")
for i in range(2,N+1):
    print(c[i])

Solution (Python):
from collections import deque
N , M = map(int,input().split())
g = [[] for _ in range(N)]
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
branch_list = [0 for i in range(N)]
def bfs(u):
    queue = deque([u])
    d = [None] *N
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] +1
                queue.append(i)
                branch_list[i] = v +1
    return d
d = bfs(0)
for i in range(1,len(branch_list)):
    if branch_list[i] == 0:
        print("No")
        break
    if i == 1:
        print("Yes")
    print(branch_list[i])

Solution (Python):
from collections import deque

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

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

tai = [False] * (n+1)
tai[1] == True
ans = [0] * (n+1)

tri = deque([1])
while len(tri) > 0:
    num = tri.popleft()
    for i in lst[num]:
        if tai[i]:
            continue
        tri.append(i)
        tai[i] = True
        ans[i] = num

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)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
ans = [-1] * (n - 1)
used = [0]*n
used[0] = 1
que = deque([0])
while que:
    posi = que.popleft()
    for p in graph[posi]:
        if not used[p]:
            que.append(p)
            ans[p-1] = posi+1
            used[p] = 1
print('Yes')
print(*ans, sep='\n')

Solution (Python):
N,M=map(int,input().split())
V=[[]for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
print('Yes')
p,q=0,[0]
seen=[0]*N
d=[0]*N
while len(q)!=p:
    for i in V[q[p]]:
        if not seen[i]:
            q.append(i)
            d[i]=q[p]+1
        seen[i]+=1
    p+=1
d.pop(0)
for i in d:print(i)

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

visited = set()
ans = [0]*n
stack = [0]
for i in stack:
    
    for j in AB[i]:
        if j in visited:
            continue
        visited.add(j)
        ans[j] = i+1
        stack.append(j)
    
for i in ans[1:]:
    if i==0:
        print('No')
        exit()
print('Yes')
for i in ans[1:]:
    print(i)

Solution (Python):
import math, sys
from collections import deque
N , M = list(map(int, input().split()))

Es = [[] for _ in range(N+1)]
for i in range(M):
    A , B = list(map(int, input().split()))
    Es[A].append(B)
    Es[B].append(A)

used = [False]*(N+1)
used[1] = True

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

cand = deque([1])
while len(cand)>0:
    tar = cand.popleft()
    for each in Es[tar]:
        if used[each]:
            continue
        cand.append(each)
        ans[each]=tar
        used[each]= True

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 _ in range(M):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)


from collections import deque

queue=deque([1])
d=[None]*(N+1)
d[1]=0
ans=[0]*(N+1)
while queue:
    v=queue.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i]=d[v]+1
            ans[i]=v
            queue.append(i)

            
print("Yes")
for i in range(2,len(ans)):
    print(ans[i])

Solution (Python):
from collections import deque

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

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

    labeled = [False] * (N+1)
    
    labeled[1] = True

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

    queue = deque([1])

    while len(queue) > 0:
        room = queue.popleft()
        nexts = next_rooms[room]
        for n in nexts:
            if labeled[n]:
                continue
            labels[n] = room
            labeled[n] = True
            queue.append(n)

    for i in range(1, N+1):
        if not labeled[i]:
            print("No")
            return

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


main()

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

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


ans = [None] * N

from collections import deque
q = deque([])

q.append((0, -1))
while q:
  v, parent = q.popleft()
  if ans[v] is not None:
    continue
  ans[v] = parent + 1
  for child in G[v]:
    if child == parent:
      continue
    q.append((child, v))

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

Solution (Python):
from collections import deque

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

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

ans = [-1] * (n - 1)

q = deque()
q.append(0)
used = {0}
while q:
  node = q.popleft()
  for next_node in graph[node]:
    if next_node in used:
      continue
    q.append(next_node)
    used.add(next_node)
    ans[next_node - 1] = node + 1

print('Yes')
print(*ans, sep='\n')

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):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

from collections import deque

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

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

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

if -1 in dist:
    print('No')
else:
    print('Yes')
    for v in prev[2:]:
        print(v)

Solution (Python):
from collections import deque

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

graph = [[] for _ in range(n+1)]
dist = [0] * (n+1)
visited = [0] * (n+1)


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

root = 1
visited[root] = 1
d  = deque([root])

while d:
    v = d.popleft()
    for i in graph[v]:
        if visited[i]:
            continue
        visited[i] = 1
        dist[i] = v
        d.append(i)

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

Solution (Python):
from collections import deque
n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(m)]
g = [[] for _ in range(n)]
l = [float('inf')] * n

for x,y in li:
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

def bfs():
    que = deque()
    l[0] = 0
    que.append(0)
    while que:
        a = que.popleft()
        for i in g[a]:
            if l[i] != float('inf'):continue
            l[i] = a
            que.append(i)
bfs()
for i in l:
    if i == float('inf'):
        print('No')
        exit()
print('Yes')
for i in l[1:]:
    print(i+1)

Solution (Python):
N,M = map(int,input().split())
t = [[i+1] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    t[A-1].append(B)
    t[B-1].append(A)
from collections import deque
d = deque()
ans = [-1]*(N)
d.append(t[0])
while len(d) > 0:
    z = d.popleft()
    x = z[0]
    for i in range(1,len(z)):
        if ans[z[i]-1] == -1:
            ans[z[i]-1] = x
            d.append(t[z[i]-1])
print("Yes")
for i in range(1,len(ans)):
    print(ans[i])

Solution (Python):
from collections import deque
INF = 1_000_000_000
def main():
    n, m = map(int, input().split(" "))
    to = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda i:int(i)-1, input().split(" "))
        to[a].append(b)
        to[b].append(a)
    que = deque()
    d = {i:INF for i in range(n)}
    prev = {i:-1 for i in range(n)}
    d[0] = 0
    que.append(0)
    while que:
        v = que.popleft()
        for i in to[v]:
            if d[i] != INF: continue
            d[i] = d[v] + 1
            prev[i] = v
            que.append(i)
    print("Yes")
    for i in range(n):
        if i == 0: continue
        print(prev[i]+1)
        
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def main():
    n, m = map(int, input().split())
    route = [[] for _ in range(n)]  
    INF = 10 ** 12

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

    d = deque()
    d.append(0)
    dist = [0] + [INF] * (n - 1)  
    pre = [-1] * n  

    while d:
        u = d.popleft()
        for v in route[u]:
            if dist[v] != INF:
                continue
            dist[v] = dist[u] + 1
            pre[v] = u
            d.append(v)

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


if __name__ == "__main__":
    main()

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

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

for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  adj_list[_].append(__)
  adj_list[__].append(_)
  
distance = [None for i in range(n)]
updated_from = [None for i in range(n)]

newly_visited = deque([0])
distance[0] = 0

while len(newly_visited) > 0:
  now = newly_visited.popleft()
  for i in adj_list[now]:
    if distance[i] is not None: continue
    newly_visited.append(i)
    distance[i] = distance[now] + 1
    updated_from[i] = now



    
"""
print(distance)

for i in range(n):
  
  now = i
  path = [now]
  while now != 0:
    now = updated_from[now]
    path.append(now)
  print(i, path) 
"""

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

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())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                p[i] = v
                queue.append(i)
    return d

p = [None]*n
d = bfs(0)
if None in p[1:]:
    print('No')
else:
    print('Yes')
        
for q in range(1,n):
    print(int(p[q])+1)

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())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    
def bfs(u):
    queue = deque([u])
    d = [None]*n
    
    d[u] = 0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v]+1
                p[i] = v
                queue.append(i)
    return d

p = [None]*n
d = bfs(0)
if None in p[1:]:
    print('No')
else:
    print('Yes')
        
for q in range(1,len(p)):
    print(int(p[q])+1)

Solution (Python):

from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
d = [-1] * (n+1)
d[0],d[1] = 0,0
queue = deque()
queue.append(1)
while queue:
    x = queue.popleft()
    for i in l[x]:
        if d[i] == -1:
            d[i] = x
            queue.append(i)
print('Yes')
for i in d[2:]:
    print(i)

Solution (Python):

from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
d = [-1] * (n+1)
d[0],d[1] = 0,0
queue = deque()
queue.append(1)
while queue:
    x = queue.popleft()
    for i in l[x]:
        if d[i] == -1:
            d[i] = x
            queue.append(i)
if -1 in d:
    print('No')
else:
    print('Yes')
    for i in d[2:]:
        print(i)

Solution (Python):
from collections import deque

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

for i in range(M):
  a,b = map(int,input().split())
  room_g[a].append(b)
  room_g[b].append(a)
  
sign = [-1]*(N+1)
sign[0] = 0
sign[1] = 0

d = deque()
d.append(1)

while d:
  x = d.popleft()
  for i in room_g[x]:
    if sign[i] != -1:
      continue
    sign[i] = x
    d.append(i)
    
ans = sign[2:]
print("Yes")
for i in range(len(ans)):
  print(ans[i])

Solution (Python):
from collections import deque

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

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

INF = float('inf')
dist = [INF]*n
dist[0] = 0

pre = [-1]*n

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

while que:
    v = que.popleft()
    for u in to[v]:
        if dist[u] != INF:continue
        dist[u] = v + 1
        pre[u] = v
        que.append(u)
print("Yes")
for i in range(1,n):
    print(dist[i])

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):

from collections import deque

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

F=[-1]*(N+1)
q=deque()
q.append((1,1))
while q:
    room,par=q.popleft()
    if F[room]>0:
        continue
    F[room]=par
    for nroom in G[room]:
        q.append((nroom,room))
        
print('Yes')
print(*F[2:],sep='\n')

Solution (Python):
from collections import deque

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

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

for i in range(m):
  a,b = map(int, input().split())
  connected[a].add(b)
  connected[b].add(a)
  
def bfs(x):
  queue = deque([x])
  d = [None] * (n+1)
  d[x] = 0
  while queue:
    v = queue.popleft()
    for i in connected[v]:
      if d[i] is None:
        d[i] = v
        queue.append(i)
  return d

print('Yes')
ans = bfs(1)[2:]

for i in ans:
  print(i)

Solution (Python):
from collections import deque

print("Yes")

N, M = map(int, input().split())
net = [[] for _ in range(N+1)]
vect = [0]*(N+1)

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

q = deque()
q.append(1)

while len(q)>0:
	t = q.popleft()
	for i in net[t]:
		if t != i and vect[i] == 0:
			vect[i] = t
			q.append(i)

for i in range(2, N+1):
	print(vect[i])

Solution (Python):

"""
Created on Mon Sep  7 21:29:58 2020

@author: liang
"""

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

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

visited = [False for i in range(N)]
sign = [-1]*N

from collections import deque

visited[0] = True
q = deque()
q.append(0)
sign[0] = 0

while q:
    cur = q.popleft()
    for a in adj[cur]:
        if not visited[a]:
            visited[a] = True
            sign[a] = cur + 1
            q.append(a)

if all(x >= 0 for x in sign):
    print("Yes")
    [print(a) for a in sign[1:] ]
else:
    print("No")

Solution (Python):
from collections import deque

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

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

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

que = deque()
que.append(0)

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

print('Yes')
while len(que) > 0:
    c = que.popleft()
    for ne in graph[c]:
        if visited[ne] == 1:
            continue
        que.append(ne)
        ans[ne] = c
        
        visited[ne] = 1

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

Solution (Python):
import collections

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

ways = collections.defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ways[a].add(b)
    ways[b].add(a)

dist = [-1] * N
q = collections.deque()

dist[0] = True
q.append(0)

while q:
    n = q.popleft()
    for adjacent in ways[n]:
        if dist[adjacent] != -1:
            continue
        dist[adjacent] = dist[n] + 1
        q.append(adjacent)


if -1 in dist:
    print('No')
else:
    print('Yes')
    for n, d in enumerate(dist):
        if n == 0:
            continue
        for adjacent in ways[n]:
            if d - 1 == dist[adjacent]:
                print(adjacent + 1)
                break

Solution (Python):
import queue

q = queue.Queue()
bool = True


def bfs():
    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
    


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
bfs()
if bool:
    print("Yes")
    for i in range(1, N):
        print(ans[i] + 1)
else:
    print("No")

Solution (Python):
from collections import deque

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

data = [[] for _ in range(N)]

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

q = deque([(0,0)])
ans = [-1]*N



while q:
    x = q.popleft()
    for y in data[x[1]]:
        if y == x[0]:
            continue
        if ans[y] == -1:
            ans[y] = x[1]
            q.append((x[1],y))
    

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

Solution (Python):
from collections import defaultdict, deque

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

go_to = [None] * N

q = deque()
q.append((0, -1))
is_visited = set()

while q:
    node, prev = q.popleft()
    if node in is_visited:
        continue
    is_visited.add(node)
    go_to[node] = prev + 1
    for dest in edges[node]:
        q.append((dest, node))

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

Solution (Python):
from collections import deque

N, M = map(int, input().split())
routes = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  routes[a].append(b)
  routes[b].append(a)
checked = [0 for _ in range(N+1)]
route = deque(routes[1])
for r in routes[1]:
  checked[r] = 1
while(len(route) > 0):
  r = route.popleft()
  for rr in routes[r]:
    if checked[rr] == 0:
      checked[rr] = r
      route.append(rr)
for i in range(2, N+1):
  if checked[i] == 0:
    print('No')
    exit()
print('Yes')
for j in range(2, N+1):
  print(checked[j])

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())
    a, b = a - 1, b - 1
    to[a].append(b)
    to[b].append(a)
    

def main():
    dist = [-1] * N
    dist[0] = 0
    que = deque([0])
    ans = [0] * (N - 1)
    
    while que:
        v = que.popleft()
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                ans[nv - 1] = v + 1
                que.append(nv)
                
    print('Yes')
    print(*ans, sep='\n')
    
    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

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

q=deque()
q.append(0)

while q:
    v=q.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        else:
            dist[i]=dist[v]+1
            pre[i]=v
            q.append(i)

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

Solution (Python):
from collections import deque

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

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

d = deque([0])

while d:
    cur = d.popleft()
    for adj in edge[cur]:
        if sign[adj] == -1:
            sign[adj] = cur
            d.append(adj)

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

Solution (Python):
def main():
	N, M = [int(x) for x in input().split(" ")]
	route = [[] for i in range(N)]
	for i in range(M):
		A, B = [int(y) for y in input().split(" ")]
		route[A - 1] += [B]
		route[B - 1] += [A]

	checked = [1] + [0] * (N - 1)
	to_check = [{"src" : s, "dst" : 1} for s in route[0]]
	signal = [-1] + [0] * (N - 1)

	for r in route[0]:
		checked[r - 1] = 1

	while len(to_check) > 0:
		checking = to_check.pop(0)
		src = checking["src"]
		signal[src - 1] = str(checking["dst"])
		rooms = route[src - 1]
		for r in rooms:
			if checked[r - 1] == 0:
				to_check.append({"src": r, "dst": src})
				checked[r - 1] = 1

	if signal.count(0) > 0:
		print("No")
	else:
		print("Yes")
		print("\n".join(signal[1:]))

main()

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

import heapq

def dijkstra(s):
    d = 1
    hq = [(0, s)]
    heapq.heapify(hq) 
    cost = [float('inf')] * n 
    cost[s] = 0 
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: 
            continue
        for u in e[v]:
            tmp = 1 + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

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

d = dijkstra(0)


ans = [0]*(n)
for i in range(1,n):
    for j in e[i]:
        
        if d[j] == d[i] - 1:
            ans[i] = j + 1
            continue

print("Yes")
print(*ans[1:], sep="\n")

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
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())
def main():
    n,m = LI()
    route = [None] + [[] for _ in range(n)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)

    explored = {1}
    queue = collections.deque([1])
    ans = [None for _ in range(n+1)]
    while len(queue)!=0:
        nxt = queue.popleft()
        for nbh in route[nxt]:
            if nbh not in explored:
                ans[nbh] = nxt
                queue.append(nbh)
                explored.add(nbh)
    print("Yes")
    print(*ans[2:],sep="\n")
        
main()

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

visited = [False]*(n+1)
que = deque([1])
visited[1] = True
ans = [-1]*(n+1)

while que:
    v = que.popleft()
    vlist = d[v]
    for next in vlist:
        if not visited[next]:
            que.append(next)
            visited[next] = True
            ans[next] = v

if -1 in ans[2:]:
    print('No')
    exit()
print('Yes')
for i in range(2,n+1):
    print(ans[i])

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

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

conne = [[] for _ in range(n+1)]
dist = [999999]*(n+1)
par = [0] * (n+1)

for i in range(m):
    a,b = map(int,input().split()) 
    conne[a].append(b)
    conne[b].append(a)
    
q=queue.Queue()
dist[1] = 0
q.put((1,0))

while not q.empty():
    
    x,d = q.get()
    
    for i in conne[x]:
        if dist[i]==999999:
            q.put((i,d+1))
            par[i] = x
            dist[i] = d+1

if max(dist[1:]) == 999999:
    print("No")
    
else:
    print("Yes")    
    
    for i in par[2:]:
        print(i)

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

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

conne = [[] for _ in range(n+1)]
dist = [99999]*(n+1)
par = [0] * (n+1)

for i in range(m):
    a,b = map(int,input().split()) 
    conne[a].append(b)
    conne[b].append(a)
    
q=queue.Queue()
dist[1] = 0
q.put((1,0))

while not q.empty():
    
    x,d = q.get()
    
    for i in conne[x]:
        if dist[i]==99999:
            q.put((i,d+1))
            par[i] = x
            dist[i] = d+1


print("Yes")    

for i in par[2:]:
    print(i)