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.



Sample input:
4 4
1 2
2 3
3 4
4 2


Sample output:
Yes
1
2
2

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()

	ki = [[] for i in range(N)]
	for i in range(M):
		A,B = inputMap()
		ki[A-1].append(B-1)
		ki[B-1].append(A-1)

	ans = [-1 for i in range(N)]
	sign = [0]
	while True:
		signed = sign
		sign = []
		for i in signed:
			for room in ki[i]:
				if ans[room] == -1:
					ans[room] = i+1
					sign.append(room)
		if len(sign) == 0:
			break

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


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from queue import Queue

n, m = map(int, input().split())
ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]
L = [-1]*n
neighbor =[[] for i in range(n)]
for i in range(m):
  neighbor[a[i]-1].append(b[i])
  neighbor[b[i]-1].append(a[i])
  
q = Queue()

q.put([1])
L[0] = 0

while not q.empty():
  pos = q.get()
  valid_pos =[]
  for p in pos:
    for m in neighbor[p-1]:
      if L[m-1] == -1:
        L[m-1] = p
        valid_pos.append(m)
  if len(valid_pos) != 0:
    q.put(valid_pos)

print('Yes')    
for i in range(n-1):
  print(L[i+1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.edges = []
    self.sign = None


def main():
  N, M = map(int, input().split())
  nodes = [Node(i + 1) for i in range(N)]

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

  nodes[0].sign = 0
  count = 1

  queue = collections.deque()
  queue.append(nodes[0])

  while len(queue) != 0:
    n = queue.popleft()

    for e in n.edges:
      if e.sign is None:
        e.sign = n.idx
        count += 1
        queue.append(e)

  if count == len(nodes):
    print('Yes')
    for n in nodes[1:]:
      print(n.sign)
  else:
    print('No')


if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

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

sign=[0]
signed_map=[-1]*N
signed_map[0]=1
while True:
  signed=sign
  sign=[]
  for s in signed:
    for room in m[s]:#サインされた場所から繋がってるとこを回る
      if signed_map[room]==-1:
        signed_map[room]=s+1
        sign.append(room)
  if sign==[]:break

print('Yes')
for ch in signed_map[1:]:
  print(ch)

Submission status: Accepted

Solution code:
from collections import deque

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

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

roomSign=[-1]*n

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

D=deque([0])

while D:
    v=D.popleft()
    for i in graph[v]:
        if roomSign[i] == -1:
          roomSign[i]=v
          D.append(i)

print("Yes")

for i in range(1,n):
    print(roomSign[i]+1)

Submission status: Accepted

Solution code:

from collections import deque

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

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

def main():
  N, M, rooms = parse()
  # print(rooms)

  # 探索する部屋番号をqに入れる
  q = deque([])
  q.append(0)

  # 各部屋の道しるべを入れる変数
  guides = [None for n in range(N)]
  guides[0] = 0
  while len(q) > 0:
    room_num = q.popleft()
    # print("room_num:", room_num)

    # 次に探索する部屋は，今の部屋を道しるべに指す
    for next_room_num in rooms[room_num]:
      # print("guides[next_room_num]:", guides[next_room_num])
      if guides[next_room_num] == None:
        q.append(next_room_num)
        # print(next_room_num)
      
        guides[next_room_num] = room_num
        # if next_room_num != room_num:

      
    # print("q:", q)
    # print("guides:", guides)
    # input()
  
  for guide in guides[1:]:
    if guide == None:
      print("No")
      exit(0)
  print("Yes")
  for guide in guides[1:]:
    print(guide + 1)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque

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)#aにはbがつながってる
    graph[b-1].append(a-1)#bにはaがつながってる
#print(graph)

res=[-1]*n
que=deque()
que.append(0)

while len(que)>0:
    i=que.popleft();
    for j in graph[i]:
        if res[j]==-1:
            res[j]=i
            que.append(j)
    #print(que)

print("Yes")
for l in res[1:]:
    print(l+1)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int,input().split())
def vertex_node()  -> list:
    v_c = [[] for _ in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        v_c[a].append(b)
        v_c[b].append(a)
    return v_c

def bfs(l) -> list:
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 0
    d = deque()
    d.append(1)
    while d:
        v = d.popleft()
        for i in l[v]:
                if dist[i] != -1:
                    continue
                dist[i] = v
                d.append(i)
    return dist
if __name__ == "__main__":
    i = vertex_node()
    ans = bfs(i)[2:]
    print("Yes")
    for i in ans:
        print(i)

Submission status: Accepted

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

ab=[list(map(int,input().split())) for _ in range(m)]
ans=[0]*n
def dfs():
    deq.append(0)#1
    finish=set()
    finish.add(0)
    while deq:
        now=deq.popleft()
     #   print(now+1)
        for ad_i in adlist[now]:
            if ad_i-1 != now and ad_i-1 not in finish:
                if ans[ad_i-1]==0:
                    ans[ad_i-1]=now+1
                deq.append(ad_i-1)
                finish.add(ad_i-1)

adlist=[[] for _ in range(n)]
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
#print(adlist)
deq=deque()
dfs()
print("Yes")
for i in range(1,n):
    print(ans[i])

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
INF=9999999
N,M=map(int,input().split())
#隣接リスト
tolist=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    tolist[a-1].append(b-1)
    tolist[b-1].append(a-1)
#始点から幅優先探索
pathlist=[0]
roomsign=[INF]*N
roomsign[0]=1
#空になるまで実行 先頭を削除して取得
while pathlist:
    nth=pathlist.pop(0)
    for i in tolist[nth]:
        if roomsign[i]==INF:
            roomsign[i]=nth+1
            pathlist.append(i)

print("Yes")
print(*roomsign[1:N],sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
n, m = [int(e) for e in input().split()]
AB = [[] for _ in range(n+1)]
for i in range(m):
    A,B = [int(e) for e in input().split()]
    AB[A].append(B)
    AB[B].append(A)

ans = [0]*(n+1)
visited = [0]*(n+1)
root = 1
visited[root] = 1
q = deque([root])

while q:
    v = q.popleft()
    for w in AB[v]:
        if visited[w]==0:
            ans[w]=v
            visited[w] +=1
            q.append(w)
        
print('Yes')
for i in ans[2:]:
    print(i)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import breadth_first_tree, breadth_first_order
from scipy.sparse import csr_matrix, coo_matrix
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
A = []
B = []
for i in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
D = [1] * M
csr = coo_matrix((D, (A, B)), (N, N)).tocsr()
Tcsr = breadth_first_order(csr, 0, False, True)
ans = []
for i in Tcsr[1][1:]+1:
    if i == -9998:
        print("No")
        quit()
    ans.append(i)
print("Yes")
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
from collections import deque
INF = float('inf')

input = sys.stdin.readline
n,m = map(int, input().split())
AB = [tuple(map(int,input().split())) for i in range(m)]
G = [[] for _ in range(n)]

for a, b in AB:
    a , b = a-1 , b-1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
dist = [INF]*n
dist[0] = 0
back = [-1] * n
while q:
    v = q.popleft()
    for to in G[v]:
        if dist[v] + 1 >=dist[to]:continue
        dist[to] = dist[v]
        back[to] = v+1
        q.append(to)
print('Yes')
print(*back[1:],sep='\n')

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import breadth_first_tree, breadth_first_order
from scipy.sparse import csr_matrix, coo_matrix
N, M = map(int,input().split())
A = []
B = []
for i in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
D = [1] * M
csr = coo_matrix((D, (A, B)), (N, N)).tocsr()
Tcsr = breadth_first_order(csr, 0, False, True)
ans = []
for i in Tcsr[1][1:]+1:
    if i == -9998:
        print("No")
        quit()
    ans.append(i)
print("Yes")
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

for _ in range(m):
    a,b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
    
q=deque()
q.append(1)
ans={}
while q:
    node=q.popleft()
    for i in d[node]:
        #訪問済み
        if i in ans:
            continue
        q.append(i)
        ans[i]=node
print('Yes')
for k in sorted(ans):
    if k==1:
        continue
    print(ans[k])

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

for i in range(M):
  a = List[i][0]
  b = List[i][1]
  
  dict[a].append(b)
  dict[b].append(a)


kouho = deque([1])
sumi = [-1 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi.append(a)

  for t in dict[a]:
    if sumi[t] != -1:
      continue
    else:
      kouho.append(t)
      sumi[t] = a
          
ck = 0

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

Submission status: Accepted

Solution code:
from  collections  import deque

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

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

ans = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])

while q:
  v = q.popleft()
  for w in AB[v]:
    if visited[w]:
      continue
    visited[w] = 1
    ans[w] = v
    q.append(w)
    
print('Yes')
for i in ans[2:]:
  print(i)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    from collections import deque
    n,m = map(int,stdin.readline().rstrip().split())       
    AB=[]
    for _ in range(m):
        AB.append(list(map(int,stdin.readline().rstrip().split())))
    
    G = [[] for _ in range(n+1)]
    for a,b in AB:
        G[a].append(b)
        G[b].append(a)

    visit = [False]*(n+1)
    visit[0]=True
    path = [-1]*(n+1)

    dq = deque([1])

    while len(dq)>0:
        edge = dq.popleft()

        for i in G[edge]:
            if not visit[i]:
                visit[i] = True
                path[i] = edge
                dq.append(i)
        
    print("Yes")
    for i in path[2:]:
        print(i)
main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
from collections import deque

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

class Room:
  def __init__(self, num):
    self.num = num
    self.roots = []
    self.kyori = -1
    self.near = 0
    
  def add_root(self, to):
    self.roots.append(to)
  def set_kyori(self, num, kyori):
    self.kyori = kyori
    self.near = num

r_list = sorted(np.unique(np.array(list(itertools.chain.from_iterable(root)))))
rooms = {i:Room(i) for i in r_list}

for r in root:
  a, b = rooms[r[0]], rooms[r[1]]
  a.add_root(b)
  b.add_root(a)

kyori = 0
near = 0
rooms[1].set_kyori(near, kyori)
rooms[1].near = near
q = deque()
q.append(rooms[1])
while len(q) > 0:
  node = q.popleft()
  kyori+=1
  for r in node.roots:
    if r.kyori != -1:
      continue
    r.set_kyori(node.num, kyori)
    q.append(r)
  
rooms[1].set_kyori(0, 0)
for r in rooms.values():
  if r.kyori == -1:
    print('No')
    break
else:
  print('Yes')
  for r in list(rooms.values())[1:]:
    print(r.near)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)

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

sign = [-1]*n # 道しるべ
sign[0] = -2 
visited = [False]*n # visited or not
visited[0] = True

q = deque([0])
while len(q)>0:
	room = q.popleft()
	for nroom in nextroom[room]:
		if visited[nroom] == 0:
			visited[nroom] = 1
			sign[nroom] = room
			q.append(nroom)

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

Submission status: Accepted

Solution code:

from sys import stdin
from collections import deque


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ipt = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
    MOD = 100100100100100100

    pl = [0] * (N + 1)

    for a, b in ipt:
        if pl[a] == 0:
            pl[a] = [b]
        else:
            pl[a].append(b)
        if pl[b] == 0:
            pl[b] = [a]
        else:
            pl[b].append(a)

    que = deque([1])
    deep = [MOD] * (N + 1)
    deep[1] = 0
    deep[0] = 0
    arrow = [0] * (N + 1)
    cnt = 1

    while not not que:
        q = que.popleft()
        for i in pl[q]:
            if deep[i] != MOD:
                continue
            deep[i] = deep[q] + 1
            arrow[i] = q
            cnt += 1
            que.append(i)

    if N != cnt:
        print("No")
    else:
        print("Yes")
        for i in arrow[2:]:
            print(i)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
AB_s = [list(map(int, input().split())) for _ in range(M)]

MAP = [[] for _ in range(N)]
for AB in AB_s:
    A, B = map(int, AB)
    MAP[A-1].append(B)
    MAP[B-1].append(A)
answer = [0] * N
queue = deque([1])
answer[0] = N
while len(queue) > 0:
    P = queue.popleft()
    if True:
        for Q in MAP[P-1]:
            if answer[Q-1] == 0:
                answer[Q-1] = P
                queue.append(Q)
if min(answer) == 0:
    print("No")
else:
    print("Yes")
    for i in range(1,N):
        print(answer[i])

Submission status: Accepted

Solution code:
from collections import deque

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

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

q = deque()
q.append(1)
sign = [-1]*(n + 1)
sign[1] = 0

while q:
    rnum = q.popleft()
    for i in rooms[rnum]:
        if sign[i] == -1:
            sign[i] = rnum
            q.append(i)

print("Yes")

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
l = [list() for _ in range(n)]

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

dist = [float('inf')]*n
dist[0] = 0
pre = [0]*n
pre[0] = 1

queue = deque([0])
while queue:
  x = queue.popleft()
  for y in l[x]:
    if dist[y] == float('inf') and pre[y] == 0:
      dist[y] = dist[x] + 1
      pre[y] = x
      queue.append(y)

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(start, line):
    quene = deque([start])
    d = [None] * len(line) # reset distance from start
    d[start] = 0
    ans = [None] * len(line)
    while quene:
        v = quene.popleft()
        for i in line[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                ans[i] = v
                quene.append(i)
    return ans


def main():
    n,w = map(int,input().split()) #n:頂点数　w:辺の数
    checker = [0]
    line = [[] for _ in range(n)]
    for i in range(w):
        x,y= map(int,input().split()) 
        x -= 1
        y -= 1
        line[x].append(y)
        line[y].append(x)
    print("Yes")
    ans = bfs(0,line)
    for i in ans[1:]:
        print(i+1)

 
 
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
bridge = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    bridge[a - 1].append(b - 1)
    bridge[b - 1].append(a - 1)
queue = deque([0])
ans = [[] for i in range(n)]
ans[0].append('god')
while queue:
    now = queue.popleft()
    for factor in bridge[now]:
        if not (ans[factor]):
            ans[factor].append(now)
            queue.append(factor)
print('Yes')
for i in range(1, len(ans)):
    print(ans[i][0]+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

to = [list() for _ in range(N)]

for i in range(M):
    a,b = [int(x)-1 for x in input().rstrip().split()]
    to[a].append(b)
    to[b].append(a)

sign = [0]*N
dist = [N]*N
dist[0] = 0

q = deque()
q.append(0)

while q:
    v = q.popleft()

    for x in to[v]:
        if dist[x] > dist[v]+1:
            dist[x] = dist[v]+1
            sign[x] = v+1
            q.append(x)
    
print('Yes')
for i in sign[1:]:
    print(i)

Submission status: Accepted

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

# 次に行こうと思えば行けるポイント
graph=[[]for _ in range(N+1)]
 
for _ in range(M):
    A,B=map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)

# 探索済みリスト
dist=[-1]*(N+1)
dist[0]=0
dist[1]=0

# 候補探索キュー
D=deque()
D.append(1)
 
while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=V
        D.append(i)
 
print('Yes')
for j in dist[2:]:
    print(j)

Submission status: Accepted

Solution code:
from collections import deque

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

AB = [map(lambda x: int(x) - 1, input().split()) for _ in range(M)]
to_list = [[] for _ in range(N)]

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

result = [-1] * N
q = deque([0])
while q:
    i = q.popleft()
    for j in to_list[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i + 1) for i in result[1:]))

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6
'''

def solve(adj):
	n = len(adj)
	dis = [maxsize]*n
	ans = [0]*n
	q = [0]
	dis[0] = 0
	while(q):
		src = q.pop(0)
		for nn in adj[src]:
			if(dis[nn] == maxsize):
				ans[nn] = src
				dis[nn] = dis[src] + 1
				q.append(nn)
	for i in range(n):
		ans[i] += 1
	if(maxsize in dis[1:]):
		print('No')
	else:
		print('Yes')
		for i in range(1,n):
			print(ans[i])

N,M = list(map(int, stdin.readline().rstrip().split()))
adj = [[] for i in range(N)]
for _ in range(M):
	a,b = list(map(int, stdin.readline().rstrip().split()))
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
solve(adj)

Submission status: Accepted

Solution code:
from queue import Queue

inp = input
out = print

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

adj = {i:[] for i in range(1, n+1)}

for i in range(m):
    u,v = map(int, inp().split())
    adj[u].append(v)
    adj[v].append(u)

seen = [False for _ in range(n+1)]
par = [0 for _ in range(n+1)]
q = Queue()
q.put(1)
seen[0] = seen[1] = True

while not q.empty():
    u = q.get()
    
    for v in adj[u]:
        if not seen[v]:
            q.put(v)
            seen[v] = True
            par[v] = u

if sum(seen) != n+1:
    out('No')

else:
    out('Yes')
    for i in range(2, n+1):
        out(par[i])

Submission status: Accepted

Solution code:
import sys

max_int = 1000000001  # 10^9+1
min_int = -max_int

n, m = map(int, sys.stdin.readline().split())
G = {}
for _m in range(m):
    a, b = map(int, sys.stdin.readline().split())
    if a not in G:
        G[a] = [[b], -1]
    else:
        G[a][0].append(b)

    if b not in G:
        G[b] = [[a], -1]
    else:
        G[b][0].append(a)

pretends = [1]
L = -1
while pretends:
    L += 1
    new_pretends = []
    for pretend in pretends:
        if G[pretend][1] != -1:
            continue
        G[pretend][1] = L
        for neighbor in G[pretend][0]:
            new_pretends.append(neighbor)
    pretends = new_pretends

for vertex in G:
    if G[vertex][1] == -1:
        print('No')
        exit()

print('Yes')

for i in range(2, n + 1):
    for neighbor in G[i][0]:
        if G[neighbor][1] == G[i][1] - 1:
            print(neighbor)
            break

Submission status: Accepted

Solution code:
import heapq

# def heapify(x):
#     for i in range((x)):
#         x[i] = -x[i]
#     heapq.heapify(x)

# def heappush(heap, item):
#     heapq.heappush(heap, -item)

# def heappop(heap):
#     return -heapq.heappop(heap)

# from heapq import heappop, heappush
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


def raw_input():
    return input()


rooms_count, passages_count = map(int, raw_input().split())
adj = []
for i in range(0, rooms_count):
    adj.append([])

for j in range(0, passages_count):
    a, b = map(int, raw_input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

seen = set()
distance = [100000000] * rooms_count
next = [100000000] * rooms_count
h = []
heapq.heappush(h, (0, 0, -1))
while len(h):
    (d, room, parent) = heapq.heappop(h)
    if (distance[room] <= d):
        continue
    distance[room] = d
    next[room] = parent
    seen.add(room)

    for neighbor in adj[room]:
        heapq.heappush(h, (d + 1, neighbor, room))

if len(seen) == rooms_count:
    print('Yes')
    for room in range(1, rooms_count):
        print(next[room] + 1)
else:
    print('No')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]

next_node = [[] for _ in range(n)]
for a, b in edge:
    next_node[a-1].append(b)
    next_node[b-1].append(a)

q = [1]
visit = [1]  + [0] * (n-1)
prev = [0] * n
while q:
    now = q.pop(0)
    for i in next_node[now-1]:
        if visit[i-1] == 0:
            q.append(i)
            visit[i-1] = 1
            prev[i-1] = now
print('Yes')
print(*prev[1:], sep='\n')

Submission status: Accepted

Solution code:
import queue
import math
q = queue.Queue()
A = []
B = []
N,M = map(int,input().split())
check = [-1]*N
graph = [[] for i in range(N+1)]
flag = [0]*N
for i in range(M):
	lines = list(map(int,input().split()))
	A.append(lines[0])
	B.append(lines[1])
	graph[lines[0]].append(lines[1])
	graph[lines[1]].append(lines[0])

q.put(1)
check[0] = 0
while not q.empty():
	p = q.get()
	for np in graph[p]:
		if check[np-1] == -1:
			check[np-1] = check[p-1] + 1
			q.put(np)

for i in range(M):
	if check[A[i]-1] - check[B[i]-1] == 1:
		flag[A[i]-1] = B[i]
	if check[B[i]-1] - check[A[i]-1] == 1:
		flag[B[i]-1] = A[i]

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