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 collections

n, m = map(int, input().split())
dic = collections.defaultdict(lambda:[])
for _ in range(m):
  a, b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
  
ans = [None] * n
bfs = [(1,dic[1])]
visited = set()
get = 0
while bfs and get < n:
  now, nexts = bfs.pop(0)

  for i in nexts:
    if i in visited:
      continue
    ans[i-1] = now
    get += 1
    bfs.append((i,dic[i]))
    visited.add(i)
      
print('Yes')  
for i in range(1, n):
  print(ans[i])

Solution (Python):








import queue







def solve():
    N, M = map(int, input().split())
    queries = (map(int, input().split()) for _ in range(M))

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

    for a, b in queries:
        tree[a].add(b)
        tree[b].add(a)

    nn = 10 ** 9
    signs = [nn for _ in range(N+1)]
    visited = {0}

    que = queue.Queue()

    que.put((0, 1))  

    while not que.empty():

        parent, current = que.get()

        if current in visited:
            continue

        visited.add(current)
        signs[current] = parent

        for t in tree[current]:
            if t in visited:
                continue
            else:
                que.put((current, t))

    return signs[2:]


def main():
    ans = solve()
    if 10**9 in ans:
        print('No')
    else:
        print('Yes')
        for a in ans:
            print(a)


if __name__ == "__main__":
    main()

Solution (Python):

import numpy as np
from collections import deque
import collections
import heapq


n, m = list(map(int, input().split()))
a = [0] * m
b = [0] * m
path = [[] for i in range(n+1)]

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


ans = [0]*(n+1)
visited = []
que = deque([[1, 1]])  
que_items = set([1])


while len(que) > 0:
    now, prev = que.popleft()
    
    for can_go in path[now]:
        if(not (can_go in que_items)):  
            
            que.append([can_go, now])
            que_items.add(can_go)
    ans[now] = prev
    visited.append(now)
    

if (len(visited) != n):
    print('No')
else:
    print('Yes')
    for _ans in ans[2:]:
        print(_ans)

Solution (Python):
from collections import deque
    
def bfs(graph,start): 
    dist = [-1] * (N)
    ans = [-1] *(N)
    dist[start]= 0
    q = deque([start])
    cnt = 0
    while q:
        x = q.popleft()
        for i in graph[x]:
            
            
            if dist[i] == -1:
                dist[i] = dist[x] + 1
                ans[i] = x+1
                q.append(i)
    return dist, ans

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

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

dist,ans = bfs(X,0)

if -1 in dist:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(ans[i])

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

from collections import deque

def linput(_t=int):
    return list(map(_t, input().split()))

def gcd(n,m):
    while m: n,m = m, n%m
    return n

def lcm(n,m): return n*m//gcd(n,m)

def main():

    N,M = linput()
    
    
    mG = [[] for _ in [0,]*(N+1)]

    for _ in [0,]*M:
        a,b = linput()
        mG[a].append(b)
        mG[b].append(a)

    vR = [0,] * (N+1)
    vR[1] = 1

    vQ = deque([])
    vQ.append((mG[1],1))

    while vQ:
        vG, pp = vQ.popleft()
        

        for g in vG:
            if vR[g] == 0:
                vR[g] = pp
                vQ.append((mG[g],g))

    print("Yes")
    print(*(r for r in vR[2:]), sep="\n")
    
    


main()

Solution (Python):
import threading, queue

N, M = map(int, input().split())
AB = [[] * N for _ in range(N)]
m = [0] * (N + 10)
q = queue.Queue()
q.put(0)

for _ in range(M):
  A, B = map(int, input().split())
  AB[A - 1].append(B - 1)
  AB[B - 1].append(A - 1)
  
while not q.empty():
  s = q.qsize()
  for _ in range(s):
    t = q.get()
    for p in AB[t]:
      if m[p] == 0:
        m[p] = t + 1
        q.put(p)

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

Solution (Python):
from heapq import heapify,heappush,heappop
N,M = map(int,input().split())
room = [[] for i in range(0,N+1,1)]
mitisirube = [-1]*(N+1)

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

D_INF = 10**10
d = [D_INF]*(N+1)
d[1] = 0
que =[]
heapify(que)
heappush(que,(d[1],1))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(room[place]),1):
        if d[room[place][i]] > time + 1:
            d[room[place][i]]=time+1
            heappush(que,(time+1,room[place][i]))
            mitisirube[room[place][i]] = place
        
print("Yes")
for i in range(2,N+1,1):
    print(mitisirube[i])

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)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')

Solution (Python):
from collections import deque

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

G = dict()
for i in range(1,N+1):
    G[i] = set()

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

ans = dict()

Q = deque([1])
visited = set()
while Q:
    room = Q.popleft()
    
    if room not in visited:
        visited.add(room)
        
        for r in G[room]:
            if r not in ans:
                ans[r] = room
            Q.append(r)
for i in range(2, N+1):
    if i not in ans:
        print('No')
        exit()

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

Solution (Python):
def resolve():
    import collections
    n, m = map(int, input().split())
    hw = [[0] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        hw[a].append(b)
        hw[b].append(a)

    dis = [0] * (n+1)
    arr = [-1] * (n+1)
    que = collections.deque([1])
    while len(que) != 0:
        a = que.popleft()
        test = hw[a]
        for i in range(len(test)):
            if test[i] != 0:
                goal = test[i]
                if arr[goal] == -1:
                    arr[goal] = a
                    que.append(goal)
    if 0 in arr[2:]:
        print("No")
    else:
        print("Yes")
        for i in range(2, len(arr)):
            print(arr[i])
resolve()

Solution (Python):
from collections import deque
N,M=map(int,input().split())
B=[[] for i in range(N)]

for i in range(M):
  a,b=map(int,input().split())
  B[a-1].append(b-1)
  B[b-1].append(a-1)
  
visited=[0]*N
d = deque()
ans=[-1]*N
d.append(0)
visited[0]=1
while d:
  c=d.popleft()
  for e in B[c]:
    if visited[e]:
      continue
      
    d.append(e)
    visited[e]=1
    ans[e]=c
    
print("Yes")
for i in range(1,N):
  print(ans[i]+1)

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

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

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    path = [None] * n
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                path[i] = v+1
                queue.append(i)
    return d, path


d, p = bfs(0)
if None in d:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(p[i])

Solution (Python):
from queue import Queue

n, m = map(int, input().split())
to = {}
for i in range(m):
    a, b = map(int, input().split())
    from_a = to.get(a, set())
    from_a.add(b)
    to[a] = from_a
    from_b = to.get(b, set())
    from_b.add(a)
    to[b] = from_b
ans = [0] * (n + 1)
ans[1] = 1
nx = Queue()
nx.put(1)
while not nx.empty():
    cur = nx.get()
    nxts = to.get(cur, [])
    for nxt in nxts:
        if ans[nxt] != 0:
            continue
        ans[nxt] = cur
        nx.put(nxt)
if 0 in ans[2:]:
    print('No')
else:
    print('Yes')
    [print(i) for i in ans[2:]]

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

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

visited = [N + 100 for _ in range(N + 1)]
step = 0
visited[1] = step
que = [1]

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

while len(que) > 0:
    step += 1

    q = que.pop(0)

    for t in m[q]:
        if visited[t] == N + 100:
            que.append(t)
        if step <= visited[t]:
            visited[t] = step
            os[t] = q 

for o in os[2:]:
    if o == 0:
        print('No')
        break
else:
    print('Yes')
    for _o in os[2:]:
        print(_o)

Solution (Python):

"""
@author: H_Hoshigi
"""

import queue

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

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

    answer_list = [ -1 for i in range(N)]
    answer_list[0] = 0

    next_rooms_queue = queue.Queue()
    next_rooms_queue.put(0)
    now_room = int()
    while not next_rooms_queue.empty():
        now_room = next_rooms_queue.get()
        for i in connedted_room_list[now_room]:
            if answer_list[i] == -1:
                answer_list[i] = now_room
                next_rooms_queue.put(i)

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

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

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque, defaultdict

def main():
    N, M = tuple(int(c) for c in input().split(' '))
    
    
    R = defaultdict(set)
    for _ in range(M):
        a, b = tuple(int(c) for c in input().split(' '))
        R[a].add(b)
        R[b].add(a)

    D = [0]*(N+1)  
    D[1] = -1
    traced = set()
    traced.add(1)

    
    q = deque((1, x) for x in R[1])
    
    while(True):
        if(len(q) <= 0):
            
            
            break
        pos, x = q.popleft()
        if x == 1:
            continue
        if D[x] == 0:
            assert not x in traced
            D[x] = pos
            traced.add(x)
            
            t = [(x, y) for y in R[x]]
            for x, y in t:
                if not y in traced:
                    q.append((x, y))
            
        elif D[x] == pos:
            assert x in traced
            continue
        else:
            
            continue
            
            
    print('Yes')
    for i in range(2, len(D)):
        print(D[i])


if __name__ == "__main__":
    main()

Solution (Python):
from queue import Queue
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].insert(len(root[A-1]), B)
    root[B-1].insert(len(root[B-1]), A)
room = [0]*N

q = Queue()
for k in root[0]:
    room[k-1] = 1
    q.put(k)
while not q.empty():
    a = q.get()
    for j in root[a-1]:
        if room[j-1] == 0:
            q.put(j)
            room[j-1] = a
if 0 in room[1:]:
    print("No")
else:
    print("Yes")
    for ans in room[1:]:
        print(ans)

Solution (Python):


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

D = {} 
T = {}
for i in range(1, N+1):
    D[i] = []
    T[i] = 0

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

child = D[1]
parent = [1]


while len(parent) > 0:
    child2 = []
    for p in parent:
        for c in D[p]:
            if T[c] != 0: continue
            T[c] = p
            child2.append(c)
    parent = child2

for i in range(2, N+1):
    if T[i] == 0:
        print('No')
        exit()

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

Solution (Python):
import queue

q = queue.Queue()

N,M = map(int,input().split())
AB = []
dic = {}
for _ in range(M):
    AB = list(map(int,input().split()))
    dic.setdefault(AB[1], []).append(AB[0])
    dic.setdefault(AB[0], []).append(AB[1])

cnt = 1
ans = [0] * N

for i in range(len(dic[1])):
    ans[dic[1][i] - 1] = 1
    q.put(dic[1][i])

while q.empty() == False:
    current_number = q.get()
    for i in range(len(dic[current_number])):
        if ans[dic[current_number][i] - 1] == 0:
            ans[dic[current_number][i] - 1] = current_number
            q.put(dic[current_number][i])

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

Solution (Python):
n,m=map(int,input().split())
marks = {i+1:-1 for i in range(n)}
marks[1] = 0
roots = {i+1:[] for i in range(n)}
count = 0
for i in range(m):
    a,b = map(int,input().split())
    roots[a].append(b)
    roots[b].append(a)

before_room = 1
searchs = [{'root':roots[1], 'mark':1}]
while searchs != []:
    next_search = []
    for search in searchs:
        for root in search['root']:
            new_root = []
            if marks[root] == -1:
                marks[root] = search['mark']
                count += 1
                new_root += roots[root]
            else:
                continue
            next_search.append({'root':roots[root], 'mark':root})
    searchs = next_search[:]

del marks[1]
print('Yes')
for v in marks.values():
    print(v)

Solution (Python):




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

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

visited = [0] * (n+1)
visited[0] = 10 ** 9

beforeidx = [0] * (n+1)


q = list()
q.append(1)

while(len(q) > 0):
    stidx = q.pop(0)
    for j in range(len(plist[stidx])):
        nextidx = plist[stidx][j]
        if visited[nextidx] == 0:
            q.append(nextidx)
            beforeidx[nextidx] = stidx
            visited[nextidx] = 1

if min(visited) > 0:
    print('Yes')
    for i in range(2, n+1):
        print(beforeidx[i])
else:
    print('No')

Solution (Python):


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

graph = {}
for node in range(1, n+1):
    graph[node] = []

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



michi = [None] * (n+1)
uses = [False] * (n+1)

def set(x):
    return x

uses[1] = True

cur_node = 1
cur_nodes = {}
child_nodes = graph[cur_node]
for child_node in child_nodes:
    cur_nodes[child_node] = cur_node
depth = 1
while True:
    next_nodes = {}
    done = False
    for cur_node, pnode in cur_nodes.items():
        if not uses[cur_node]:
            michi[cur_node] = pnode
            uses[cur_node] = True
            for child_node in graph[cur_node]:
                if child_node == pnode or uses[child_node]:
                    continue
                next_nodes[child_node] = cur_node
            done = True

    if not done:
        break
    depth += 1
    cur_nodes = next_nodes
    

michi = michi[2:]
if None in michi:
    print("No")
else:
    print("Yes")
    for node in michi:
        print(node)

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

point=[-1]*n
dist=[-1]*n
from collections import deque
q=deque()
q.append(0)
dist[0]=0
while q:
  cur=q.popleft()
  for nx,nd in G[cur]:
    if dist[nx]!=-1:continue
    dist[nx]=dist[cur]+nd
    point[nx]=cur
    q.append(nx)


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

Solution (Python):

MOD = 10 ** 9 + 7
INFI = 10**10

import math
from collections import deque
import itertools
import heapq


import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default




def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


def main():
    n,m=map(int,input().split())
    a=[[] for _ in range(n+1)]
    for i in range(m):
        x,y=map(int,input().split())
        a[x].append(y)
        a[y].append(x)

    moto=[-1 for _ in range(n+1)]
    def bfs(a, visited, s):
        queue = deque([])
        visited[s] = 0
        for i in a[1]:
            queue.append(i)
            visited[i] = visited[1] + 1
            moto[i] = 1
        while queue:
            if len(queue) <= 0:
                return
            now = queue.popleft()

            for i in a[now]:
                if visited[i]<0:
                    visited[i]=visited[now]+1
                    queue.append(i)
                    moto[i]=now
    visited=[-1 for _ in range(n+1)]
    bfs(a,visited,1)

    if min(moto[2:])>=0:
        print("Yes")
        for i in range(2,n+1):
            print(moto[i])
    else:
        print("No")


if __name__ == "__main__":

    main()

Solution (Python):
from collections import deque

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

route = [[] for _ in range(N)]
used = [False] * N
used[0] = True

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

queue= deque([(route[0],0)])


def bfs(queue):
    while queue:
        next,before = queue.popleft()
        for i in next:
            if used[i] != False:
                continue
            used[i] = before+1
            queue.append((route[i], i))

bfs(queue)

for i, v in enumerate(used):
    if i == 0:
        print("Yes")
    else:
        print(v)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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

N, M = getNM()
dist = [[] for i in range(N + 1)]
for i in range(M):
    a, b = getNM()
    dist[a].append(b)
    dist[b].append(a)

pos = deque([[1, 0]])
ignore = [-1] * (N + 1)
ans = [-1] * (N + 1)
ignore[1] = 0

while len(pos) > 0:
    u, time = pos.popleft()
    for i in dist[u]:
        if ignore[i] != -1:
            continue
        ignore[i] = time + 1
        ans[i] = u
        pos.append([i, time + 1])
ans.pop(0)
ans.pop(0)
flag = True
for i in ans:
    if i < 0:
        flag = False
if flag:
    print('Yes')
    for i in ans:
        print(i)
else:
    print('No')

Solution (Python):
import math


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

    routes = {i:[] for i in range(N)}
    directions = [None for _ in range(N)]
    queue = [0]
    current_time = 1

    for i in range(M):
        A, B = map(lambda n: int(n)-1, input().split())
        routes[A].append(B)
        routes[B].append(A)

    
    directions[0] = 0
    while len(queue) != 0:
        i = queue.pop(0)
        
        go = routes[i]
        
        for j in go:
            if directions[j] == None:
                
                directions[j] = i
                queue.append(j)
                
                

    
    if None in directions:
        print("No")
        return
    else:
        print("Yes")
        for i in range(1,N):
            print(directions[i]+1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

from collections import deque

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

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

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

Solution (Python):
N, M = [int(i) for i in input().split()]
from collections import deque

graph = [deque([]) for _ in range(N + 1)]
for _ in range(M):
    u, v = [int(x) for x in input().split()]
    graph[u].append(v)
    graph[v].append(u)  


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


def bfs(root):
    if root is None:
        return
    sirube[1] = 1
    q = deque()
    q.append(root)
    while q:
        r = q.popleft()
        qq = graph[r]
        while qq:
            n = qq.popleft()
            if sirube[n] == -1:
                sirube[n] = r
                q.append(n)

bfs(1)  

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

Solution (Python):
[N,M]=[int(i)for i in input().split()]

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

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


shortestPath=[N+1]*(N+1)
shortestPath[1]=0
nextEdgeKouho=set([1])

while(len(nextEdgeKouho)>0):
  nextNextEdgeKouho = set([])
  for start in nextEdgeKouho:
    tmpshortestpath=shortestPath[start]
    for end in edge[start]:
      if shortestPath[end] == N+1:
        shortestPath[end] = start
        nextNextEdgeKouho.add(end)
  
  nextEdgeKouho=nextNextEdgeKouho


if N + 1 in shortestPath[1:]:
  print("No")
else:
  print("Yes")
  [print(i) for i in shortestPath[2:]]

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')

n_nodes, m_edges = map(int, input().split())
edges = [[] for _ in range(n_nodes)]
for _ in range(m_edges):
    u, v = map(int, input().split())
    edges[u - 1].append([v - 1, 1])
    edges[v - 1].append([u - 1, 1])


parents = [-1] * n_nodes


def dijkstra(n_nodes, edges, start):
    que = deque()
    dist = [INF] * n_nodes
    dist[start] = 0
    que.append([start, 0])
    while len(que) > 0:
        v, v_cost = que.popleft()
        if dist[v] < v_cost:
            continue
        for u, u_cost in edges[v]:
            if v_cost + u_cost < dist[u]:
                dist[u] = v_cost + u_cost
                parents[u] = v
                que.append([u, dist[u]])
    return dist


start = 0
dist = dijkstra(n_nodes, edges, start)



print('Yes')
for i in range(1, n_nodes):
    print(parents[i] + 1)

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

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

from collections import deque

s = [0 for _ in range(n)]
seen = [False for _ in range(n)]
seen[0] = True
queue = deque([1])
while queue:
    now = queue.popleft()
    for i in g[now-1]:
      if(not seen[i-1]):
        seen[i-1] = True
        s[i-1] = now
        queue.append(i)
s = s[1:]
if(0 in s):
  print("No")
else:
  print("Yes")
  for s_i in s:
    print(s_i)

Solution (Python):
N, M = map(int, input().split())
a = []
from collections import defaultdict
for i in range(M):
    a.append(list(map(int,input().split())))
dic = defaultdict(list)
res = {}
res_set =set()
res_set.add(1)
for i in range(M):
    dic[a[i][0]].append(a[i][1])
    dic[a[i][1]].append(a[i][0])
queue = [1]
while queue:
    tmp = queue.pop(0)
    for i in range(len(dic[tmp])):
        if dic[tmp][i] not in res_set:
            res_set.add(dic[tmp][i])
            queue.append(dic[tmp][i])
            res[dic[tmp][i]] = tmp
if len(res_set) < N:
    print("No")
else:
    print("Yes")
    for i in range(2, N + 1):
        print(res[i])

Solution (Python):
from collections import deque

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

"""
グラフの最短経路問題
１からたどる
最短経路の時，たどる前にいた点を答えとして収納すれば良い
"""
ans = [0] * (N + 1)
neighbor = [[] for _ in range(N+1)]

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

que = deque([1])
while len(que) > 0:
    s = que.popleft()
    
    for i in neighbor[s]:
        if ans[i] == 0:
            ans[i] = s
            que.append(i)

if 0 not in ans[2:]:
    print("Yes")
else:
    print("No")
    exit()

for i in ans[2:]:
    print(i)

Solution (Python):
N,M=map(int, input().split())
a_list=[]
for i in range(M):
    a_list.append(list(map(int,input().split())))
V_list=[[] for i in range(N)]

for item in a_list :
    V_list[item[0]-1].append(item[1])
    V_list[item[1] - 1].append(item[0])

from collections import deque
s_list=[0]*N
current_V=deque()
current_V.append(1)

while (current_V!=deque([])) :
    a=current_V.popleft()
    current_list=V_list[a-1]
    for item in current_list :
        if s_list[item-1]==0 :
            current_V.append(item)
            s_list[item-1] =a
print('Yes')
for item in s_list[1:] :
    print(item)

Solution (Python):
import queue

def func():
    n, m = map(int, input().split())
    m_list = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        m_list[a-1].append(b-1)
        m_list[b-1].append(a-1)
    q = queue.Queue()
    q.put(0)
    ans = [-1 for i in range(n)]
    ans[0] = -2
    while not q.empty():
        before_room = q.get()
        for i in m_list[before_room]:
            if ans[i] != -1:
                continue
            ans[i] = before_room
            q.put(i)
    for i in ans:
        if i == -1:
            print('No')
            return
    print ('Yes')
    for i in ans:
        if i == -2:
            continue
        print (i+1)

if __name__ == '__main__':
    func()

Solution (Python):
from collections import deque
n,m = map(int,input().split())
visited = [-1 for _ in range(n)]
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
pos = 0
que = deque([])
if g[0]:
    visited[0] = 0
    for nx in g[0]:
        que.append((nx, 0))
while que:
    to, now = que.popleft()
    if visited[to] != -1:
        continue
    else:
        visited[to] = now
        for nx in g[to]:
            que.append((nx, to))
visited = visited[1:]
if -1 in visited:
    print('No')
else:
    print('Yes')
    for k in visited:
        print(k+1)

Solution (Python):
def task(n, m, a, b):
    graph = []
    for i in range(0, n + 1):
        graph.append(set())

    for i in range(0, m):
        graph[a[i]].add(b[i])
        graph[b[i]].add(a[i])
    

    stack = [1]
    ans = 0
    traversed = {}
    traversed[1] = True

    while len(stack):
        nxtstack = set()
        ans += 1
        while len(stack):
            nxt = stack.pop()
            for value in graph[nxt]:
                if not value in traversed:
                    nxtstack.add(value)
                    traversed[value] = nxt
        stack = nxtstack

    for i in range(1, n + 1):
        if not i in traversed:
            print("No")
            return

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


n, m = map(int, input().split())
a = []
b = []
for i in range(0, m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
task(n, m, a, b)

Solution (Python):


import numpy as np

N,M = list(map(int, input().split()))
paths = []
connection_dic = {}

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

for i in range(M):
    A,B = list(map(int, input().split()))
    connection_dic[A].add(B)
    connection_dic[B].add(A)



ans_list = np.zeros(N-1, dtype = np.int)

current_distance = 0

parents = set([1])
next_parents = set()

while len(parents) > 0:
    
    
    
    current_distance += 1
    while len(parents) > 0:
        parent = parents.pop()
        for node in connection_dic[parent]:
            if node >= 2 and ans_list[node-2] == 0:
                ans_list[node-2] = parent
                next_parents.add(node)
    parents = next_parents
    next_parents = set()
    

for ans in ans_list:
    if ans == 0:
        print("No")
        exit()

print("Yes")
for ans in ans_list:
    print(int(ans))