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 sys
from collections import deque

n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i:[] for i in range(n)}
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

que = deque([0])
res = {0:-1}
while len(que) > 0:
    cur = que.popleft()
    for _next in graph[cur]:
        if _next in res:
            continue
        res[_next] = cur
        que.append(_next)

if len(res) < n:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(res[i]+1)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
graph=[[] for i in range(N)]
for m in range(M):
    A,B=map(int,input().split())
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)
queue=deque([0])
distance=[0]*N
while queue:
    room=queue.popleft()
    for next_room in graph[room]:
        if distance[next_room]==0:
            distance[next_room]=room+1
            queue.append(next_room)
if 0 in distance:
    print("No")
else:
    print("Yes")
    print(*distance[1:],sep="\n")

Solution (Python):
from collections import deque

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

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

q = deque([0])
depth[0] = 0

while len(q) > 0:
  pos = q.popleft()
  for i in tree[pos]:
    if depth[i] == -1:
      depth[i] = depth[pos] + 1
      prev[i] = pos
      q.append(i)
      
print('Yes')
for i in range(1,n):
  ans = prev[i] + 1
  print(ans)

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

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)
print('Yes')
q = deque([])
dist = [INF] * n
pre = [-1] * n
dist[0] = 0
q.append(0)

while len(q) > 0:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != INF:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        q.append(i)

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

Solution (Python):
N, M = map(int, input().split())
adj = {}
for i in range(N):
    adj[i + 1] = []
for i in range(M):
    v1, v2 = map(int, input().split())
    adj[v1].append(v2)
    adj[v2].append(v1)

visited = {1}
parent = {1: None}
frontier = [1]
while frontier:
    nxt = []
    for u in frontier:
        for v in adj[u]:
            if v not in visited:
                parent[v] = u
                nxt.append(v)
                visited.add(v)
    frontier = nxt

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

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

from collections import deque

q = deque()

prev = [-1] * n

q.append(0)
while q:
    v = q.popleft()
    for e in edges[v]:
        if prev[e] != -1:
            continue
        prev[e] = v
        q.append(e)

print("Yes")
for val in prev[1:]:
    print(val + 1)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
graph=[[] for i in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)
queue=deque([0])
distance=[0]*N
while queue:
    que=queue.popleft()
    for value in graph[que]:
        if distance[value]==0:
            distance[value]=que+1
            queue.append(value)
if 0 in distance:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(distance[i])

Solution (Python):
from collections import deque
N,M=map(int,input().split())
graph=[[] for i in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)
queue=deque([0])
distance=[0]*N
while queue:
    value=queue.popleft()
    for i in graph[value]:
        if distance[i]<1:
            distance[i]=value+1
            queue.append(i)
if 0 in distance:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(distance[i])

Solution (Python):
from collections import deque

N, M = [int(i) for i in input().split()]

graph = { _:[] for _ in range(N)}

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

que = deque([0])

while que:
    v = que.popleft()
    for i in graph[v]:
        if visited[i] < 1:
            visited[i]+=v+1
            que.append(i)
            
if 0 in visited:
    print('No')
else :
    print('Yes')
    for v in visited[1:]:
        print(v)

Solution (Python):


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

def main():
    N,M=map(int,input().split())
    adj=[[] for i in range(N)]
    for i in range(M):
        A,B=map(int,input().split())
        adj[A-1]+=[B-1]
        adj[B-1]+=[A-1]
    parent=[-1]*N
    qu=deque([0])
    qup=qu.popleft
    qua=qu.append
    parent[0]=0
    while(len(qu)>0):
        v=qup()
        for nv in adj[v]:
            if parent[nv]!=-1:
                continue
            else:
                parent[nv]=v
                qua(nv)
    print("Yes")
    for i in range(1,N):
        print(parent[i]+1)
        
    
    
if __name__=="__main__":
    main()

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

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

for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    x[x1].append(y1)
    x[y1].append(x1)

ans = [10**10] * n
ans[0] = 0
root = [10**10] * n
root[0] = 0

from collections import deque
q = deque() 
for i in x[1]:
    q.append((1,i))
    root[i-1] = 1

while q:
    a,b = q.popleft() 
    
    if (ans[a-1] + 1) < ans[b-1]:
        root[b-1] = a
        ans[b - 1] = ans[a - 1] + 1
    else:
        continue

    for i in x[b]:
        if ans[i-1] > (ans[a-1]+1):
            q.append((b,i))


for i in ans[1:]:
    if i == 10**10:
        print("No")
        exit()

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

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)

p=[0]*N
que= deque([0])

while que:
    v=que.popleft()
    for i in graph[v]:
        if p[i]<1:
            p[i]=v+1
            que.append(i)

if 0 in p:
    print("No")
else:
    print("Yes", *p[1:], sep="\n")

Solution (Python):
N,M=map(int,input().split())
G=[]
for i in range(0,N):
    G.append([])

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

q=[]
sign=[-1]*N
sign[0]=0
q.append(0)
while q:
    x=q.pop(0)
    for nv in G[x]:
        if sign[nv]==-1:
            sign[nv]=x
            q.append(nv)

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

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    to = [[] for _ in range(n+1)]
    ans = [None]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        to[a].append(b)
        to[b].append(a)
    q = deque([1])
    while q:
        p = q.pop()
        children = to[p]
        for child in children:
            if ans[child] is None:
                ans[child] = p
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))
            
    

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

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

ans = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in g[i]:
        if ans[j] == -1:
            ans[j] = i
            q.append(j)
print('Yes')
for i in ans[2:]:
    print(i)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    to = [[] for _ in range(n+1)]
    ans = [None]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        to[a].append(b)
        to[b].append(a)
    q = deque([1])
    while q:
        p = q.pop()
        for child in to[p]:
            if ans[child] is None:
                ans[child] = p
                q.appendleft(child)
    print("Yes")
    for a in ans[2:]:
        print(a)
    

if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    n, m = map(int, input().split())
    adj = [[] for i in range(n+1)]
    for i in range(m):
        A, B = map(int, input().split())
        adj[A].append(B)
        adj[B].append(A)
    from collections import deque
    q = deque([1])
    ans = [-1 for i in range(n+1)]
    while q:
        v = q.popleft()
        for u in adj[v]:
            if ans[u] == -1:
                ans[u] = v
                q.append(u)
    print("Yes")
    for i in range(2, n+1):
        print(ans[i])

resolve()

Solution (Python):
from collections import deque


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

signs = [-1] * N
que = deque()
que.append((-2, 0))
seen = set()
while(que):
    fr, de = que.popleft()
    if(de in seen):
        continue
    signs[de] = fr
    seen.add(de)
    for next_de in gp[de]:
        if(next_de not in seen):
            que.append((de, next_de))

if(len(seen) == N):
    print('Yes')
    for s in signs[1:]:
        print(s+1)
else:
    print('No')

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

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

d = deque([0])
ans = [-1]*n
ans[0]=0
while d:
  p=d.popleft()
  for v in r[p]:
    if ans[v]!=-1: continue
    ans[v]=p
    d.append(v)
if -1 in ans:
  print('No')
  exit()
else:
  print('Yes')
  for v in ans[1:]:
    print(v+1)

Solution (Python):
def resolve():
    n, m = map(int, input().split()) 
    adj = [[] for i in range(n+1)] 
    for i in range(m):
        A, B = map(int, input().split())
        adj[A].append(B) 
        adj[B].append(A) 
    
    

    from collections import deque
    q = deque([1])
    ans = [-1 for i in range(n+1)]
    while q:
        v = q.popleft() 
        for u in adj[v]:
            if ans[u] == -1: 
                ans[u] = v
                q.append(u)
    print("Yes")
    for i in range(2, n+1):
        print(ans[i])

resolve()

Solution (Python):
(N, M), *miti = [[*map(int, line.split())] for line in open(0)]



A = [list() for _ in range(N+1)]
for m in miti:
    a, b = m
    A[a].append(b)
    A[b].append(a)



ans = [0] * (N + 1)
dist = [N] * (N + 1)
R = [list() for _ in range(N)]

dist[1] = 0
R[0].append(1)
ans[1] = 88888
for i in range(N):
    for p in R[i]:
        for t in A[p]:
            if i + 1 < dist[t]:
                dist[t] = i + 1
                R[i+1].append(t)
                ans[t] = p

dist = dist[1:]
ans = ans[2:]
if all(d < N for d in dist):
    print("Yes")
    for a in ans:
        print(a)
else:
    print("No")

Solution (Python):

from collections import deque

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

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


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









q = deque([1])

while q:
    
    i = q.popleft()
    
    for j in links[i]:
        
        
        if result[j] == -1:
            result[j] = i
            
            q.append(j)













print('Yes')

print('\n'.join(str(i) for i in result[2:]))

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


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



dist = [-1]*2 + [0 for i in range (n-1)]
dist[1] = 0
d = deque([1])


while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] == 0:
            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())


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]*2 + [0 for i in range (n-1)]

d = deque([1])


while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] == 0:
            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())
rootlist = [[] for i in range(n)]
flag = [False]*n

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

que = deque([1])
while que:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for root in flag[1:]:
    print(root)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
rootlist = [[] for i in range(n)]
flag = [False for i in range(n)]

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

que = deque()
que.append(1)
while len(que) !=0:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for root in flag[1:]:
    print(root)

Solution (Python):
from collections import deque

def mapinput():
    return map(int,input().split())

n,m = mapinput()
rootlist = [[] for i in range(n)]
flag = [False for i in range(n)]

for i in range(m):
    a,b= mapinput()
    rootlist[a-1].append(b)
    rootlist[b-1].append(a)

que = deque()
que.append(1)
while len(que) !=0:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for root in flag[1:]:
    print(root)

Solution (Python):
from collections import deque

def mapinput():
    return map(int,input().split())

n,m = mapinput()
rootlist = [[] for i in range(n)]
flag = [False for i in range(n)]

for i in range(m):
    a,b= mapinput()
    rootlist[a-1].append(b)
    rootlist[b-1].append(a)

que = deque()
que.append(1)
while len(que) !=0:
    now = que.popleft()
    for room in rootlist[now-1]:
        if flag[room-1] == False:
            flag[room-1] = now
            que.append(room)

print('Yes')
for i,root in enumerate(flag):
    if i == 0:
        continue
    print(root)

Solution (Python):
from collections import deque

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

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

ans = [0] * n
visited = [False] * n
visited[0] = True

for _ in range(m):
  s, t = map(int, input().split())
  grid[s].append(t)
  grid[t].append(s)

queue = deque([1])

while queue:
  node = queue.popleft()
  for i in grid[node]:
    if visited[i - 1]:
      continue
    visited[i - 1] = True
    ans[i - 1] = node
    queue.append(i)

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

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

from collections import deque

def bfs(u): 
    memo=[0]*(n+1)
    queue=deque([u])
    d=[None]*(n+1)
    d[u]=0
    while queue:
        v=queue.popleft()
        for i in edges[v]:
            if d[i] is None:
                d[i]=d[v]+1
                queue.append(i)
                memo[i]=v
    return d,memo
d,memo=bfs(1)
print("Yes")
for i in range(2,n+1):
    print(memo[i])

Solution (Python):
from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')

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

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

for a, b in ab:
    a, b = a - 1, b - 1
    rt[a].append(b)
    rt[b].append(a)

q = deque([0])
INF = float('inf')
dis = [INF] * n
dis[0] = 0
back = [-1] * n

while q:
    zzz = q.popleft()
    for i in rt[zzz]:
        if dis[zzz] + 1 >= dis[i]:
            continue
        dis[i] = dis[zzz]
        back[i] = zzz + 1
        q.append(i)

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

Solution (Python):
from collections import deque

N, M = [int(i) for i in input().split(' ')]
    
links = [[] for _ in range(N + 1)]

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

q = deque([1])

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

while q:
    i = q.popleft()
    for j in links[i]:
        if results[j] == -1:
            results[j] = i
            q.append(j)

print('Yes')
print('\n'.join(str(i) for i in results[2:]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import networkx as nx
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

g = nx.Graph()
g.add_edges_from([LIST() for _ in range(M)])
q = deque()
q.append(1)
ans = [None]*N
ans[0] = 0
while q:
	n = q.popleft()
	for node in g[n]:
		if ans[node-1] == None:
			q.append(node)
			ans[node-1] = n
print("Yes")
for i in range(1, N):
	print(ans[i])

Solution (Python):

import sys
import numpy as np
from collections import deque



N,M = [int(x) for x in sys.stdin.readline().split()]
g = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = [int(x) for x in sys.stdin.readline().split()]
    g[a].append(b)
    g[b].append(a)



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

if num_crew == N:
    print('Yes')
    for i in range(N-1):
        print(d[i+2])
else:
    print('No')

Solution (Python):
from collections import deque

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

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

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

Solution (Python):
import glob
import math



REL_PATH = 'ABC\\168\\D'


TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    alph = []

    def rec(self, result, now, max, N):

        if now == N:
            res = ""
            for i in result:
                res += self.alph[i]
            print(res)
            return

        if now == 0:
            result[0] = 0
            self.rec(result, now+1, 0, N)
            return

        for i in range(0, max+2):
            if i == N:
                return
            result[now] = i
            if i > max:
                self.rec(result, now+1, i, N)
            else:
                self.rec(result, now+1, max, N)

    def resolve(self):

        count = 0

        N, M = map(int, self.input_data().split())
        node = [list(map(int, self.input_data().split())) for i in range(M)]
        sp = [[0, 200000] for i in range(N+1)]   
        path = [[] for i in range(N+1)]
        for n in node:
            path[n[0]].append(n[1])
            path[n[1]].append(n[0])

        next = [1]
        sp[1][1] = 0
        while len(next) != 0:
            now = next.pop(0)
            for n in path[now]:
                if sp[n][1] > sp[now][1]+1:
                    sp[n][0] = now
                    sp[n][1] = sp[now][1]+1
                    next.append(n)


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

solver = Solver(REL_PATH)
solver.exec_resolve()

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

AB = dict()

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

    AB.setdefault(b, [])
    AB[b].append(a)

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

a[1] = 0
current = 1
pos = [1]

while True:
    next_pos = []

    for p in pos:
        for n in AB[p]:
            if a[n] == -1:
                a[n] = p
                next_pos.append(n)

    pos = next_pos
    if not pos:
        break

if -1 in a[2:]:
    print('No')
else:
    print('Yes')
    for i in a[2:]:
        print(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)



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

d = deque()
d.append(1)

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

    d.append(i)



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

Solution (Python):
from collections import deque
n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
visited = [float('inf') for i in range(n)]
visited[0] = 0
ans = [float('inf') for i in range(n)]
que = deque()
que.append(0)
while que:
    t = que.popleft()
    for j in edge[t]:
        if visited[j] == float('inf'):
            visited[j] = t+1
            que.append(j)
if float('inf') in visited:
    print("No")
    exit()
print("Yes")
for i in range(1,n):
    print(visited[i])

Solution (Python):
from collections import deque


n, m = map(int, input().split())
G = [[] for _ 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(0)

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

pre = [-1] * n

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

if -1 in pre[1:]:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        print(pre[i])

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, prev):
    while queue:
        current = queue.popleft()

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

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

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

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, prev):
    while queue:
        current = queue.popleft()

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

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

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

Solution (Python):
from collections import deque

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

q = deque([0])
used[0] = 1
while q:
    u = q.popleft()
    for v in G[u]:
        if used[v] == 1:
            continue
        q.append(v)
        used[v] = 1
        prev[v] = u + 1

for i in range(n):
    if used[i] != 1:
        print("No")
        exit()

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

Solution (Python):
import sys
from collections import deque


def main():
    input = sys.stdin.readline
    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)
    ans = [0] * (N + 1  )
    ans[1] = 1
    cnt = 1
    q = deque([1])
    while q:
        v = q.popleft()
        for to in G[v]:
            if ans[to] > 0: continue
            ans[to] = v
            q.append(to)
            cnt += 1
    if cnt < N:
        print('No')
        return
    print('Yes')
    for i in range(2, N + 1):
        print(ans[i])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        route[a].append(b)
        route[b].append(a)
    ans = [None]*(n+1)
    q = deque([1])
    while q:
        parent = q.pop()
        children = route[parent]
        for child in children:
            if ans[child] is None:
                ans[child] = parent
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))

if __name__ == "__main__":
    main()

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


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


parent ={i:-1 for i in range(1,N+1)} 
parent[1] =0
children = deque()
children.extend(connection[1])
for i in children:
    parent[i] =1
while children:
    next =children.popleft()

    for i in connection[next]:
        if parent[i] != -1:
            continue
        else:
            parent[i] =next

            children.append(i)

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

Solution (Python):
from collections import deque
N, M = map(int, input().split())
g = [[] for i in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    g[A].append(B)
    g[B].append(A)
Q = deque()
vstd = [0]*(N+1)
mark = [0]*(N+1)
vstd[1] = 1
Q.append(1)
while Q:
    par = Q.popleft()
    for r in g[par]:
        if vstd[r]:
          continue
        mark[r]=par
        vstd[r]=1
        Q.append(r)
print('Yes')
for mk in mark[2:]:
    print(mk)