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 bfs():
    visited=[-1]*n
    q=deque()
    start=1
    visited[start-1]=0
    q.append(start)
    while q:
        now=q.popleft()
        for next in graph[now-1]:
            if visited[next-1]==-1:
                q.append(next)
                visited[next-1]=now
    return visited[1:]

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

graph = [[] for _ in range(n)]
for v in p:
    graph[v[0]-1].append(v[1])
    graph[v[1]-1].append(v[0])  



ans=bfs()
if -1 in ans:
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Solution (Python):
from collections import deque

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

d = deque()
d.append(1)
ans = [-1] * (n+1)
ans[1] = 1
while d:
    f = d.popleft()
    for t in ex[f]:
        if ans[t] == -1:
            ans[t] = f
            d.append(t)

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

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

Solution (Python):
from collections import deque

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

d = deque()
d.append(1)
ans = [-1] * (n+1)
ans[1] = 1
while d:
    f = d.popleft()
    for t in ex[f]:
        if ans[t] == -1:
            ans[t] = f
            d.append(t)

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

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

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    ans = [0]*n
    dist = [-1]*n
    que = deque([0])
    dist[0] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in g[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            ans[w] = v + 1
            que.append(w)
    return ans[1:]

n, m = MAP()
g = [[] for i in range(n)]
for i in range(m):
    A, B =MAP()
    g[A-1].append(B-1)
    g[B-1].append(A-1)

print("Yes")
for x in bfs():
    print(x)

Solution (Python):
from collections import deque

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)
dist=[-1]*(N+1)
dist[0]=0
dist[1]=0
d=deque()
d.append(1)
ans=[0]*(N+1)
while d:
    v=d.popleft()
    for i in graph[v]:
        if dist[i]!=-1:
            continue
        dist[i]=dist[v]+1
        d.append(i)
        if ans[i]!=0:
            continue
        ans[i]+=v
print("Yes")
for i in ans:
    if i==0:
        continue
    print(i)

Solution (Python):
from collections import deque


def nearlist(N, LIST):
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  
    PATH = [-1 for _ in range(N)]
    PATH[S] = 's'
    frag, que = set([S]), deque([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:
                continue
            PATH[i] = q
            que.append(i), frag.add(i)
    return PATH


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

near = nearlist(n, ab)
path = bfs(near, 0, n)

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

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

A = []
B = []

for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

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

for a, b in zip(A, B):
    P[b].append(a)
    P[a].append(b)

ans = [0] * (N + 1)
ans[1] = 1
next_numbers = [1]

while next_numbers:
    check_number = next_numbers[:]
    next_numbers = []
    for number in check_number:
        for x in P[number]:
            if ans[x] == 0:
                ans[x] = number
                next_numbers.append(x)

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

Solution (Python):
N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
prev = [0] * N
to_list = [ [] for _ in range(N)]
for a,b in AB:
 to_list[a - 1].append(b - 1)
 to_list[b - 1].append(a - 1)
marked = {0}
que = [0]
for i in que:
   for j in to_list[i]:
       if j in marked: continue
       que.append(j)
       marked.add(j)
       prev[j] = i+1
print('Yes')
print(*prev[1:], sep='\n')

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

from collections import deque
q = deque()

dis = [-1] * n
ans = [0] * n

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dis[to] != -1:
            continue
        dis[to] = dis[now] + 1
        q.append(to)
        ans[to] = now
print("Yes")
for i in range(1,n):
    print(ans[i] + 1)

Solution (Python):
from collections import deque

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

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

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

while q:
    u = q.popleft()
    for v in l[u]:
        if not s[v]:
            s[v] = u
            q.append(v)
print('Yes')

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

Solution (Python):
n,m=list(map(int,input().split()))
road=[[] for i in range(n)]

for i in range(m):
  a,b=list(map(int,input().split()))
  road[a-1].append(b)
  road[b-1].append(a)
from collections import deque
q=deque([1])
check=[0 for i in range(n)]
check[0]=1
ans=[0 for i in range(n)]
while len(q)>0:
  p=q.popleft()
  for i in range(len(road[p-1])):
    if check[road[p-1][i]-1]==0:
      q.append(road[p-1][i])
      check[road[p-1][i]-1]=1
      ans[road[p-1][i]-1]=p
      
      
print("Yes")
for i in range(1,n):
  print(ans[i])

Solution (Python):
import collections

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

Cost = [[] for l in range(N+1)]
R = [0]*(N+1)


for a, b in AB:
    Cost[a].append(b)
    Cost[b].append(a)




Rcount = 0
Pipod = collections.deque()
Pipod.append(1)
while Rcount != N-1:
    
    p = Pipod.popleft()
    
    for c in Cost[p]:
        if c != 1 and R[c] == 0:
            R[c] = p
            Pipod.append(c)
            Rcount += 1
    if len(Pipod) == 0:
        print('No')
        exit(0)

print('Yes')
for x in R[2:N+1]:
    print(x)

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

g = [[] for _ in range(N)]
sign = [-1 for _ in range(N)]

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

    g[a-1].append(b-1)
    g[b-1].append(a-1)

queue = deque()
queue.append(0)

while len(queue) > 0:

    now = queue.popleft()

    for adj in g[now]:
        if sign[adj] == -1:
            queue.append(adj)
            sign[adj] = now


allVisited = True

for i in range(1, len(sign)):
    if sign[i] == -1:
        allVisited = False

if not allVisited:
    print("No")
    exit()

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

Solution (Python):
N,M=list(map(int,input().split()))
E={i:[] for i in range(1,N+1)}
for i in range(M):
    a,b=list(map(int,input().split()))
    E[a].append(b)
    E[b].append(a)
V={i:0 for i in range(1,N+1)}
W=[1]
while W!=[]:
    S=[]
    for a in W:
        for b in E[a]:
            if V[b]==0:
                V[b]=a
                S.append(b)
    W=S
if -1 in V:
    print('No')
else:
    print('Yes')
    for i in range(2,N+1):
        print(V[i])

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque
from copy import deepcopy
def main():
    n, m = map(int, input().split())
    edges = {e:[] for e in range(n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)

    res = [0] * (n + 1)
    dist = 1
    distroom = [n + 1] * (n + 1)
    distroom[1] = 0
    q1 = deque()
    q2 = deque()
    q1.append(1)
    while q1:
        for q1e in q1:
            for adj in edges[q1e]:
                if distroom[adj] > dist:
                    res[adj] = q1e
                    distroom[adj] = dist
                    q2.append(adj)
        dist += 1
        q1 = deepcopy(q2)
        q2 = deque()
    print('Yes')
    print(*res[2:],sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):
import collections

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

coriddorList = [set() for i in range(n+1)]
deepList = [-1 for i in range(n+1)]


for i in range(m):
    a,b = list(map(int,input().split()))
    coriddorList[a].add(b)
    coriddorList[b].add(a)

checkList = [0] * (n + 1)
ansList = [0] * (n + 1)
checkList[1] = 1
q = collections.deque()
q.appendleft(1)

while len(q) > 0:
    value = q.pop()
    for k in coriddorList[value]:
        if checkList[k] == 0:
            checkList[k] = 1
            ansList[k] = value
            q.appendleft(k)

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

Solution (Python):
from collections import deque

INF = 9999999

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

que = deque([0])
dist = [INF] * N
pre = [0] * N
dist[0] = 0
while que:
    from_v = que.popleft()
    for to_u in to[from_v]:
        if dist[to_u] != INF:
            continue
        dist[to_u] = dist[from_v]+1
        pre[to_u] = from_v
        que.append(to_u)

print('Yes')
for i in range(N):
    if i == 0:
        continue
    print(pre[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())
    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):
print('Yes')

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)


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

d = deque()
d.append(1)

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

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

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

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

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

from collections import deque
q = deque()

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

q.append(0)
while len(q) != 0:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now

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

Solution (Python):
from collections import deque
N, M = map(int, input().split())
road = [[] for _ in range(N+1)]
ans = [-1]*(N+1)
d = deque()
for i in range(M):
    A, B = map(int, input().split())
    road[A].append(B)
    road[B].append(A)
d.append(1)
while len(d) != 0:
    look = d.popleft()
    for i in road[look]:
        if ans[i] == -1:
            d.append(i)
            ans[i] = look

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

Solution (Python):
import sys
from collections import *

N,M=map(int,input().split())
adj=[[] for _ in range(N+1)]
for ln in sys.stdin:
    A,B=map(int,ln.split())
    adj[A].append(B)
    adj[B].append(A)

ans=[0]*(N+1)
ans[1]=1
que=deque([1])
while que:
    A=que.popleft()
    for B in adj[A]:
        if ans[B]==0:
            ans[B]=A
            que.append(B)

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

Solution (Python):
import sys
from collections import *

N,M=map(int,input().split())
adj=defaultdict(list)
for ln in sys.stdin:
    A,B=map(int,ln.split())
    A,B=A-1,B-1
    adj[A].append(B)
    adj[B].append(A)

a={0:0}
que=deque([0])
while que:
    u=que.popleft()
    for v in adj[u]:
        if v not in a:
            a[v]=u
            que.append(v)

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

Solution (Python):
import sys
N,M=map(int,input().split())
adj={}
for ln in sys.stdin:
    A,B=map(int,ln.split())
    if A not in adj: adj[A]=[]
    if B not in adj: adj[B]=[]
    adj[A].append(B)
    adj[B].append(A)

a=[0]*(N+1)
a[1]=-1
que=[1]
while que:
    suc=[]
    for u in que:
        for v in adj[u]:
            if a[v]!=0:
                continue
            a[v]=u
            suc.append(v)
    que=suc





ok=True
ans=[]
for i in range(2,N+1):
    if a[i]==0:
        ok=False
        break
    ans.append(a[i])

if not ok:
    print('No')
else:
    print('Yes')
    for x in ans:
        print(x)

Solution (Python):


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

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

from collections import deque
q=deque([1])
ans=[0 for i in range(n)]
check=[0 for i in range(n)]
check[0]=1
while len(q)>0: 
  p=q.popleft()
  for j in road[p-1]:
    if check[j-1]==0:
      q.append(j)
      check[j-1]=1
      ans[j-1]=p

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

Solution (Python):

from collections import deque

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

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

INF = 10 ** 9 + 7
d = [INF] * (N + 1)
ans = [0] * (N + 1)
q = deque([1])
d[1] = 0
while q:
    u = q.popleft()
    for v in graph[u]:
        if d[v] > d[u] + 1:
            d[v] = d[u] + 1
            ans[v] = u
            q.append(v)

print("Yes")
print(*ans[2:], 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):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

from collections import deque

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

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

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

Solution (Python):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal 
from functools import lru_cache





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

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

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

queue=deque([ [0,i] for i in A[0] ])
now=0
while queue:
    now,to=queue.pop()
    
    if flag[to]==-1:
        flag[to]=now
        for i in A[to]:
            queue.appendleft([to,i])


if -1 in flag:
    print("No");exit()
print("Yes")
for i in range(1,n):
    print(flag[i]+1)

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate 

from collections import deque,defaultdict,Counter
import decimal
import re












import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
q = deque([0])
def pa():
    while q:
        v = q.popleft()
        for nv in G[v]:
            if arrived[nv] < 0:
                arrived[nv] = v + 1
                q.append(nv)
arrived = [-1] * n
pa()
if -1 in arrived[1:]:
    print('No')
else:
    print('Yes')
    print(*arrived[1:],sep='\n')

Solution (Python):
import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()

G.add_edges_from(tuple(map(int, input().split())) for _ in range(M))

dist = nx.shortest_path_length(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(min((dist[j], j) for j in nx.all_neighbors(G, i))[1])

Solution (Python):
from collections import deque

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

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

queue = deque([1])
visited = [-1] * n
parent = [0] * n
now = 1

visited[0]=0

while len(queue) > 0:
    now = queue.popleft()
    for i in aisle[now-1]:
        if visited[i-1]==-1:
            queue.append(i)
            visited[i-1]=visited[now-1]+1
            parent[i-1] = now


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

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



def main():
    N, M = [int(i) for i in input().strip().split()]
    graph = [[] for _ in range(N)]
    sign = [0] * N
    for _ in range(M):
        a, b = [int(i) for i in input().strip().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    candidates = deque([0])
    visited = [False] * N
    visited[0] = True
    while len(candidates) > 0:
        v = candidates.popleft()
        for i in graph[v]:
            if visited[i]:
                continue
            visited[i] = True
            sign[i] = v
            candidates.append(i)
    print("Yes")
    for i in sign[1:]:
        print(i + 1)

    return


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(lambda x: int(x)-1, input().split())
    adj[A].append(B)
    adj[B].append(A)

from collections import deque

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

while queue:
    now = queue.popleft()
    for u in adj[now]:
        if visit[u] < 0:
            queue.append(u)
            visit[u] = visit[now] + 1

print('Yes')
for i in range(1,N):
    for u in adj[i]:
        if visit[u] == visit[i]-1:
            print(u+1)
            break

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,b = a-1, b-1
  g[a].append(b)
  g[b].append(a)
stack = deque([0])
dist = [-1]*n
dist[0] = 0

while stack:
  v = stack.popleft()
  for nv in g[v]:
    if dist[nv] == -1:
      dist[nv] = v+1
      stack.append(nv)

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

Solution (Python):
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,1)]
dist[1] = 0
hist[1] = 1
pre = {1:0}
while heap:
    d,x = heapq.heappop(heap)
    if d>dist[x]:continue
    for y in G[x]:
        if hist[y]==0:
            if dist[y]>d+1:
                dist[y] = d+1
                pre[y] = x
                heapq.heappush(heap,(d+1,y))
flag = 0
for i in range(1,N+1):
    if dist[i]>=INFTY:
        flag = 1
        break
if flag==1:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(pre[i])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

prev = [-1] * N
visited = [0] * N
visited[0] = 1
from collections import deque
q = deque([0])
while q:
    v = q.popleft()
    for to in es[v]:
        if visited[to]: continue
        visited[to] = 1
        prev[to] = v
        q.append(to)

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

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

def bfs():
    q = deque([0])
    pre = [-1]*N
    pre[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if pre[nv]==-1:
                pre[nv] = v
                q.append(nv)
    
    return pre

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)

pre = bfs()
print('Yes')

for pre_i in pre[1:]:
    print(pre_i+1)

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

from collections import deque
q = deque([])
q.append(0)
visit = [-1]*n
visit[0] = 0
while q:
    v = q.popleft()
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = v
            q.append(u)
print('Yes')
for i in range(1, n):
    print(visit[i]+1)

Solution (Python):
import queue

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

ans = [-1 for _ in range(n)]
ans[0] = 0
q = queue.Queue()
q.put(0)
while not q.empty():
    start = q.get()
    for end in maze[start]:
        if ans[end] == -1:
            q.put(end)
            ans[end] = start

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

Solution (Python):
n,m=map(int,input().split())
s=[[]for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    s[a-1].append(b-1)
    s[b-1].append(a-1)
t=[-1]*n
q=[0]
while q:
    p=[]
    for j in q:
        for i in s[j]:
            if i!=j and t[i]==-1:
                p.append(i)
                t[i]=j
    q=p[::]
print("Yes")
for i in t[1:]:
    print(i+1)

Solution (Python):

def main():
    import sys
    from collections import deque

    input = sys.stdin.readline

    N, M = map(int, input().split())
    G = [[] for _ in [0] * (N + 1)]
    for _ in [0] * M:
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    
    q = deque([1])
    depth = [0 for _ in [0] * (N + 1)]
    while q:
        v = q.popleft()
        for nv in G[v]:
            if depth[nv] == 0:
                
                depth[nv] = v
                q.append(nv)
    if 0 in depth[2:]:
        print('No')
        return
    else:
        print('Yes')
        for guide in depth[2:]:
            print(guide)


if __name__ == '__main__':
    main()

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

a = [0] * (m + 1)
b = [0] * (m + 1)
road = [[] for _ in range(n + 1)]

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

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

q = deque()
q.appendleft(1)

while len(q):
    i = q.pop()
    for j in road[i]:
        if ans[j] == -1:
            ans[j] = i
            q.appendleft(j)

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

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

Solution (Python):
import collections

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

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

    while len(q) != 0:
        v = q.popleft()
        for u in g[v]:
            
            if check[u] == 0:
                check[u] = 1
                ans[u] = v
                q.append(u)

    for i in range(2,n+1):
        if ans[i] == 0:
            print('No')
            return

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

main()

Solution (Python):
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=[0]
visited[0]=True

while Q:
  v=Q.pop(0)
  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 defaultdict

G = defaultdict(set)
N, M = [int(_) for _ in input().split()]
for _ in range(M):
    A, B = [int(_) for _ in input().split()]
    G[A].add(B)
    G[B].add(A)

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

pool = set([1])
np = set()
cnt = 0
while pool:
    np = set()
    for p in pool:
        for v in G[p]:
            if f[v] == -1:
                f[v] = p
                cnt += 1
                np.add(v)
    pool = np

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
A=[[] for i in range(n)]
for i in range(m) :
    a,b=map(int,input().split())
    A[b-1].append(a-1)
    A[a-1].append(b-1)
depth=[-1]*n
visit=deque([0])

while True :
    if len(visit)==0 :
        break
    x=visit.popleft()
    for i in A[x] :
        if depth[i]==-1 :
            depth[i]=x+1
            visit.append(i)

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

Solution (Python):
from collections import deque

n, m = map(int, input().split())
root = [[] for _ in range(n)]
adj = [-1 for _ in range(n)]
for _ in range(m):
  r,c = map(int, input().split())
  root[r-1].append(c-1)
  root[c-1].append(r-1)
  
explor = deque()
explor.append(0)

while explor:
  tmp = explor.popleft()
  for i in root[tmp]:
    if adj[i]==-1:
      adj[i] = tmp
      explor.append(i)

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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
l=[[] for i in range(n)]

for a,b in ab:
    l[a-1].append(b)
    l[b-1].append(a)
result=[-1]*n
q=deque([1])

while True:
    if len(q)==0:
        break
    x=q.popleft()
    for j in l[x-1]:
        if result[j-1]==-1:
            result[j-1]=x
            q.append(j)
    

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

Solution (Python):
from collections import deque

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

for i in range(m):
    tmp = list(map(int,input().split()))
    turo[tmp[0]].append(tmp[1])
    turo[tmp[1]].append(tmp[0])

sirusi[1] = 0

q = deque()
q.append(1)

while len(q) != 0:
    x = q.popleft()
    for i in turo[x]:
        if sirusi[i] == -1:
            sirusi[i] = x
            q.append(i)

print('Yes')
for i in range(n+1):
    if i != 0 and i != 1:
        print(sirusi[i])

Solution (Python):
import collections

n,m = map(int,input().split())
g = [[] for i in range(n+1)]
for i in range(m):
  a,b = map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q = collections.deque()
q.append(1)
check = [0]*(n+1)
check[1] = 1
ans = [0]*(n+1)
while len(q)!=0:
  v = q.popleft()
  for j in g[v]:
    if check[j] == 0:
      check[j] = 1
      ans[j] = v
      q.append(j)
print('Yes')
for k in range(2,n+1):
  print(ans[k])

Solution (Python):
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
mark=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  a-=1;b-=1
  g[a].append(b)
  g[b].append(a)
D=deque([0])
visited=[False]*n
visited[0]=True
while D:
  v=D.popleft()
  for i in g[v]:
    if visited[i]:
      continue
    visited[i]=True
    mark[i]=v
    D.append(i)
print("Yes")
for i in range(1,n):
  print(mark[i]+1)