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 defaultdict, deque


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

    route = defaultdict(list)
    for ab in AB:
        route[ab[0]].append(ab[1])
        route[ab[1]].append(ab[0])

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

    while(len(que) != 0):
        v = que.popleft()

        for nv in route[v]:
            if ans[nv-1] != -1:
                continue

            ans[nv-1] = v
            que.append(nv)

    if -1 in ans:
        print('No')
        exit()

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


if __name__ == "__main__":
    main()

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


dist = [False]*N 
que = deque()


dist[0] = True
que.append(0) 
ans = [0]*N


while len(que)!=0:
    v = que.popleft() 

    
    for nv in G[v]:
        
        if dist[nv]:
            continue 

        
        dist[nv] = True
        ans[nv] = v 
        que.append(nv)

    
if any(dist):
    print("Yes")
    for v in range(1,N):
        print(ans[v]+1)
else:
    print("No")

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

ab = []
room = [set() for _ in range(n)]
root_help = [-1 for _ in range(n)]
for i in range(m):
    tmp=list(map(int,input().split()))
    tmp.sort()
    room[tmp[0]-1].add(tmp[1]-1)
    room[tmp[1]-1].add(tmp[0]-1)
    ab.append(tmp)

ab.sort(key=lambda x:x[0])

posi=[0]
next = [1]
already = {0}
while posi:
    tmp_posi=[]
    for p in posi:
        connect = room[p]
        for i in connect:
            if i not in already:
                root_help[i]=p
                already.add(i)
                tmp_posi.append(i)
    posi=tmp_posi

answer = [i + 1 for i in root_help[1::]]
if 0 in answer:
    print('No')
else:
    print('Yes')
    for i in answer:
        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)
T = [-1]*N
T[0] = 0
tlist = [0]
t_change = True
while t_change:
  t_change = False
  tlist2 = []
  for t in tlist:
    for i in AB[t]:
      if T[i]==-1:
        t_change = True
        T[i] = t
        tlist2.append(i)
  tlist = tlist2
  
if -1 in T:
  print('No')
else:
  print('Yes')
  for i in range(1,N):
    print(T[i]+1)

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

from collections import deque
que = deque()
que.append(0)
seen = [-1] * n
seen[0] = 0
while len(que) > 0:
    i = que.popleft()
    for gi in G[i]:
        if seen[gi] != -1:
            continue
        seen[gi] = i
        que.append(gi)
print('Yes')
for i in range(1, n):
    print(seen[i] + 1)

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

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

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,m = MI()
ab = LI(m)

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)


ls_ans = [-1]*n

q = deque()
q.append(0)

while q:
    t = q.popleft()
    ls = g[t]
    for i in ls:
        if ls_ans[i]==-1:
            ls_ans[i] = t
            q.append(i)
        else:
            pass


if -1 in ls_ans:
    print("No")
else:
    for i in range(n):
        if i==0:
            print("Yes")
        else:
            print( ls_ans[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)

que = deque([0])
seen = [-1] * n
seen[0] = 0

while len(que) > 0:
    now_v = que.popleft()
    now_board = seen[now_v]
    next_vs = G[now_v]
    for next_v in next_vs:
        if seen[next_v] == -1:
            seen[next_v] = now_v
            que.append(next_v)

print('Yes')
for x in seen[1:]:
    print(x + 1)

Solution (Python):
n,m=map(int,input().split())
path=[[] for i in range(n+1)]
anser=[0 for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  path[a].append(b)
  path[b].append(a)
nowlis=[1]
nowdone=1
anser[1]=1
while nowdone<n:
  now=nowlis.pop(0)
  done=path[now]
  
  for i in done:
    if anser[i]==0:
      anser[i]=now
      nowlis.append(i)
      nowdone+=1
  
kad=anser.pop(0)
kadd=anser.pop(0)
print("Yes")
for i in anser:
  print(i)

Solution (Python):
from _collections import deque
n,m=map(int,input().split())
X=[[] for _ in range(n)]
visited=[0]*(n+1)
ANS=[0]*n
ANS[0]=1
for i in range(m):
    a,b=map(int,input().split())
    X[a-1].append(b-1)
    X[b-1].append(a-1)

q=deque([0])
visited[0]=1
while len(q)>0:
    s=q.popleft()
    for x in X[s]:
        if visited[x]:
            continue
        q.append(x)
        ANS[x]=s
        visited[x]=1
print('Yes')
for ans in ANS[1:]:
    print(ans+1)

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor, gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    
    N,M = LMIIS()
    edge = defaultdict(list)
    for i in range(M):
        a,b = LMIIS()
        edge[a].append(b)
        edge[b].append(a)

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


    
    
    roots = deque()
    roots.append(1)
    visited = [INF]*(N+1)
    visited[1] = 0
    lights = [0]*(N+1)
    while len(roots) > 0:
        root = roots.popleft()
        length = visited[root]
        for v in edge[root]:
            if length + 1 < visited[v]:
                visited[v] = length + 1
                lights[v] = root
                roots.append(v)
    print('Yes')
    for i in range(2,N+1):
        print(lights[i])





main()

Solution (Python):
import queue
import sys

input = sys.stdin.readline

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

parent = [-1] * (N)
parent[0] = 0

found = [False] * N
found[0] = True

depth = [10 ** 9] * N
depth[0] = 0

q = queue.Queue()
q.put(0)
while not q.empty():
    pos = q.get()
    possible_parent = []
    for next_room in path[pos]:
        if parent[next_room] == -1:
            if not found[next_room]:
                q.put(next_room)
                found[next_room] = True
                depth[next_room] = min(depth[next_room], depth[pos] + 1)
        else:
            possible_parent.append(next_room)

    for p1 in possible_parent:
        for p2 in possible_parent:
            if depth[p1] > depth[p2]:
                break
        else:
            parent[pos] = p1
            break

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

Solution (Python):
from collections import defaultdict
from collections import deque

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

Graph=defaultdict(list)

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

ans=[0]*(N+1)
q=deque()
q.append(1)

while(q):
  start=q.popleft()
  startans=ans[start]
  for a in Graph[start]:
    if ans[a]>0 or a==1:
      continue
    else:
      ans[a]=start
      q.append(a)
  

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

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

from collections import deque

Q = deque([0])
ans[0] = -2

while Q:
    v = Q.popleft()
    for s in to[v]:
        if ans[s] == -1:
            ans[s] = v
            Q.append(s)
print("Yes")
print(*(a + 1 for a in ans[1:]), sep="\n")

Solution (Python):
from collections import deque
N, M = [int(_) for _ in input().split()]
G = [[] for i in range(N+1)]
for i in range(M):
    A, B = [int(_) for _ in input().split()]
    G[A].append(B)
    G[B].append(A)

visited = [False for i in range(N+1)]
mark = [0 for i in range(N+1)]
q = deque([1])
while len(q) != 0:
    p = q.popleft()
    for g in G[p]:
        if not visited[g]:
            q.append(g)
            mark[g] = p
            visited[g] = True

cnt_visited = len([v for v in visited if v])
if cnt_visited != N:
    print('No')
else:
    print('Yes')
    for i in range(2, N+1):
        print(mark[i])

Solution (Python):
import sys
input=sys.stdin.readline
f=lambda:map(int,input().split())
n,m=f()
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
d=[-1]*n
from collections import deque
q=deque([0])
d[0]=0
while q:
  p=q.popleft()
  for c in g[p]:
    if d[c]<0:
      d[c]=p
      q.append(c)
if -1 in d: print('No')
else:
  print('Yes')
  for i in range(1,n): print(d[i]+1)

Solution (Python):
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input=sys.stdin.readline
    n,m=L()
    dic={}
    michi=[1e+7]*(n-1)
    for i in range(m):
        ai,bi=L()
        if ai not in dic:
            dic[ai]=[]
        if bi not in dic:
            dic[bi]=[]
        dic[ai].append(bi)
        dic[bi].append(ai)
    from collections import deque
    d=deque()
    for i in dic[1]:
        michi[i-2]=1
        d.append(i)
    while len(d)!=0:
        i=d.popleft()
        
        
        
        for j in dic[i]:
            
            if j==1:
                continue
            if michi[j-2]==1e+7:
                michi[j-2]=i
                d.append(j)
        
        
    for i in michi:
        if i>=1e+7:
            print('No')
            exit()
    print('Yes')
    for i in michi:
        print(i)
    
        
if __name__ == '__main__':
    main()

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

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

from collections import deque
checked = [-1]*N
dirc = [-1]*N
def bfs(v):
    queue = deque()
    queue.appendleft((v, 0))
    while queue:
        v, p = queue.pop()
        if checked[v]==1:
            continue
        dirc[v] = p
        checked[v] = 1
        for i in rooms[v]:
            if checked[i]==-1:
                queue.appendleft((i, v))

bfs(0)
if -1 in dirc:
    print('No')
else:
    print('Yes')
    for d in dirc[1:]:
        print(d+1)

Solution (Python):
import sys

input = sys.stdin.readline
from collections import *


def bfs():
    q = deque([1])
    dist = [0] * (N + 1)
    while q:
        v = q.popleft()

        for nv in G[v]:
            if dist[nv] == 0:
                dist[nv] = v
                q.append(nv)

    return dist


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)

dist = bfs()

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

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


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

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


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

near = [[] for _ in range(n)]
for a, b in ab:
    near[a - 1].append(b - 1)
    near[b - 1].append(a - 1)
pas = bfs(near, 0, n)

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

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

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

while q:
    now =  q.popleft()
    for nxt in g[now]:
        if ans[nxt] == -1:
            ans[nxt] = now
            q.append(nxt)
print('Yes')
for i in range(1,N):
    print(ans[i]+1)

Solution (Python):
from collections import deque

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

pathes = {i: set() for i in range(1, n + 1)}
for _ in range(m):
  ai, bi = map(int, input().split()) 
  pathes[ai].add(bi)
  pathes[bi].add(ai)

queue = deque()
queue.append(1)

ans = [None] * n 

for _ in range(n):
  if len(queue) == 0:
    break;
  i = queue.popleft()
  next_room = pathes[i]
  for j in next_room:
    if ans[j-1] == None:
      ans[j-1] = str(i)
      queue.append(j)

ans[0] = "Yes"

print("\n".join(ans))

Solution (Python):
from collections import deque

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)

visit = [-1]*N
visit[0] = 0
q = deque()
q.append([0, 0])
while len(q) > 0:
    v, c = q.popleft()
    for u in ab[v]:
        if visit[u] < 0:
            visit[u] = v
            q.append([u, v])

ok = True
for i in range(1, N):
    if visit[i] < 0:
        ok = False

if ok:
    print("Yes")
    for i in range(1, N):
        print(visit[i]+1)
else:
    print("No")

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))

from collections import deque
def resolve():
    N,M=pin()
    edge=dict()
    for i in range(M):
        a,b=pin()
        
        edge.setdefault(a,[])
        edge.setdefault(b,[])
        edge[a].append(b)
        edge[b].append(a)
    
    milestones=[0]*(N+1)
    milestones[1]=1
    c=deque([1])
    
    while(1):
        if len(c)==0:
            break
        t=c.popleft()
        
        for to in edge[t]:
            
            if milestones[to]==0:
                milestones[to]=t
                c.append(to)
        
        
        
    print("Yes")
    print(*milestones[2:],sep="\n")
        

resolve()

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

q=deque([])

edge=[set([]) for _ in range(n+1)]
mark=[-1 for _ in range(n+1)]
used=[False for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].add(b)
    edge[b].add(a)

q.append(1)
mark[1]=1
used[1]=True
while(len(q)>0):
    vi=q.popleft()
    ei=edge[vi]
    for eij in ei:
        if(used[eij]):
            continue
        else:
            mark[eij]=vi
            used[eij]=True
            q.append(eij)

print('Yes')
for i in range(2,len(mark)):
    print(mark[i])

Solution (Python):
import queue
n,m=map(int,input().split())
a=[[] for i in range(n)]
for i in range(m):
    b,c=map(int,input().split())
    if c!=1:
        a[b-1].append(c)
    if b!=1:
        a[c-1].append(b)
d=[0 for i in range(n)]
qu=queue.Queue()
qu.put(1)
while qu.empty()==False:
    qu1=qu.get()
    for i in range(len(a[qu1-1])):
        if d[a[qu1-1][i]-1]==0:
            d[a[qu1-1][i]-1]=qu1
            qu.put(a[qu1-1][i])
for i in range(1,n):
    if d[i]==0:
        print("No")
        break
else:
    print("Yes")
    for i in range(1,n):
        print(d[i])

Solution (Python):
def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(N + 1):
        AB.append([])
    for _ in range(M):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)
    result = [0] * (N + 1)
    from collections import deque
    work = deque([])
    append = work.append
    pop = work.popleft
    append(1)
    while len(work) > 0:
        now = pop()
        for to in AB[now]:
            if result[to] == 0:
                result[to] = now
                append(to)
    for i in result[2:]:
        if i == 0:
            print("No")
            return
    print("Yes")
    for i in result[2:]:
        print(i)
main()

Solution (Python):
from collections import deque


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

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

dist = [-1] * n
prev = [-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
        que.append(w)
        prev[w] = v

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

Solution (Python):
from collections import deque
n, m = list(map(int, input().split()))
al = [0] * n
bl = [0] * n
G = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
N = n



dist = [-1]*N
tag = [-1]*N
que = deque([0])
dist[0] = 0
pre = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        tag[w] = v + 1
        que.append(w)

print('Yes')
for t in tag[1:]:
    print(t)

Solution (Python):
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def dijkstra(path, N, start):
    visited = [False] * N
    mark = [-1] * N  
    que = [(0, start, -1)]  
    heapify(que)  
    dist = [-1] * N  
    dist[start] = 0  
    while que:
        d, v, pre = heappop(que)  
        visited[v] = True  
        if v > 0:
            if mark[v] != -1 and mark[v] != pre:
                return 'No'
            mark[v] = pre
        
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to, v))

    return mark

def main():
    N, M = map(int, readline().rstrip().split())
    path = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().rstrip().split())
        path[a-1].append((1, b-1))
        path[b-1].append((1, a-1))
    
    start = 0
    mark = dijkstra(path, N, start)
    if mark == 'No':
        print('No')
        return

    print('Yes')
    for v in range(1, N):
        print(mark[v] + 1)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

YES = "Yes"  


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    visited = set()
    visited.add(1)
    res = [0 for _ in range(N+1)]
    To = {}
    for a, b in zip(A, B):
        if a in To:
            To[a].add(b)
        else:
            To[a] = set()
            To[a].add(b)
        if b in To:
            To[b].add(a)
        else:
            To[b] = set()
            To[b].add(a)
    crt = set()
    crt.add(1)
    crt2 = set()
    while(len(visited) < N):
        for i in crt:
            for j in To[i]:
                if j not in visited:
                    res[j] = i
                    visited.add(j)
                    crt2.add(j)
        crt = set(crt2)
        crt2.clear()

    print(YES)
    for i in range(2, N+1):
        print(res[i])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline


def main():
    N, M = [int(v) for v in input().split()]

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

    arrow = [-1] * N

    def search():
        q = deque()
        q.append(0)

        closed = 1

        while q:
            e = q.popleft()
            for n in net[e]:
                if closed & (1 << n) == 0:
                    q.append(n)
                    arrow[n] = e
                    closed |= (1 << n)

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

    search()


main()

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline

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

ans = [0]*(n+1)

stk = deque([1])

while stk:
    v = stk.pop()
    for s in G[v]:
        if ans[s] == 0:
            ans[s] = v
            stk.appendleft(s)
ans = ans[2:]

if 0 in ans:
    print("No")
else:
    print("Yes")
    for i in ans:
        print(i)

Solution (Python):


from collections import deque

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

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

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


check_list = [0 for _ in range(n)]
d = deque([(0, -1)])
ans = [0 for _ in range(n)]
while(len(d) >= 1):
    
    index, origin = d.popleft()
    if check_list[index] == 1:
        continue
    else:
        check_list[index] = 1
        ans[index] = origin
    road_list = road_map[index]

    for i in road_list:
        if check_list[i] == 0:
            
            d.append((i, index))


for i in range(1, len(ans)):
    if ans[i] == -1:
        print("No")
        exit()

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

Solution (Python):
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

def main():
    N, M = map(int, input().split())
    to = [[] for _ in range(N)]

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

    def bfs(s):
        q = deque()
        q.append(s)
        visited[s] = True
        par[s] = s

        while q:
            now = q.popleft()
            for nv in to[now]:
                if visited[nv]: continue
                else:
                    visited[nv] = True
                    par[nv] = now+1
                    q.append(nv)
    bfs(0)

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

    

if __name__ == "__main__":
    main()

Solution (Python):
"""
N rooms and M passages
"""

import sys

input = sys.stdin.readline

from collections import deque

def solve(n, m, g):
    visited = [0] * (n+1)
    prev = [0] * (n+1)

    deq = deque([0])
    visited[0] = 1
    visited_count = 1

    while deq:
        node = deq.popleft()

        for nb in g[node]:
            if not visited[nb]:
                visited[nb] = 1
                deq.append(nb)
                visited_count += 1
                prev[nb] = node + 1
    
    if visited_count == n:
        print("Yes")
        for node in range(1, n):
            print(prev[node])
    else:
        print("No")
            


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

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

solve(n, m, g)

Solution (Python):
from collections import deque

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

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

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

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

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

if -1 in ans:
  print('No')
  exit()

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

Solution (Python):
import sys


from math import sqrt, sin, cos, pi
from collections import defaultdict as dd, deque, Counter as C








mod = pow(10, 9) + 7
mod2 = 998244353


def data(): return sys.stdin.readline().strip()


def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)


def l(): return list(sp())


def sl(): return list(ssp())


def sp(): return map(int, data().split())


def ssp(): return map(str, data().split())


def l1d(n, val=0): return [val for i in range(n)]


def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


inf = 10 ** 20
n, m = sp()
graph = dd(set)
for i in range(m):
    u, v = sp()
    graph[u].add(v)
    graph[v].add(u)
dist = dd(lambda: inf)
dist[1] = 0
answer = dd(int)
vis = dd(lambda: False)
vis[1] = True
stack = deque()
stack.append(1)
while stack:
    temp = stack.popleft()
    for child in graph[temp]:
        if not vis[child]:
            stack.append(child)
            vis[child] = True
        if dist[child] > dist[temp] + 1:
            dist[child] = dist[temp] + 1
            answer[child] = temp
for i in range(1, n+1):
    if not vis[i]:
        out("No")
        exit()
out("Yes")
for i in range(2, n+1):
    out(answer[i])

Solution (Python):
import heapq
n,m = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(m)]

es = [[] for i in range(n)]
for x,y in src:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

INF = float('inf')
ds = [INF] * n
ans = [-1]*(n)

def dijkstra(start, dists):
    dists[start] = 0
    hq = [(0,start)]
    heapq.heapify(hq)
    while hq:
        dist,v = heapq.heappop(hq)
        for to in es[v]:
            if dist+1 >= dists[to]: continue
            dists[to] = dist+1
            ans[to]=v+1
            heapq.heappush(hq, (dist+1,to))

dijkstra(0,ds)

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

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

n, m = map(int, input().split())
a = [[] for _ in range(n + 1)]
chk = [0] * (n + 1)
chkchk = [1] * (n + 1)
chkchk[0] = 0

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

q = deque()

for x in a[1]:
    q.append(x)
    chk[x] = 1
    chkchk[x] = 0

while True:
    if len(q) == 0:
        break

    now = q.popleft()

    for x in a[now]:
        if chkchk[x] == 0:
            continue

        q.append(x)
        chk[x] = now
        chkchk[x] = 0

if sum(chkchk) == 0:
    print("Yes")
    for x in chk[2:]:
        print(x)
else:
    print("No")

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

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

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

from collections import deque

que = deque([1])

ans = [-1 for i in range(N+1)]
dist = [0 for i in range(N+1)]
ans[1] = 0
dist[1] = 0

while que:
    now = que.popleft()
    for v in node[now]:
        if ans[v] == -1:
            ans[v] = now
            dist[v] = dist[now] + 1
            que.append(v)
print('Yes')
print('\n'.join(map(str,ans[2:])))