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 queue
import sys
imput = sys.stdin.readline

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

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

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

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

print("Yes")    

for i in par[1:]:
    print(i+1)

Solution (Python):
import copy
N, M = map(int, input().split())
res = [[] for i in range(N+5)]


for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    res[a].append(b)
    res[b].append(a)
    
pre = [-1] * N
dist = [-1] * N
d = 1
dl = []
pre[0] = 0
dist[0] = 0
dl.append(0)

while(len(dl) != 0) :
    a = dl[0]
    dl.pop(0)
    for i in res[a] :
        if(dist[i] != -1):
            continue
        dist[i] = dist[a] + 1
        pre[i] = a
        dl.append(i)
        
for i in range(N) :
    if(i == 0) :
        print("Yes")
        continue
    print(pre[i] + 1)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
k=[0]*(n+1)
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            k[i]=p
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        print(k[i])

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Solution (Python):
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Solution (Python):
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Solution (Python):
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Solution (Python):
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
R=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
    R[a].append(b)
    R[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
    r[p]=[]
if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in R[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Solution (Python):
from collections import deque
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    r[a].append(b)
    r[b].append(a)
dep=[-1]*(n+1)
dep[0]=0
dep[1]=0
data=deque([1])
d=0
while len(data)>0:
    p=data.popleft()
    for i in r[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)

if not all(dep[i+1]>=0 for i in range(n)):
    print("No")
else:
    print("Yes")
    for i in range(2,n+1):
        for j in r[i]:
            if dep[j]==dep[i]-1:
                print(j)
                break

Solution (Python):
import numpy as np
from sys import stdin

def getval():
    n,m = map(int,input().split())
    path = [[] for i in [0]*(n+1)]
    for i in [0]*m:
        a,b = map(int, stdin.readline().split())
        path[a].append(b)
        path[b].append(a)
    return n,m,path

def solve(n,m,p):
    prev = np.zeros((n+1))
    q = [1]
    while q:
        idx = q.pop(0)
        adj = p[idx]
        for i in adj:
            if prev[i]:
                continue
            prev[i] = idx
            q.append(i)
    print("Yes")
    for i in range(2,n+1):
        print(int(prev[i]))

if __name__=="__main__":
    n,m,p = getval()
    
    solve(n,m,p)

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

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

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)

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

Solution (Python):
from collections import deque
n,m = map(int, input().split())
dis = [n+2]*(n)
dis[0] = 0
near = [[] for _ in range(n)]
mark = [-1]*(n)
mark[0] = 0
que = deque()
for _ in range(m):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  near[a].append(b)
  near[b].append(a)
  if a==0:
    que.appendleft(b)
    mark[b] = 0
    dis[b] = 1
  if b==0:
    que.appendleft(a)
    mark[a] = 0
    dis[a] = 1
while que:
  i = que.popleft()
  for j in near[i]:
    if dis[i]+1<dis[j]:
      dis[j] = dis[i]+1
      mark[j] = i
      que.append(j)
if n+2 not in dis:
  print('Yes')
  for i in mark[1:]:
    print(i+1)
else:
  print('No')

Solution (Python):
from collections import deque
n,m = map(int, input().split())
dis = [n+2]*(n)
dis[0] = 0
near = [[] for _ in range(n)]
mark = [-1]*(n)
mark[0] = 0
que = deque()
for _ in range(m):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  near[a].append(b)
  near[b].append(a)
  if a==0:
    que.appendleft(b)
    mark[b] = 0
    dis[b] = 1
  if b==0:
    que.appendleft(a)
    mark[a] = 0
    dis[a] = 1
while que:
  i = que.popleft()
  for j in near[i]:
    if dis[i]+1<dis[j]:
      dis[j] = dis[i]+1
      mark[j] = i
      que.append(j)
if n+2 not in dis:
  print('Yes')
  for i in mark[1:]:
    print(i+1)
else:
  print('No')

Solution (Python):
from collections import deque

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

if len(c[0]) == 0:
    print('No')
    exit()

l = [0]*n
l[0] = 1
q = deque()
for i in c[0]:
    q.append(i)
    l[i] = 1
while q:
    p = q.pop()
    for i in c[p]:
        if l[i] == 0:
            l[i] = p+1
            q.appendleft(i)

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

Solution (Python):
from collections import deque

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

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

  
dist=[-1]*(N+1)
d=deque([1])

while d:
  x = d.popleft()
  for i in range(len(edge[x])):
    if dist[edge[x][i]]==-1:
      dist[edge[x][i]]=x
      d.append(edge[x][i])

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

Solution (Python):
from collections import deque
n,m = map(int,input().split())
load = [list(map(int,input().split())) for _ in range(m)]
goal = [[] for _ in range(n)]
for i in load:
    goal[i[0]-1].append(i[1]-1)
    goal[i[1]-1].append(i[0]-1)

q = deque([0])
ans = [-1 for _ in range(n)]
ans[0] = 0
while q:
    check = q.popleft()
    for j in goal[check]:
        if ans[j] == -1:
            ans[j] = check+1
            q.append(j)
if -1 in ans:
    print("No")
else:
    print("Yes")
    for p in range(1,n):
        print(ans[p])

Solution (Python):
from collections import deque

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

for i in range(M):
    link[L[i][0]-1].append(L[i][1]-1)
    link[L[i][1]-1].append(L[i][0]-1)

checked = [-1 for _ in range(N)]
checked[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(len(link[now])):
        if checked[link[now][i]] == -1:
            checked[link[now][i]] = now + 1
            d.append(link[now][i])


flag = False
for i in range(1, N):
    if checked[i] == -1:
        flag = True
        break

if flag:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(checked[i])

Solution (Python):
from collections import deque

N,M = map(int,input().split())
G = [None] + [[] for i in range(N)]
dist = [None]+[-1]*N
ans = [None]+[10**6]*N

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

deq = deque()

dist[1] = 0
deq.append(1)

while len(deq) != 0:
    v = deq.popleft()
    
    for i in G[v]:
        if dist[i] != -1:
            if dist[v]-dist[i] == 1:
                ans[v] = i
            continue
        dist[i] = dist[v]+1
        deq.append(i)

print("Yes")

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

Solution (Python):





n,m=map(int, input().split())
ab=[[]for _ in range(n)]
for i in range(m):
    a,b = list(map(int, input().split()))
    a,b = a-1, b-1
    ab[a].append(b)
    ab[b].append(a)
    '''
    まず両方を追加する考えがなかった。
    浅い部屋からも深い部屋からも参照できる。
    その代わりに visitedで考えなくて良い部屋を記録している。
    部屋１につながっているのはもっとも浅い部屋でそこから考えることがきっかけになる？
    '''

ans = [0]*n
visited={0}
stack=[0]
for i in stack:
    '''
    現在考えている部屋を stack、そこにつながる部屋 ab[i]として考える。
    stack=[0]なので1の部屋から始める。なので深さ1の部屋が ab[i](ab[0])で分かる。
    i==0の始めの一周では、ab[i]は深さ１の部屋のリストであり、それぞれの部屋を jとして順番に考える。
    (このように深さ1から考えられる＋次に深さ2の部屋を求めるというのが上手くいく)
    その現在考えている部屋 i(stackの循環)とそこにつながる部屋 j(abの循環)なので、
    部屋 jはより浅い部屋 iを道しるべにすればよい。
    しかし、ab[a], ab[b]と両方を追加しているので、浅い部屋も深い部屋も abには含まれている。
    浅い部屋から順に考えているので、過去に調べた abの値は無視するために visitedを導入する。たぶん。
    '''
    for j in ab[i]:
        
        if j in visited:
            continue
        stack.append(j)
        visited.add(j)
        ans[j]=i+1
        
        
        
'''check=0
for i in ans[1:]:
    if i==0:check==1
if check:
    print('No')
else:
    print("Yes")
    print(*ans[1:])'''
print("Yes")
print(*ans[1:])

Solution (Python):





n,m=map(int, input().split())
ab=[[]for _ in range(n)]
for i in range(m):
    a,b = list(map(int, input().split()))
    a,b = a-1, b-1
    ab[a].append(b)
    ab[b].append(a)
    '''
    まず両方を追加する考えがなかった。
    浅い部屋からも深い部屋からも参照できる。
    その代わりに visitedで考えなくて良い部屋を記録している。
    部屋１につながっているのはもっとも浅い部屋でそこから考えることがきっかけになる？
    '''

ans = [0]*n
visited={0}
stack=[0]
for i in stack:
    '''
    現在考えている部屋を stack、そこにつながる部屋 ab[i]として考える。
    stack=[0]なので1の部屋から始める。なので深さ1の部屋が ab[i](ab[0])で分かる。
    i==0の始めの一周では、ab[i]は深さ１の部屋のリストであり、それぞれの部屋を jとして順番に考える。
    (このように深さ1から考えられる＋次に深さ2の部屋を求めるというのが上手くいく)
    その現在考えている部屋 i(stackの循環)とそこにつながる部屋 j(abの循環)なので、
    部屋 jはより浅い部屋 iを道しるべにすればよい。
    しかし、ab[a], ab[b]と両方を追加しているので、浅い部屋も深い部屋も abには含まれている。
    浅い部屋から順に考えているので、過去に調べた abの値は無視するために visitedを導入する。たぶん。
    '''
    for j in ab[i]:
        
        if j in visited:
            continue
        stack.append(j)
        visited.add(j)
        ans[j]=i+1
        
        
        
check=0
for i in ans[1:]:
    if i==0:check==1
if check:
    print('No')
else:
    print("Yes")
    print(*ans[1:])

Solution (Python):
from collections import deque
N, M = list(map(int, input().split()))
S = [set() for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    S[a].add(b)
    S[b].add(a)


parents = [-1]*N
parents[0] = 0
L = deque([0])
while L:
    k = L.pop()
    s=S[k]
    for l in s:
        if parents[l] < 0:
            L.appendleft(l)
            parents[l] = k
    

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

Solution (Python):
def resolve():
    N, M = list(map(int, input().split()))
    AB = {}
    for _ in range(M):
        a, b = list(map(int, input().split()))
        a, b = a-1, b-1
        if a not in AB:
            AB[a] = []
        if b not in AB:
            AB[b] = []
        AB[a].append(b)
        AB[b].append(a)

    import collections
    q = collections.deque([0])
    passed = [-1 for i in range(N)]
    passed[0] = 0
    while q:
        node = q.pop()
        for nxt in AB[node]:
            if passed[nxt] == -1:
                passed[nxt] = node
                q.appendleft(nxt)
    
    for m in passed:
        if m == -1:
            print("No")
            return
    print("Yes")
    for i in range(1, N):
        print(passed[i]+1)


if '__main__' == __name__:
    resolve()

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

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

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

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

Solution (Python):

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

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

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

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

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

graph = [[] for _ in range(N)]
flag = [0] * N

for i in range(M):
  A, B = map(int,input().split())
  A -= 1
  B -= 1
  graph[A].append(B)
  graph[B].append(A)
  
D = deque()
D.append(0)
visited = [False] * N
visited[0] = True

while D:
  v = D.popleft()
  for nv in graph[v]:
    if visited[nv] == True:
      continue
    visited[nv] = True
    flag[nv] = v
    D.append(nv)
    
print("Yes")
for i in range(1,N):
  print(flag[i] + 1)

Solution (Python):
from collections import deque

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

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

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

que = deque()
que.append(1)

while que:
    v = que.popleft()

    for i in connection[v]:
        if dist[i] != -1:continue

        dist[i] = dist[v] + 1
        que.append(i)
        ans[i] = v


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

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

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

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

que = []
que.append(1)

while que:
    v = que.pop(0)

    for i in connection[v]:
        if dist[i] != -1:continue

        dist[i] = dist[v] + 1
        que.append(i)
        ans[i] = v


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

Solution (Python):
from collections import deque
n,m=map(int,input().split())
print('Yes')
root=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
q=deque([0])
check=[0]*n
while q:
    e=q.popleft()
    for i in root[e]:
        if check[i]:
            continue
        check[i]=e+1
        q.append(i)
for i in range(1,n):
    print(check[i])

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

print("Yes")
g = [[] for i 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)
q = deque([])
q.append(0)
check = [0] * n
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    if check[i] > 0:
      continue
    check[i] = e + 1
    q.append(i)
for i in range(1,n):
  print(check[i])

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

print("Yes")
g = [[] for i 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)
q = deque([])
q.append(0)
check = [0] * n
while len(q) > 0:
  e = q.popleft()
  for i in g[e]:
    if check[i] > 0:
      continue
    check[i] = e + 1
    q.append(i)
for i in range(1,n):
  print(check[i])

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

graph = [[] for _ in range(N)]
flag = [0] * N

for i in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  graph[A].append(B)
  graph[B].append(A)
  
D = deque([0])
visited = [False] * N
visited[0] = True

while D:
  v = D.popleft()
  for i in graph[v]:
    if visited[i]:
      continue
    visited[i] = True
    flag[i] = v
    D.append(i)
    
print("Yes")
for i in range(1, N):
  print(flag[i] + 1)

Solution (Python):

import sys
from itertools import chain






YES = "Yes"  


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    routes = [set() for _ in range(N)]
    marks = [None for _ in range(N)]
    for a, b in zip(A, B):
        a = a - 1
        b = b - 1
        routes[a].add(b)
        routes[b].add(a)

    marks[0] = -1
    cur_rooms = [0]
    count = 1
    while count < N:
        new_cur_rooms = []
        for cur_room in cur_rooms:
            next_rooms = list(routes[cur_room])
            for next_room in next_rooms:
                if marks[next_room] is None:
                    marks[next_room] = cur_room
                    new_cur_rooms.append(next_room)
                    count += 1
        cur_rooms = new_cur_rooms

    answer = "Yes\n" + "\n".join((str(n + 1) for n in marks[1:]))

    return answer


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    
    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))
    answer = solve(N, M, A, B)
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
edge=[[] for _ 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)
dist=[-1]*n
d=deque()
d.append(0)
now=0
while d:
    x=d.popleft()
    for i in range(len(edge[x])):
        if dist[edge[x][i]]==-1:
            dist[edge[x][i]]=x+1
            d.append(edge[x][i])
print("Yes")
for i in range(n-1):
    print(dist[i+1])

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

for _ in range(m):
    tempa,tempb=map(int,input().split())
    tempa-=1
    tempb-=1
    l[tempa].append(tempb)
    l[tempb].append(tempa)
que=queue.Queue()
dist=[-1]*n

dist[0]=0
que.put(0)
ans=[0]*n

while not que.empty():
    v=que.get()

    for nv in l[v]:
        if dist[nv]!=-1:
            continue
        dist[nv]=dist[v]+1
        que.put(nv)
        ans[nv]=v
if -1 in dist:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i]+1)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
haba=[[] for i in range(N+1)]
for i in range(M):
    A,B=map(int,input().split())
    haba[A].append(B)
    haba[B].append(A)
kyori=[-1]*(N+1)
kyori[0]=0
kyori[1]=0

que=deque()
que.append(1)

while que:
    kari=que.popleft()
    for i in haba[kari]:
        if kyori[i]!=-1:
            continue
        kyori[i]=kari
        que.append(i)

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

Solution (Python):
import keyword
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 - 1)
    G[b - 1].append(a - 1)

visited = [False] * N
par = [0] * N
visited[0] = True
d = deque(G[0])
for i in G[0]:
    visited[i] = True
    par[i] = 0
cur = 0
while d:
    cur = d.popleft()
    for i in G[cur]:
        if not visited[i]:
            visited[i] = True
            par[i] = cur
            d.append(i)

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

Solution (Python):
from collections import deque
infty = 10 ** 9

def BFS(graph, parent, u):
    queue = deque()
    queue.append(u)
    visited = [False for k in range(len(parent))] 
    visited[u] = True
    while queue:
        v = queue.popleft()
        for j in graph[v]:
            if not visited[j]:
                queue.append(j)
                visited[j] = True
                parent[j] = v

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)
parent = [-1 for i in range(n)]
BFS(graph, parent, 0)
if -1 in parent[1:]:
    print("No")
else:
    print("Yes")
    for p in parent[1:]:
        print(p+1)

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

d=deque([1])
visited=[0 for _ in range(N)]
visited[0]=1
cnt=1
while d:
    tmp=d.popleft()
    for e in dp[tmp-1]:
        if visited[e-1]==0:
            visited[e-1]=tmp
            cnt+=1
            d.append(e)
            
if cnt!=len(visited):
    print("No")
else:
    print("Yes")
    for n in range(1,N):
        print(visited[n])

Solution (Python):


import sys
sys.setrecursionlimit(500*500)

from collections import deque




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















































tree = [[] for _ in range(N + 1)]
edges = [list(map(int,input().split())) for _ in range(M)]

for edge in edges:
    tree[edge[0]].append(edge[1])
    tree[edge[1]].append(edge[0])

depth = [-1] * (N + 1)
depth[1] = 0

d = deque()
d.append(1)

ans = [0] * (N + 1)
while d:
 v = d.popleft()
 for i in tree[v]:
   if depth[i] != -1:
     continue
   depth[i] = depth[v] + 1
   ans[i] = v
   d.append(i)


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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
INF = 1000000
to_room = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    to_room[a].append(b)
    to_room[b].append(a)
dp = [INF] * (n + 1)
dp[1] = 0
seen_room = deque()
seen_room.append(1)
ans = [0] * (n + 1)
while seen_room:
    v = seen_room.popleft()
    for next in to_room[v]:
        if dp[next] <= dp[v] + 1:
            continue
        dp[next] = dp[v] + 1
        ans[next] = v
        seen_room.append(next)



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

Solution (Python):
from collections import deque
N, M = map(int, input().split())
B = [[] for i in range(N)]
C = [0 for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  B[a-1].append(b)
  B[b-1].append(a)
d = deque([1])
while len(d):
  p = d.pop()
  for q in B[p-1]:
    if C[q-1] == 0:
      C[q-1] = p
      d.appendleft(q)
print("Yes")
for i in range(1, N):
  print(C[i])

Solution (Python):

import sys
from collections import deque

YES = "Yes"  


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    dq = deque([])
    traversed = [False for _ in range(N+1)]
    ans = [None for _ in range(N+1)]

    G = {n : set([]) for n in range(1, N+1)}
    for a, b in zip(A,B):
        G[a].add(b)
        G[b].add(a)

    dq.append(1)
    traversed[1] = True

    while dq:
        s = dq.popleft()

        for node in G[s]:
            if not traversed[node]:
                dq.append(node)
                traversed[node] = True
                

                ans[node] = s

    print(YES)
    for s in ans:
        if s != None:
            print(s)
    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

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

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

for i in range(M):
    A, B = [int(x) for x in input().split()]
    conn[A].append(B)
    conn[B].append(A)

q = deque([1])
signpost = [0] * (N + 1)

while q:
    v = q.popleft()
    for w in conn[v]:
        if signpost[w] == 0:
            signpost[w] = v
            q.append(w)

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

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

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

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

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

def BFS():
    q = deque()
    q.append(1)
    pre = [0] * (N+1)
    pre[0] = pre[1] = -1
    while(q):
        x = q.popleft()
        for y in A[x]:
            if pre[y] == 0:
                pre[y] = x 
                q.append(y)
    if 0 in pre:
        print('No')
    else:
        print('Yes')
        for i in range(2,N+1):
            print(pre[i])

BFS()

Solution (Python):
def abc168d_double_dots():
    n, m = map(int, input().split())
    path_dict = {}
    for _ in range(m):
        a, b = map(int, input().split())
        if b not in path_dict.keys():
            path_dict[b] = [a]
        else:
            path_dict[b].append(a)
        a, b = b, a
        if b not in path_dict.keys():
            path_dict[b] = [a]
        else:
            path_dict[b].append(a)

    q = [1]
    cnt = 0
    ans = [0] * n
    ans[0] = 1
    while len(q) != 0:
        no = q.pop(0)
        for next_room in path_dict[no]:
            if ans[next_room - 1] == 0:
                ans[next_room - 1] = no
                q.append(next_room)
                cnt += 1

    if cnt != n-1:
        print('No')
        return
    print('Yes')
    for a in ans[1:]:
        print(a)


abc168d_double_dots()