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

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

G=[[] for i in range(n)]

for _ in range(m):
 y,yy=map(int,input().split())
 y-=1
 yy-=1
 G[y].append(yy)
 G[yy].append(y)

q=queue.Queue()

vis=[0]*n
mae=[-1]*n

q.put([0,0])
while q.empty()==False:
 r=q.get()
 if vis[r[0]]==1:
  continue
 vis[r[0]]=1
 mae[r[0]]=r[1]
 for v in G[r[0]]:
  if vis[v]==0:
   q.put([v,r[0]])

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

Solution (Python):
from collections import deque, defaultdict


def bfs(graph, start):

    queue = deque([start])
    visited = set()
    visited.add(start)
    parent = defaultdict(int)
    parent[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                queue.append(v)
                visited.add(v)
                parent[v] = current_vertex
    return parent

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

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

parent = bfs(graph, 1)

print('Yes')
for k, v in sorted(parent.items()):
    if v != 0:
        print(v)

Solution (Python):



from collections import deque

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

    for m in range(M):
        A, B = map(int, input().split())
        path[A-1].append(B-1)
        path[B-1].append(A-1)
    
    sign = [-1]*N
    q = deque()
    q.append(0)
    while q:
        u = q.popleft()
        for v in path[u]:
            if sign[v] == -1:
                sign[v] = u + 1
                q.append(v)
    
    print('Yes')
    print('\n'.join(map(str, sign[1:])))




if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


r, p = map(int, input().split())
graph = [[] for _ in range(r)]

for x in range(p):
    x1, x2 = map(int, input().split())
    graph[x1-1].append(x2-1)
    graph[x2-1].append(x1-1)

q = deque([0])
res = [-1]*r
res[0] = 0
while q:
    l = q.popleft()
    for x in graph[l]:
        if res[x] == -1:
            res[x] = l
            q.append(x)
if -1 in res[1:]:
    print("No")
    exit()
print("Yes")
for x in res[1:]:
    print(x+1)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

G = [[] for _ in range(N + 1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)

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

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

visited={1}
stack=deque([1])
re=[-1 for i in range(N+1)]
re[0]=0
re[1]=0
while stack:
    
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            re[p]=a
            stack.append(p)

if -1 in re:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(re[i])

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque


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


def I(): return int(sys.stdin.readline().rstrip())


def MI(): return map(int, sys.stdin.readline().rstrip().split())


def MS(): return map(str, sys.stdin.readline().rstrip().split())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def LS(): return list(sys.stdin.readline().rstrip().split())






n, m = map(int, input().split())
a = [0] * m
b = [0] * m
box = [[] for i in range(n)]
s = deque()
ans = [-1] * (n - 1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    box[a[i] - 1].append(b[i])
    box[b[i] - 1].append(a[i])
for i in range(len(box[0])):
    s.append([1, box[0][i]])

while len(s) > 0:
    k = s.popleft()

    if ans[k[1] - 2] == -1 and k[1] - 2 != -1:
        ans[k[1] - 2] = k[0]

        for i in range(len(box[k[1] - 1])):
            s.append([k[1], box[k[1] - 1][i]])

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

Solution (Python):
import queue
def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q =queue.Queue()
    q.put(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.get()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.put(next)
        if q.empty():
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



if __name__=='__main__':
    main()

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

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

ans=[-1]*n
ans[0] = 0
from collections import deque
q = deque([0])
while q:
    a=q.popleft()
    for i in lis[a]:
        if ans[i]==-1:
            ans[i]=a
            q.append(i)
print("Yes")
for i in range(1,len(ans)):
    print(ans[i]+1)

Solution (Python):
from queue import Queue

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

visited = [False for x in range(n)]
distance = [float("inf") for x in range(n)]
distance[0] = 0
parent = [-1 for x in range(n)]
que = Queue()
que.put(0)
while not que.empty():
    now = que.get()
    if visited[now]:
        continue
    visited[now] = True
    for _next in d[now]:
        if visited[_next]: continue
        if parent[_next] != -1: continue
        parent[_next] = now + 1
        distance[_next] = min(distance[_next], distance[now] + 1)
        que.put(_next)
print("Yes")
for i in parent[1:]:
    print(i)

Solution (Python):
import collections

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)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
  v=q.popleft()
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      ans[u]=v
      q.append(u)
print('Yes')
for i in range(2,n+1):
  print(ans[i])

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque


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


def I(): return int(sys.stdin.readline().rstrip())


def MI(): return map(int, sys.stdin.readline().rstrip().split())


def MS(): return map(str, sys.stdin.readline().rstrip().split())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def LS(): return list(sys.stdin.readline().rstrip().split())






n, m = map(int, input().split())
a = [0] * m
b = [0] * m
box = [[] for i in range(n)]
s = deque()
ans = [-1] * (n - 1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    box[a[i] - 1].append(b[i])
    box[b[i] - 1].append(a[i])
for i in range(len(box[0])):
    s.append([1, box[0][i]])

while len(s) > 0:
    k = s.popleft()

    if ans[k[1] - 2] == -1 and k[1] != 1:
        ans[k[1] - 2] = k[0]

        for i in range(len(box[k[1] - 1])):
            s.append([k[1], box[k[1] - 1][i]])

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

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
d=deque()

l=[[] for _ in range(n)]
R=[-1]*(n+1)
R[1]=0

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

def g(s):
    for i in range(len(l[s-1])):
        if R[l[s-1][i]]==-1:
            R[l[s-1][i]]=s
            d.append(l[s-1][i])
    if len(d)!=0:
        s=d.popleft()
        return g(s)
    else:
        return
g(1)
print("Yes")
for h in range(2,len(R)):
    print(R[h])

Solution (Python):
import sys
import numpy as np




from collections import deque

input = sys.stdin.readline
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    n, m = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(m)]
    graph = [[] for _ in range(n)]
    for a, b in AB:
        graph[a-1].append(b)
        graph[b-1].append(a)
    dist = np.ones(n)
    dist *= -1
    dist[0] = 0
    queue = deque([1])
    while queue:
        p = queue.popleft()
        for next in graph[p-1]:
            if dist[next-1] == -1:
                dist[next-1] = p
                queue.append(next)

    if np.count_nonzero(dist == -1) > 0:
        print(c)
    else:
        print('Yes')
        for d in dist[1:]:
            print(int(d))


if __name__ == '__main__':
    main()

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

ans_li = [-1]*n
queue=deque([0])
visited = [False]*n

while queue:
    x = queue.popleft()
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def bfs(s):
    from collections import deque
    check = [0] * (n + 1)
    check[s] = 1
    q = deque([s])
    while q:
        now = q.popleft()
        for next in graph[now]:
            if check[next] == 0:
                check[next] = str(now)
                q.append(next)
    return check


n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
print('Yes')
print('\n'.join(bfs(1)[2:]))

Solution (Python):


import heapq as hq


def D_stra(N, connections, st):
    mxc = float("inf") 
    cost = [mxc for i in range(N)]
    route = [mxc for i in range(N)]
    visited = [False for i in range(N)]
    cost[st] = 0
    q = []

    hq.heappush(q, (0, st))

    while q:
        c, node = hq.heappop(q)
        if visited[node]:
            continue
        visited[node] = True

        for connection in connections[node]:
            target, mc = connection
            if cost[target] > c + mc:
                cost[target] = c + mc
                hq.heappush(q, (c + mc, target))
                route[target] = node


    return cost, route

n, m = map(int, input().split())
mp2 =[]

connections = [[] for _ in range(n)]
for _ in range(m):
    aa, bb = map(int, input().split())
    connections[aa-1].append([bb-1, 1])
    connections[bb-1].append([aa-1, 1])

dijkstra_result = []
_, result = D_stra(n, connections, 0)

if float("inf") in result[1:]:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(result[i]+1)

Solution (Python):

from collections import deque


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



ans=[-1]*(N+1)
X=[[] for i in range(N+1)]

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

    X[a].extend([b])
    X[b].extend([a])

c=0
dq=deque([1])

while c<N:
    i = dq.popleft()
    for j in X[i]:
        if ans[j]==-1:
            ans[j]=i
            c+=1
            dq.append(j)
            
print('Yes')
print(*ans[2:],sep='\n')

Solution (Python):
from collections import deque

import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
n, m = list(map(int, input().split()))
room = [[] for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    room[a-1].append(b-1)
    room[b-1].append(a-1)

ans = [-1]*n


def bfs(i):
    q = deque()
    q.append(i)
    while q:
        x = q.popleft()
        for i in range(len(room[x])):
            if ans[room[x][i]] == -1:
                q.append(room[x][i])
                ans[room[x][i]] = x
    return


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

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10


N, M = [int(x) for x in stdin.readline().rstrip().split()]

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



for _ in range(M):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    route[A].append(B)
    route[B].append(A)


dist_to_1 = [INF for _ in range(N+1)]
dist_to_1[1] = 0


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


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



que = deque([1])


while len(que) != 0:
    now = que.popleft()
    
    
    if is_visited[now]:
        continue

    is_visited[now] = True

    
    for place in route[now]:
        que.append(place)

        
        if dist_to_1[now]+1 < dist_to_1[place]:
            dist_to_1[place] = dist_to_1[now]+1
            next_route[place] = now



if 0 in next_route[2:]:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(next_route[i])

Solution (Python):
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N, M = map(int, input().split())
guidepost = [None] * N
distance = [0] + [10**9] * (N - 1)
dd = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    dd[a].append(b)
    dd[b].append(a)
stack = deque([1])
checked = [False] * N
while len(stack) >= 1:
    i = stack.popleft()
    if checked[i - 1]:
        continue
    checked[i - 1] = True
    for j in dd[i]:
        distance[j - 1] = min(distance[j - 1], distance[i - 1] + 1)
        if guidepost[j - 1] is None:
            guidepost[j - 1] = i
        elif distance[guidepost[j - 1] - 1] > distance[i - 1]:
            guidepost[j - 1] = i
        if not checked[j - 1]:
            stack.append(j)
print('Yes')



print('\n'.join([str(guidepost[i]) for i in range(1, N)]))

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

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



root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in g[p+1]:
        if root[i-1] <= 0:
            q.put(i-1)
            root[i-1] = p + 1
            count += 1
            
            if count >= n:
                break


if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])

Solution (Python):
N,M = map(int,input().split())
L = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    L[A-1].append(B-1)
    L[B-1].append(A-1)
ans = [0] * N
visit = [0] * N
visit[0] = 1
from queue import Queue
q = Queue()
q.put(0)
while not q.empty():
    current = q.get()
    for a in L[current]:
        if visit[a] == 0:
            visit[a] = visit[current] + 1
            ans[a] = current + 1
            q.put(a)
        else:
            if visit[a] > visit[current] + 1:
                visit[a] = visit[current] + 1
                ans[a] = current + 1
flag = True
for i in range(1,N):
    if ans[i] == 0:
        flag = False
        print('No')
        break
if flag == True:
    print('Yes')
    for i in range(N-1):
        print(ans[i+1])

Solution (Python):
n, m = map(int, input().split())
c = [[] for i in range(n)]
d = [0]
e = [-1]*n
for i in range(m):
    a, b = map(int, input().split())
    c[a-1].append(b-1)
    c[b-1].append(a-1)
while d:
    f = d.pop(0)
    for i in c[f]:
        if e[i] == -1:
            d.append(i)
            e[i] = f
print("Yes")
for i in range(n-1):
    print(e[i+1]+1)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()

rt = [[] for i in range(n)]
srb = [None] * n
dk = [10**10]*n


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

from collections import deque
l = deque()

srb[0] = 0
for i in rt[0]:
    l.append(i)
    srb[i] = 1

while len(l) != 0:
    c = l.popleft()
    for i in rt[c]:
        if srb[i] == None:
            l.append(i)
            srb[i] = c+1

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

Solution (Python):
from collections import deque

import sys
input = sys.stdin.readline 

N,M = map(int,input().split())
path = [[] for i in range(N)]
ans = [None for i in range(N)]
visited = [0 for i in range(N)]

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

def bfs(path, root,visited):
  visited[root] = 1
  queue = deque([root])
  while queue:
    cur = queue.popleft()
    for chi in path[cur]:
      if visited[chi] == 1:
        continue
      else:
        ans[chi] = cur + 1
        visited[chi] = 1
        queue.append(chi)

  if all([i == 1 for i in visited]):
    return "Yes"
  else:
    return "No"
  
flag = bfs(path,0,visited)

print(flag)

if flag == "Yes":
  for i in range(1,N):
    print(ans[i])

Solution (Python):
n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace():
    tasks = [(1, 0)]
    i = 0
    while i < len(tasks):
        no, lv = tasks[i]
        for c in d[no]:
            if c != 1:
                if c not in r or (r[c][1] > lv and r[c][1] != 0):
                    r[c] = (no, lv)
                    tasks.append((c, lv + 1))
        i += 1
trace()

for i in range(2, n):
    if i not in r:
        print('No')
        break
else:
    print('Yes')
    for i in range(2, n +1):
        print(r[i][0])

Solution (Python):

import sys

N, M, *AB = map(int, sys.stdin.buffer.read().split())

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

for i in range(M):
  A,B = AB[2*i],AB[2*i+1]
  list_path[A].append(B)
  list_path[B].append(A)

list_bfs = [1]
list_flg = [0 for _ in range(N+1)]
list_flg[1] = 1

while len(list_bfs)>0:
  list_tmp = []
  for i in list_bfs:
    for j in list_path[i]:
      if list_flg[j]==0:
        list_tmp.append(j)
        list_flg[j] = i
  list_bfs = list_tmp

print('Yes')
for i in list_flg[2:]:
  print(i)

Solution (Python):

import sys

N, M, *AB = map(int, sys.stdin.buffer.read().split())

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

for i in range(M):
  A,B = AB[2*i:2*i+2]
  list_path[A].append(B)
  list_path[B].append(A)

list_bfs = [1]
list_flg = [0 for _ in range(N+1)]
list_flg[1] = 1

while len(list_bfs)>0:
  list_tmp = []
  for i in list_bfs:
    for j in list_path[i]:
      if list_flg[j]==0:
        list_tmp.append(j)
        list_flg[j] = i
  list_bfs = list_tmp

print('Yes')
for i in list_flg[2:]:
  print(i)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def bfs(s):
    from collections import deque
    check = [-1] * (n + 1)
    check[s] = 0
    q = deque([s])
    while q:
        now = q.popleft()
        for next in graph[now]:
            if check[next] == -1:
                check[next] = now
                q.append(next)
    return check


n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
print('Yes')
for v in bfs(1)[2:]:
    print(v)

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

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

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

kakutei = [1]

answer_li = [0]*n

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        if answer_li[r-1] == 0:
            kakutei.append(r)
            answer_li[r-1] = k

answer_li = answer_li[1:]
if 0 in answer_li:
    print('No')
else:
    print('Yes')
    for i in answer_li:
        print(i)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = [-1 for i in range(n+1)]
def bfs():
    
    que = deque([1])
    while que:
        node = que.popleft()
        for i in adjacent_list[node]:
            if ans[i] == -1:
                que.append(i)
                ans[i] = node
bfs()
print("Yes")
for i in range(2,n+1):
    print(ans[i])

Solution (Python):
from collections import deque
def bfs(graph, 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)
print("Yes")
print(*bfs(graph, N, 0)[1:], sep="\n")

Solution (Python):
from collections import deque

def main():
  N, M = list(map(int, input().split(' ')))

  root = [[] for i in range(N+1)]
  for i in range(M):
    A, B = list(map(int, input().split(' ')))
    root[A].append(B)
    root[B].append(A)

  mitisurube = [-1 for i in range(N+1)]
  next_ = deque()
  next_.append(1)

  while next_:
    now_pos = next_.popleft()
    for next_pos in root[now_pos]:
      if mitisurube[next_pos] == -1:
        mitisurube[next_pos] = now_pos
        next_.append(next_pos)
  
  
  
  print('Yes')
  print(*mitisurube[2:], sep='\n')

if __name__ == '__main__':
  main()

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

for i in range(m):
    ta, tb = map(int, input().split())
    dir[ta].append(tb)
    dir[tb].append(ta)

ans = [0]*(n+1)
flag = [False]*(n+1)
flag[1] = True
que = deque([1])
while que:
    
    now = que.popleft()
    for to in dir[now]:
        if flag[to]:
            continue
        que.append(to)
        flag[to] = True
        ans[to] = now

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

Solution (Python):

from collections import deque
def resolve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(lambda x:int(x)-1, input().split())
        G[x].append(y)
        G[y].append(x)

    dist = [-1]*N
    ans = [0]*N
    q = deque()
    q.append(0)
    while q:
        fm = q.popleft()
        for to in G[fm]:
            if dist[to] != -1:
                continue
            dist[to] += 1
            ans[to] = fm
            q.append(to)

    print("Yes")
    for i in range(1, N):
        print(ans[i] + 1)
        
if __name__ == "__main__":
    resolve()

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

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

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

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

q = [0]

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

while q:
    l = q.pop(0)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

if count == n:
    print('Yes')
    for i in ans[1:]:
        print(i+1)
else:
    print('No')

Solution (Python):
def resolve():
    from collections import deque

    n, m = map(int, input().split())
    d = {}
    par = [[] for i in range(n)]
    que = deque()
    for i in range(m):
        a, b = map(int, input().split())
        par[a - 1].append(b)
        par[b - 1].append(a)

    que.append(1)
    while(len(que) > 0):
        label = que.popleft()
        for i in par[label - 1]:
            if i not in d.keys():
                que.append(i)
                d[i] = label

    if len(d) < n:
        print("No")
        return

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

resolve()

Solution (Python):
from collections import deque
n, m = map(int, input().split())
lis = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)
queue = deque([1])
dist_list = [-1]*(n+1)
dist_list[1] = 0
while len(queue) != 0:
    now = queue.popleft()
    for v in lis[now]:
        if dist_list[v] == -1:
            dist_list[v] = dist_list[now] + 1
            queue.append(v)
print("Yes")
for i in range(2, n+1):
    for v in lis[i]:
        if dist_list[v] == dist_list[i]-1:
            print(v)
            break

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

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
lis = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)
queue = deque([1])
dist_list = [-1]*(n+1)
dist_list[1] = 0
while len(queue) != 0:
    now = queue.popleft()
    for v in lis[now]:
        if dist_list[v] == -1:
            dist_list[v] = dist_list[now] + 1
            queue.append(v)
print("Yes")
for i in range(2, n+1):
    for v in lis[i]:
        if dist_list[v] == dist_list[i]-1:
            print(v)
            break

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

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

kakutei = [1]

answer_li = [0]*n

while kakutei:
    k = kakutei.pop(0)
    for r in root[k-1]:
        if answer_li[r-1] == 0:
            kakutei.append(r)
            answer_li[r-1] = k

answer_li = answer_li[1:]
if 0 in answer_li:
    print('No')
else:
    print('Yes')
    for i in answer_li:
        print(i)

Solution (Python):
import queue

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

for i in range( M ):
  A, B = map( int, input().split() )
  A, B = A - 1, B - 1
  L[ min( A, B ) ].append( max( A, B ))
  L[ max( A, B ) ].append( min( A, B ))
  
R = [ -1 ] * N
Q = queue.Queue()
Q.put( 0 )
while not Q.empty():
  n = Q.get()
  for l in L[ n ]:
    if R[ l ] == -1:
      R[ l ] = n + 1
      Q.put( l )

is_Flag = True 
for i in R:
  if i < 0:
    is_Flag = False
if is_Flag:
  print( "Yes" )
else:
  print("No")

for i in range( 1, N ):
  print( R[ i ] )

Solution (Python):
from collections import deque

print("Yes")

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)

q = deque([0])
b = [0] * n
while q:
    x = q.popleft()
    for i in g[x]:
        if b[i] != 0:
            continue
        b[i] = x + 1
        q.append(i)

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

Solution (Python):
from collections import deque

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

d = {}

for i in range(N):
    d[i+1] = set()

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

que = deque([1])
checked = set()
ans = {1:-1}

while que:
    now = que.popleft()
    for h in d[now]:
        if not h in ans:
            ans[h] = now
            que.append(h)
    if len(ans) == N:
        break
    
if len(ans) == N:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
else:
    print('No')