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

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

graph = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

dist = [0] * (N + 1)
queue = [1]

while len(queue)>0:
    now = queue.pop(0)
    for v in graph[now]:
        if dist[v] == 0:
            queue.append(v)
            dist[v] = now


print("Yes")
for k in dist[2:]:
    print(k)

Solution (Python):
from collections import defaultdict
import queue

def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    
    q = queue.Queue()
    F = [-1]*N 
    s = 1 
    while True:
        for v in vum[s]:
            if F[v-1] < 0:
                q.put(v)
                F[v-1] = s
        if q.empty():
            break
        s = q.get()

    if -1 in F[1:]:
        print('No')
    else:
        print('Yes')
        for f in F[1:]:
            print(f)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

n,m = map(int, input().split())
dic = {}

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

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

for a,b in AB:
    a -= 1
    b -= 1

    dic[a].append(b)
    dic[b].append(a)


queue = deque([0])
visited = []
pre = [-1] * (n+1)


queue.append(0)

while queue:
    v = queue.popleft()
    
    for i in dic[v]:
        if pre[i] == -1:
        
            pre[i]= v
            queue.append(i)

print("Yes")
for i in range(n):
    ans = 0
    
    if(i == 0):
        continue
    
    ans = pre[i]
    ans += 1
    print(ans)

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

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

dist = [-1] * n
prev_node = [-1] * n
dist[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for v_next in graph[v]:
        if dist[v_next] == -1:
            dist[v_next] = dist[v] + 1
            prev_node[v_next] = v
            q.append(v_next)




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

Solution (Python):
n,m=map(int,input().split())
w={}
for i in range(m):
    a,b=map(int,input().split())
    if a in w: w[a].add(b)
    else: w[a]=set([b])
    if b in w: w[b].add(a)
    else: w[b]=set([a])

d=[-1]*(n+1)
p=set([1])
q=set([])
d[1]=0
f=1
while 1:
    if f%2:
        for i in p:
            for j in w[i]:
                if d[j]==-1 or f<d[j]:
                    d[j]=f
                    q.add(j)
        p=set([])
        if len(q)==0: break
    else:
        for i in q:
            for j in w[i]:
                if d[j]==-1:
                    d[j]=f
                    p.add(j)
        q=set([])
        if len(p)==0: break
    f+=1

print("Yes")
for i in range(2,n+1):
    for j in w[i]:
        if d[j]+1==d[i]:
            print(j)
            break

Solution (Python):
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)
from collections import deque

queue = deque([1])
d = [None]*(N+1)
d[1]=None
while queue:
    now = queue.popleft()
    for i in g[now]:
        if d[i] is None:
            d[i]=now
            queue.append(i)
print("Yes")
for i in range(2,N+1):
    print(d[i])

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

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]

for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

Q = deque()
Q.append(1)

while Q:
    x = Q.pop()
    for t in G[x]:
        if USED[t] == -1:
            Q.appendleft(t)
            USED[t] = x

if -1 in USED:
    print("No")
else:
    print("Yes")
    print(*USED[2:])

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

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

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

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

from collections import deque
Q=deque()
Q.append(1)
while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==-1:
            USE[to]=x
            Q.appendleft(to)

if -1 in USE:
    print("No")
else:
    print("Yes")
    print(*USE[2:])

Solution (Python):



from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

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

graph = [[] for i in range(N)]

for A, B in AB:
    graph[A-1] += [B]
    graph[B-1] += [A]

D = deque([0])
visited = [0] * N
visited[0] = 1

ret = [0 for i in range(N)]

while D:
    v = D.popleft()
    for i in graph[v]:
        i -= 1
        if visited[i]: continue
        visited[i] = 1
        ret[i] = v + 1
        D.append(i)

if any(ret[1:]):
    print("Yes")
    for i in ret[1:]:
        print(i)
else:
    print("No")

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

for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

Q = deque()
Q.append(1)

while Q:
    x = Q.pop()
    for t in G[x]:
        if USED[t] == -1:
            Q.appendleft(t)
            USED[t] = x

if -1 in USED:
    print("No")
else:
    print("Yes")
    print(*USED[2:])

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



ans = [-1]*(N+1)
ans[1] = 0
dis_stack = list()
dis_stack.extend(graph[0])
bef_stack = [1]




while dis_stack:
    now_watch=dis_stack.pop(0)
    next_watch = graph[now_watch]
    for spot in next_watch:
        if(ans[spot] != -1):
            continue            
        
        
        dis_stack.append(spot)
        ans[spot] = now_watch
            
 
ans.pop(0)
print("Yes")
for i in range(1,len(ans)):
    print(ans[i])

Solution (Python):



from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

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

graph = [[] for i in range(N)]

for A, B in AB:
    graph[A-1] += [B]
    graph[B-1] += [A]

D = deque([0])
visited = [0] * N
visited[0] = 1

ret = [0 for i in range(N)]

while D:
    v = D.popleft()
    for i in graph[v]:
        i -= 1
        if visited[i]: continue
        visited[i] = 1
        ret[i] = v + 1
        D.append(i)

if any(ret[1:]):
    print("Yes")
    for i in ret[1:]:
        print(i)
else:
    print("No")

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

for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

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

Q = deque()
Q.append(1)

while Q:
    x = Q.pop()
    for t in G[x]:
        if USED[t] == -1:
            Q.appendleft(t)
            USED[t] = x

if -1 in USED:
    print("No")
else:
    print("Yes")
    for _ in USED[2::]:
        print(_)

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

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

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

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


q=deque([1])

while q:
    pos=q.popleft()
    for i in links[pos]:
        if results[i]==-1:
            results[i]=pos
            q.append(i)
print('Yes')
print('\n'.join(str(i) for i in results[2:]))

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

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])

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())
    g[a-1].append(b)
    g[b-1].append(a)
d = [0]*n
check = [False]*n
check[0] = True
def bfs():
    q = deque()
    q.append(1)
    
    while q:
        room = q.popleft()
        for nroom in g[room-1]:
            if check[nroom-1]:
                continue
            d[nroom-1] = room
            check[nroom-1] = True
            q.append(nroom)

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

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


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

from collections import deque

todo=deque([0]) 
mae=[-1]*n 
visited=[False]*n 
mae[0]=0
visited[0]=True


while todo:
    now=todo.popleft() 
    for next in road[now]:
        if visited[next]: 
            continue
        visited[next]=True 
        mae[next]=now 
        todo.append(next) 


if False in visited:
    print("No")
else:
    print("Yes")
    [print(i+1) for i in mae[1:]]

Solution (Python):
from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(m):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * n
    siru[0] = 1
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not siru[n-1]: 
                q.append(n)
                siru[n-1] = now
    
    
    print("Yes")
    print("\n".join(map(str, siru[1:])))
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(m):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * n
    siru[0] = 1
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not siru[n-1]: 
                q.append(n)
                siru[n-1] = now
    
    
    print("Yes")
    print("\n".join(map(str, siru[1:])))
if __name__ == "__main__":
    main()

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)

flag = [0] * (n+1)
flag[0] = 1
flag[1] = 1

d = deque()
d.append(1)

guidepost = [-1] * (n+1)

while d:
  v = d.popleft()
  for i in graph[v]:
    if flag[i] != 0:
      continue
    flag[i] = 1
    d.append(i)
    if guidepost[i] != -1:
      print("No")
      exit()
    else:
      guidepost[i] = v
  
if not all(guidepost):
  print("No")
  exit()

ans = guidepost[2:]    

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

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

flag = [0] * (n+1)
flag[0] = 1
flag[1] = 1

d = deque()
d.append(1)

guidepost = [-1] * (n+1)

while d:
  v = d.popleft()
  for i in graph[v]:
    if flag[i] != 0:
      continue
    flag[i] = 1
    d.append(i)
    if guidepost[i] != -1:
      print("No")
      exit()
    else:
      guidepost[i] = v
  
if not all(guidepost):
  print("No")
  exit()

ans = guidepost[2:]    

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

Solution (Python):
from collections import deque


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

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


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

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


while que:
    v = que.popleft() 
    
    for i in link[v]:
      
      if dist[i] == -1:
        dist[i] = v
        que.append(i)


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

Solution (Python):
from collections import deque

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

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

INF = 2 * m

dists = [INF for i in range(n)]

def bfs(cur, pre, dist):
    stack = deque([[cur, pre, dist]])
    while stack:
        cur, pre, dist = stack.popleft()
        if dist < dists[cur]:
            dists[cur] = dist
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur, dist + 1])
bfs(0, -1, 0)

print('Yes')

for i in range(1,n):
    di = dists[i]
    for e in E[i]:
        if di - 1 == dists[e]:
            print(e+1)
            break

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

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])

Solution (Python):

from pprint import pprint
from collections import deque

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

A = []
B = []




route2 = [[] for n in range(N)]

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

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)










room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue)>0:
    now = queue.popleft()
    
    
    
    

    for i in route2[now]:
        if i not in visited:

    
    
    
    
    

            
            
            
            
            
            
            
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

            
            

            
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1
            
            

    

    
    

    
    
    
    
    
    

print('Yes')
for s in room_sign[1:]:
    print(s)

Solution (Python):

from collections import deque

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

A = []
B = []


route2 = [[] for n in range(N)]

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

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)

Solution (Python):
import sys
import math
import numpy as np
from collections import deque

def I():
  return int(input())
def IS():
  return map(int, input().split())
def IL():
  return [int(x) for x in input().split()]
def ILL(n):
  return [list(map(int, input().split())) for _ in range(n)]
def S():
  return input()
def SS():
  return input().split()

def main():
  N, M = IS()
  to = [[] for _ in range(N)]
  INF = float('inf')
  for i in range(M):
    A, B = IS()
    A -= 1
    B -= 1
    to[A].append(B)
    to[B].append(A) 
  
  q = deque()
  q.append(0)
  
  dist = [INF] * N
  
  prev = [-1] * N
 
  
  while len(q) != 0:
    
    v = q.popleft()
    
    for u in to[v]:
      if prev[u] == -1:
        dist[u] = dist[v] + 1
        prev[u] = v
        q.append(u)
  
  print("Yes")
  for i in range(1, len(prev)):
    print(prev[i] + 1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


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

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


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

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


while que:
    v = que.popleft() 
    
    for i in link[v]:
      
      if dist[i] == -1:
        dist[i] = v
        que.append(i)


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

Solution (Python):
import itertools
import math
import fractions
import functools
import copy
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)

ans = [-1] * n
d = deque([0])

while d:
    f = d.popleft()
    for i in ab[f]:
        if ans[i] == -1:
            ans[i] = f
            d.append(i)

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

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

queue = []
dist = [float('INF')]*(n+1)
pre = [-1]*(n+1)
dist[0] = 0
dist[1] = 0
queue.append(1)

while(len(queue)>0):
    now = queue.pop(0)
    for nx in mp[now]:
        if dist[nx]!= float('INF'):
            continue
        dist[nx] = dist[now] + 1
        pre[nx] = now
        queue.append(nx)
print('Yes')
for i in range(2,n+1):
    print(pre[i])

Solution (Python):
from collections import deque

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

q = deque()
q.append(0)
dist = [INF] * n
prev = [-1] * n

while len(q) != 0:
    v = q.popleft()
    for u in to[v]:
        if prev[u] == -1:
            
            prev[u] = v
            q.append(u)


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

Solution (Python):
import sys
from collections import deque

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

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

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

ans = [0] * (n+1)
alr = [0] * (n+1)
que = deque([1])
while len(que) > 0:
    idx = que.popleft()
    for i in path[idx]:
        if alr[i] == 0:
            que.append(i)
            ans[i] = idx
            alr[i] = 1
        else:
            pass

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

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

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

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

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

ans = [0] * (n+1)
alr = [0] * (n+1)
que = deque([1])
while len(que) > 0:
    idx = que.popleft()
    for i in path[idx]:
        if alr[i] == 0:
            que.append(i)
            ans[i] = idx
            alr[i] = 1
        else:
            pass

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

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

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

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

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

ans = [0] * (n+1)
alr = [0] * (n+1)
que = deque([1])
while len(que) > 0:
    idx = que.popleft()
    for i in path[idx]:
        if alr[i] == 0:
            que.append(i)
            ans[i] = idx
            alr[i] = 1
        else:
            pass

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

Solution (Python):
from collections import deque

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

AB=[]
for i in range(M):
	AB.append(list(map(int,input().split())))

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

for a, b in AB:
    links[a].append(b)
    links[b].append(a)
q=deque([1])

while q:
	pos=q.popleft()
	for i in links[pos]:
		if results[i]==-1:
			results[i]=pos
			q.append(i)
print('Yes')
print('\n'.join(str(i) for i in results[2:]))

Solution (Python):
import queue

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

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

q = queue.Queue()
q.put((1,0))
while not q.empty():
    x,p = q.get()
    if pre[x] != -1:
        continue
    
    pre[x] = p
    for i in to[x]:
        if pre[i] == -1:
            q.put((i,x))

print('Yes')
for p in pre[2:]:
    print(p)

Solution (Python):
from collections import deque

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


q = deque()
q.append(0)

dist = [INF] * n

prev = [-1] * n


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

    
    for u in to[v]:
        if prev[u] == -1:
            dist[u] = dist[v] + 1
            prev[u] = v
            q.append(u)


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

Solution (Python):
from collections import defaultdict
import queue

def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    
    q = queue.Queue()
    F = [-1]*N 
    s = 1 
    step = 0
    while True:
        
        for v in vum[s]:
            
            if F[v-1] < 0:
                q.put(v)
                F[v-1] = s
        if q.empty():
            break
        
        s = q.get()

    if -1 in F[1:]:
        print('No')
    else:
        print('Yes')
        for d in F[1:]:
            print(d)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

for _ in range(m):
    a, b = list(map(int, input().split()))
    if a not in root_dict:
        root_dict[a] = [b]
    else:
        root_dict[a].append(b)
    if b not in root_dict:
        root_dict[b] = [a]
    else:
        root_dict[b].append(a)

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

done = deque([1])

while done:
    x = done.popleft()
    for i in root_dict[x]:
        if visited[i-1] < 0:
            visited[i-1] = x
            done.append(i)

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

Solution (Python):
from collections import deque

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

for _ in range(m):
    a, b = list(map(int, input().split()))
    if a not in root_dict:
        root_dict[a] = deque([b])
    else:
        root_dict[a].append(b)
    if b not in root_dict:
        root_dict[b] = deque([a])
    else:
        root_dict[b].append(a)

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

done = deque([1])

while done:
    x = done.popleft()
    while root_dict[x]:
        i = root_dict[x].popleft()
        if visited[i-1] < 0:
            visited[i-1] = x
            done.append(i)

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

Solution (Python):


def input_one_number():
    return int(input())

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

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

N,M = input_multiple_number()

shilve = [-1]*(N+1)
michi = [[] for _i in range(N+1)]

for i in range(M):
	a,b = input_multiple_number()
	michi[a].append(b)
	michi[b].append(a)

que = [1]

while len(que) > 0:
	now_heya = que.pop(0)
	for nexthop in michi[now_heya]:
		if shilve[nexthop] == -1:
			shilve[nexthop] = now_heya
			que.append(nexthop)


print("Yes")
for i in shilve[2:]:
	print(i)

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]+=[b-1]
  g[b-1]+=[a-1]

from collections import deque
q=deque([0])
s=[0]*n
while q:
  p=q.popleft()
  for v in g[p]:
    if s[v] < 1:
      s[v]=p+1
      q.append(v)
if 0 in q:print('No')
else:
  print('Yes')
  for v in s[1:]:
    print(v)

Solution (Python):
from collections import deque

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



def bfs(x):
	q = deque()
	q.append(x)
	while(len(q) != 0):
		now = q.popleft()

		for k in g[now]:
			if(misi[k] == 0):

				misi[k] = now
				
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)



if(True):
	print("Yes")
	for i in range(2,n+1):
		
		print(misi[i])
else:
	print("no")

Solution (Python):
from collections import deque
def bfs(gragh,n,start):
    visited = [0]*n
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited


n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(lambda n: int(n)-1,input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = bfs(graph,n,0)[1:]
if all(visited):
    print("Yes")
    print(*visited,sep="\n")
else:
    print("No")

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 q:
    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)
'''
catupperさんのコードを写経しました。
'''

Solution (Python):
from collections import deque
n,m,*inp=map(int,open(0).read().split())
d=[[] for i in range(n)]
for i in range(m):
    j=2*i
    a,b=inp[j:j+2]
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
l=[-1 for i in range(n)]
q=deque([0])

while len(q)>0:
    x=q.popleft()
    for i in d[x]:
        
        if l[i]==-1:
            q.append(i)
            
            l[i]=str(x+1)
l=l[1:]

print('No' if 0 in l else 'Yes\n'+'\n'.join(l))

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

G = list([set() for i in range(N)])
for i in range(M):
  A,B = map(int,input().split())
  G[A-1].add(B-1)
  G[B-1].add(A-1)

q = queue.Queue()
dist = [-1] * N
dist[0] = 0
q.put(0)

while(q.empty() != True):
  nextNode = q.get()
  nextDist = dist[nextNode] + 1
  for i in G[nextNode]:
    if dist[i] == -1:
      q.put(i)
      dist[i] = nextNode

if len([0 for i in dist if i == -1]) == 0:
  print('Yes')
  for i in dist[1:]:
    print(i + 1)
else:
  print('No')

Solution (Python):
import sys

def input(): return sys.stdin.readline().rstrip()

from collections import deque

def main():

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

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

    for i in range(m):

        a,b=map(int,input().split())

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

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

    queue=deque([0])

    visited=[False]*n

    visited[0]=True

    ans=[0]*n

    while queue:

        node=queue.popleft()

        for xnode in graph[node]:

            if visited[xnode]:continue

            ans[xnode]=node+1

            visited[xnode]=True

            queue.append(xnode)

    print("Yes")

    for a in ans[1:]:

        print(a)





if __name__=='__main__':

    main()

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

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

sirube=[-1]*N
visited=[True]+[False]*(N-1)
def bfs():
    global visited,sirube
    queue=[1]
    while queue:
        now=queue.pop(0)
        
        for n in p[now]:
            if not visited[n-1]:
                queue.append(n)
                visited[n-1]=True
                sirube[n-1]=now
    return
bfs()
if -1 in sirube[1:]:
    print("No")
    exit()

print("Yes")
for sir in sirube[1:]:
    print(sir)