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:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map( int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map( lambda x:int(x)-1, input().split())
        E[u].append(v)
        E[v].append(u)
    d = deque([0])
    V = [-1]*N
    V[0] = 0
    while d:
        u = d.popleft()
        for v in E[u]:
            if V[v] == -1:
                V[v] = u+1
                d.append(v)
    print("Yes")
    print( "\n".join( map( str, V[1:])))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
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)

from collections import deque
inf = 10 ** 6
mark = [-1 for _ in range(n)]
que = deque()
mark[0] = 0
que.append(0)

while que:
    cur = que.popleft()
    for to in edges[cur]:
        if mark[to] == -1:
            mark[to] = cur
            que.append(to)

if any(mark[i] == -1 for i in range(n)):
    print('No')

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
s=[[]for i in range(N)]
print("Yes")
for i in range(M):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
l=[-1]*N
b=[0]
while b:
    a=[]
    for i in b:
        for j in s[i]:
            if l[j]==-1:
                l[j]=i+1
                a.append(j)
    b=a
print(*l[1:],sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

g = defaultdict(list)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)

source = 1
dist = {}
q = deque()
q.append(source)
dist[source] = 0
while q:
    node = q.popleft()
    level = dist[node]
    for nbr in g[node]:
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = level + 1

if len(dist) != N:
    print("No")
    exit()

print("Yes")
for i in range(2, N + 1):
    for nbr in g[i]:
        if dist[nbr] == dist[i] - 1:
            print(nbr)
            break

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0

    # 経路を復元するための配列．直前に通った場所を記録
    prev = [None] * n_nodes

    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)

    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)

        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue

        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for j in edge[i]:
            if dist[j] > dist[i] + 1:
                dist[j] = dist[i] + 1
                prev[j] = i  # jにいくために直前にiを通った
                heapq.heappush(q, (dist[j], j))

    return dist, prev


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

    dist, prev = dijkstra(0, N, edges)

    for d in dist:
        if d == INF:
            print("No")
            return

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import defaultdict, deque
import heapq
g = defaultdict(list)
for a, b in ab:
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)


d = [float('inf')] * n
d[0] = 0

q = [(0, 0)] # min-heap, (距離, 頂点)
prev = [float('inf')] * n # 経路をたどるときに使う
heapq.heapify(q)
while q:
    du, u = heapq.heappop(q) # 最短距離とその頂点
    if d[u] < du:
        continue
    for v in g[u]:
        if du + 1 < d[v]:
            d[v] = du + 1
            prev[v] = u
            heapq.heappush(q, (d[v], v))

f = True
prev2 = []
for i in range(1, n):
    if prev[i] == float('inf'):
        f = False
    prev2.append(prev[i] + 1)

if f:
    print('Yes')
    for p in prev2:
        print(p)
else:
    print('No')

Submission status: Accepted

Solution code:
import collections


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

F = [-1 for _ in range(N)]

que = collections.deque([0])
while que:
    target = que.popleft()
    for g in G[target]:
        if F[g] == -1:
            F[g] = target
            que.append(g)

res = [F[i] + 1 for i in range(N)]
res[0] = "Yes"
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, m = tin()
	#s = input()
	mm = [[] for _ in range(n)]
	rrp=[-1]*n
	for _ in range(m):
		a,b = tin()
		mm[a-1].append(b-1)
		mm[b-1].append(a-1)
	
	q = queue.Queue()
	q.put((0,0))
	while not q.empty():
		pos, parent = q.get()
		if rrp[pos] >= 0:
			continue
		rrp[pos] = parent
		
		for v in mm[pos]:
			q.put((v, pos))
	print('Yes')
	for v in rrp[1:]:
		print(v+1)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from collections import deque

N,M = [int(i) for i in input().split()]
graph = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = [int(i) for i in input().split()]
    graph[a].add(b)
    graph[b].add(a)

path = {1:0}
seen = set([1])
que = deque([1])
while que:
    node = que.popleft()
    for n in graph[node]:
        if n not in seen:
            seen.add(n)
            que.append(n)
            path[n] = node

if len(seen) != N:
    print("No")
else:
    print("Yes")
    for i in range(2,N+1):
        print(path[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,M = map(int, input().split())

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

for _ in range(M):
  A,B = map(int, input().split())
  dict_path[A].append(B)
  dict_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 dict_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)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
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)
    G[b-1].append(a-1)
from collections import deque
q=[0]
q=deque(q)
ans=[-1]*n
while len(q)>0:
    now=q.popleft()
    for i in G[now]:
        if ans[i]<0:
            ans[i]=now
            q.append(i)
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def Yes(): print("Yes"); return
def No(): print("No"); return

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N,M = inputIL()

graph = [[] for i in range(N)]
for _ in range(M):
  a,b = inputIL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
d = [INF for i in range(N)]
prev = [None for i in range(N)]
q = deque([0])
d[0] = 0
while q:
  x = q.popleft()
  nd = d[x]+1
  for nx in graph[x]:
    if nd < d[nx]:
      d[nx] = nd
      prev[nx] = x
      q.append(nx)
      
print("Yes")
for i in prev[1:]:
  print(i+1)

Submission status: Accepted

Solution code:
import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
# t=int(input())
t=1
graph=defaultdict(lambda:[])
for _ in range(t):
    n,m=map(int,stdin.readline().split())
    for _ in range(m):
        a,b=map(int,stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    root=1
    ans=defaultdict(lambda:0)
    visited=defaultdict(lambda:False)
    q=deque()
    q.append(1)
    visited[1]=True
    count=0
    while(len(q)>0):
        temp=q.popleft()
        for i in graph[temp]:
            if(not visited[i]):
                visited[i]=True
                ans[i]=temp
                q.append(i)
                count+=1
    if(count==n-1):
        print("Yes")
        for i in range(2,n+1):
            print(ans[i])
    else:
        print("No")

Submission status: Accepted

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

from collections import deque

d = deque()
d.append(0)
ans = [-1]*n
while d:
    u = d.popleft()
    for v in to[u]:
        if ans[v]==-1:
            ans[v]=u
            d.append(v)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N)]

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

ans = [None]*N
ans[0]=-1

queue=[0]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if ans[e] is not None: continue
            ans[e]=q
            queue_new.append(e)

    queue = queue_new

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    edge = [[] for _ in range(N)]
    for i in range(M):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    queue = deque([0])
    dist = [inf]*N
    dist[0] = 0
    ans = [-1]*N
    while(queue):
        v = queue.popleft()
        for to in edge[v]:
            if(dist[to]==inf):
                ans[to] = v+1
                queue.append(to)
                dist[to] = dist[v] + 1

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

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
N, M = map(int, input().split())
e = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
Q = dq([1])
d = [10 ** 6] * (N + 1)
d[1] = 0
res = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  for y in e[x]:
    if d[y] > d[x] + 1:
      d[y] = d[x] + 1
      Q.append(y)
      res[y] = x
if min(res[2: ]):
  print("Yes")
  for r in res[2: ]: print(r)
else: print("No")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
n,m=NM()
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    c=1
    edge[a].append((b,c))
    edge[b].append((a,c))
pre=[-1]*(n+1)
from heapq import *
def dijkstra(s,n):
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            pre[v]=u
            heappush(pq,(d[v],v))
    return d
dijkstra(1,n)
if -1 in pre[2:]:
    print("No")
else:
    print("Yes")
    for i in pre[2:]:
        print(i)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

q = [(0, 0)]
dist = [float('inf')] * N
dist[0] = 0
ret = [-1] * N
ret[0] = 0

while q :
  cc, cur = heappop(q)
  for nex in vec[cur] :
    if cc + 1 < dist[nex] :
      dist[nex] = cc + 1
      ret[nex] = cur
      heappush(q, (cc + 1, nex))
      
if -1 in ret :
  print('No')
else :
  print('Yes')
  for i in range(1, N) :
    print(ret[i] + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
    import queue
    q=queue.Queue()
    q.put((0,-1))
    ans=[-1]*N
    
    while not q.empty():
        v,p=q.get()
        for nv in adj[v]:
            if nv!=p:
                if ans[nv]==-1:
                    q.put((nv,v))
                    ans[nv]=v
                    
    print("Yes")
    for i in range(1,N):
        print(ans[i]+1)
                

main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

Ans=[0]*n

Chk=[False]*n
Dist=[float("inf")]*n
Chk[0]=True
Dist[0]=0
S=collections.deque()
S.append(0)
while S:
  s=S.popleft()
  for g in edge[s]:
    if not Chk[g]:
      S.append(g)
      Chk[g]=True
      Ans[g]=s+1



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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    adj = [[] for _ in range(N)]
    for i in range(M):
        a = A[i]
        b = B[i]
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    visited = set()
    q = collections.deque([(0, 0)])  # (index,from)
    ans = [-1] * N
    while q:
        index, _from = q.popleft()
        if index in visited:
            continue
        visited.add(index)
        ans[index] = _from
        for adj_v in adj[index]:
            q.append((adj_v, index))

    if len(visited) != N:
        print("No")
        return
    print("Yes")
    for i, a in enumerate(ans):
        if i == 0:
            continue
        print(a + 1)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
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)
T = [-1]*n
que = deque()
que.append(0)
while que:
    v = que.popleft()
    for nv in G[v]:
        if T[nv] == -1:
            T[nv] = v+1
            que.append(nv)
print("Yes")
print(*T[1:], sep="\n")

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.prev = [None] * N
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)
		G.add_edge(B, A)

	BF = BFS(G, 0, N)
	print("Yes")
	prev = BF.prev
	for i in range(1, N):
		print(prev[i] + 1)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def examA():
    S = {0:"pon",1:"pon",2:"hon",3:"bon",4:"hon",5:"hon",6:"pon",7:"hon",8:"pon",9:"hon"}
    N = SI()
    ans = S[int(N[-1])]
    print(ans)
    return

def examB():
    K = I()
    S = SI()
    N = len(S)
    if N<=K:
        ans = S
    else:
        ans = S[:K]+"..."
    print(ans)
    return

def examC():
    A, B, H, M = LI()
    a = abs(H*30 - M*5.5)
    deg = min(360-a,a)*math.pi/180
    #print(deg)
    ans = (A**2 + B**2 - 2*A*B*math.cos(deg))**(0.5)
    print(ans)
    return

def examD():

    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)

    ans = [-1]*N

    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = now
                    que.append(ne)
        return W
    ans = bfs(N,0,V)
    for a in ans:
        if a==-1:
            print("No")
            return
    print("Yes")
    for v in ans[1:]:
        print(v+1)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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)]

adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

s = 1
dq = deque([s])
d = [-1] * (n + 1)
d[s] = 0
p = [-1] * (n + 1)

while dq:
    u = dq.popleft()
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            p[v] = u
            dq.append(v)

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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


class Graph:
    def __init__(self, n, e, wv=None, we=None):
        self.n = n
        self.e = list(map(tuple, e))
        self.wv = wv
        self.we = we

        self.adjlist = self.__get_adjlist()
        self.wedict = self.__get_wedict()

    def __get_adjlist(self):
        adjlist = [[] for _ in range(self.n)]

        for v0, v1 in self.e:
            adjlist[v0].append(v1)

        return adjlist

    def __get_wedict(self):
        return dict(zip(self.e, self.we))


def dijkstra(graph, s):
    INF = float('inf')

    d = [INF for _ in range(graph.n)]
    d[s] = 0
    prev = [None for _ in range(graph.n)]

    queue = []
    heappush(queue, (0, s))

    while queue:
        di, v = heappop(queue)
        for neighbor in graph.adjlist[v]:
            dtmp = d[v] + graph.wedict[(v, neighbor)]
            if dtmp < d[neighbor]:
                d[neighbor] = dtmp
                prev[neighbor] = v
                heappush(queue, (dtmp, neighbor))

    return d, prev


graph = Graph(n=n, e=e, we=[1] * (2 * m))

_, prev = dijkstra(graph, 0)

print('Yes')
for p in prev[1:]:
    print(p + 1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict

n, m = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: float("inf")))
for _ in range(m):
    a, b = map(int, input().split())
    edges[a-1][b-1] = 1
    edges[b-1][a-1] = 1

def dijkstra(s, n, cost):
    d = [float("inf")] * n
    d[s] = 0
    que = [[0, s]]
    prev = {}
    heapify(que)
    while len(que) > 0:
        u_dist, u = heappop(que)
        #まだ使われてない頂点の中から最小の距離のものを探す
        for v in edges[u].keys():
            alt = d[u] + cost[u][v]
            if d[v] > alt:
                prev[v] = u
                d[v] = alt
                heappush(que, [alt, v])
    return d, prev

_, prev = dijkstra(0, n, edges)
ans = []
ans.append("Yes")
for i in range(1, n):
    ans.append(str(prev[i]+1))
print("\n".join(ans))

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)

    Direc = [-1] * N
    q = []
    heapify(q)
    heappush(q, (0, 0, 0))
    while q:
        dist, now, pre = heappop(q)
        if Direc[now] == -1:
            Direc[now] = pre + 1
            for ne in Edge[now]:
                if ne != pre: heappush(q, (dist + 1, ne, now))
    print("Yes")
    print("\n".join(map(str, Direc[1:])))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    dist = [-1] * N
    par = [-1] * N
    dist[0] = 0
    dq = deque([0])
    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = d + 1
            par[u] = v + 1
            dq.append(u)

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


if __name__ == '__main__':
    main()