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:
n, m = map(int, input().split())
road=[[] for i in range(n)]

# road[i]はi番目の部屋とつながってる部屋番号のリスと
for i in range(m):
    a, b = map(int, input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)

from collections import deque

todo=deque([0]) # 処理すべき点の番号を入れる
mae=[-1]*n # 前にどこにおったか
visited=[False]*n # その点に行ったかどうか
mae[0]=0
visited[0]=True

# 幅優先探索
while todo:
    now=todo.popleft() # やることリストから現在地を取得
    for next in road[now]:
        if visited[next]: # もう訪れてたらスルー
            continue
        visited[next]=True # 訪れてなかったら訪れたことにする
        mae[next]=now # nextの前の地点を代入
        todo.append(next) # nextが次の現在地の候補となる


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

Submission status: Accepted

Solution code:
from collections import deque

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

Submission status: Accepted

Solution code:
from collections import deque

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

d = deque()
d.append(1)

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

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

ans = guidepost[2:]    

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

Submission status: Accepted

Solution code:
import math
from collections import deque

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

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

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

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

d = deque()
d.append(1)

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

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

ans = guidepost[2:]    

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

Submission status: Accepted

Solution code:
from collections import deque

# 頂点数と辺数
N, M = map(int, input().split())
# 辺
AB = [map(int, input().split()) for _ in range(M)]

# 無向グラフの隣接リスト
link = [[] for _ in range(N + 1)]
for a, b in AB:
  link[a].append(b)
  link[b].append(a)
    
# BFSのデータフレーム
dist = [-1] * (N + 1)  # 始点から頂点iの距離
que = deque([1])       # 頂点1を始点としたキュー

# BFS 開始 (キューが空になるまで探索を行う)
while que:
    v = que.popleft() # キューから先頭頂点 v を取り出す
    
    for i in link[v]:
      # 未訪問頂点 i について距離情報を更新してキューに追加する
      if dist[i] == -1:
        dist[i] = v
        que.append(i)

# 結果出力（各頂点の頂点1からの距離）        
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))

Submission status: Accepted

Solution code:
from collections import deque

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

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

INF = 2 * m

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

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

print('Yes')

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

Submission status: Accepted

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

will.append(1)

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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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

A = []
B = []

# route = [[0 for j in range(N)] for i in range(N)]

# 隣接リスト
route2 = [[] for n in range(N)]

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

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


# # 隣接行列
# for i in range(N):
#     for j in range(N):
#
# for a, b in zip(A, B):
#     route[a - 1][b - 1] = route[b - 1][a - 1] = 1


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

stack = [0]

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

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

while len(queue)>0:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

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

    # for i, node in enumerate(route[now]):
    #     if node == 0:
    #         continue
    #
    #     if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1
            #
            # room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

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

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

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

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

room_sign = [None] * N

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

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

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

            room_sign[i] = now + 1

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

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
from collections import deque

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

def main():
  N, M = IS()
  to = [[] for _ in range(N)]
  INF = float('inf')
  for i in range(M):
    A, B = IS()
    A -= 1
    B -= 1
    to[A].append(B)
    to[B].append(A) 
  # queue
  q = deque()
  q.append(0)
  # diatance to first room
  dist = [INF] * N
  # previous room
  prev = [-1] * N
 
  #### BFS ####
  while len(q) != 0:
    # pop from queue
    v = q.popleft()
    # seatch room of v's neighboor
    for u in to[v]:
      if prev[u] == -1:
        dist[u] = dist[v] + 1
        prev[u] = v
        q.append(u)
  # print answer
  print("Yes")
  for i in range(1, len(prev)):
    print(prev[i] + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
import copy
from collections import deque

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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


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

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
import time
input = sys.stdin.readline

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

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
#n部屋数、M通路数
AB=[]
for i in range(M):
	AB.append(list(map(int,input().split())))

links=[[] for _ in range(N+1)]
results=[-1]*(N+1)#番号をそのまま使いたいから

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

while q:
	pos=q.popleft()#1からスタート
	for i in links[pos]:#部屋posにつながる部屋iを探索
		if results[i]==-1:#部屋iを未探索なら、そこに行くべき場所posを記入
			results[i]=pos
			q.append(i)#捜索した部屋iを次の出発地として追記
print('Yes')
print('\n'.join(str(i) for i in results[2:]))

Submission status: Accepted

Solution code:
import queue

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

# queue
q = deque()
q.append(0)
# 最初の部屋までの距離
dist = [INF] * n
# 直前の部屋
prev = [-1] * n

#### BFS ####
while len(q) != 0:
    # queueから値を取り出す
    v = q.popleft()

    # vに隣接する部屋について調べる
    for u in to[v]:
        if prev[u] == -1:
            dist[u] = dist[v] + 1
            prev[u] = v
            q.append(u)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    ### bfs ###
    q = queue.Queue()
    F = [-1]*N # 道標の先の部屋
    s = 1 # 始点
    step = 0
    while True:
        # print('s',str(s))
        for v in vum[s]:
            # print('v',str(v))
            if F[v-1] < 0:
                q.put(v)
                F[v-1] = s
        if q.empty():
            break
        # print(list(q.queue),V)
        s = q.get()

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

done = deque([1])

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

done = deque([1])

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

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

Submission status: Accepted

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

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

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

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

N,M = input_multiple_number()

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

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

que = [1]

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


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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

#q = []

def bfs(x):
	q = deque()
	q.append(x)
	while(len(q) != 0):
		now = q.popleft()
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

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

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

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

Submission status: Accepted

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


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

Submission status: Accepted

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

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

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

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

from collections import deque
q = deque()

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

q.append(0)
while q:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now

print('Yes')
for i in range(1,n):
    print(ans[i] + 1)
'''
catupperさんのコードを写経しました。
'''

Submission status: Accepted

Solution code:
from collections import deque
n,m,*inp=map(int,open(0).read().split())
d=[[] for i in range(n)]
for i in range(m):
    j=2*i
    a,b=inp[j:j+2]
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
l=[-1 for i in range(n)]
q=deque([0])
#print(d)
while len(q)>0:
    x=q.popleft()
    for i in d[x]:
        #print(i)
        if l[i]==-1:
            q.append(i)
            #print(i)
            l[i]=str(x+1)
l=l[1:]
#print(l)
print('No' if 0 in l else 'Yes\n'+'\n'.join(l))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys

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

from collections import deque

def main():

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

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

    for i in range(m):

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

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

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

    queue=deque([0])

    visited=[False]*n

    visited[0]=True

    ans=[0]*n

    while queue:

        node=queue.popleft()

        for xnode in graph[node]:

            if visited[xnode]:continue

            ans[xnode]=node+1

            visited[xnode]=True

            queue.append(xnode)

    print("Yes")

    for a in ans[1:]:

        print(a)





if __name__=='__main__':

    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
#AB=[list(map(int,input().split()) for _ n range(N))]
p=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,input().split())
    p[a].append(b)
    p[b].append(a)
#print(p)
sirube=[-1]*N
visited=[True]+[False]*(N-1)
def bfs():
    global visited,sirube
    queue=[1]
    while queue:
        now=queue.pop(0)
        #print(now)
        for n in p[now]:
            if not visited[n-1]:
                queue.append(n)
                visited[n-1]=True
                sirube[n-1]=now
    return
bfs()
if -1 in sirube[1:]:
    print("No")
    exit()

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

Submission status: Accepted

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

    ans=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    d=deque([1])
    while len(d)>0:
        now=d.popleft()
        v=now
        for u in G[v]:
            if flags[u]==False:
                flags[u]=True
                ans[u]=v
                d.append(u)

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

Submission status: Accepted

Solution code:
import sys
import os
from collections import deque

def file_input():
    f = open('ABC168/input.txt', 'r')
    sys.stdin = f

def main():
    if os.getenv("ENV")=='LOCAL':
        file_input()

    N,M=map(int, input().split())
    r={}
    for i in range(M):
        A,B=map(int, input().split())
        # print("A:"+str(A[i])+" B:"+str(B[i]))
        if A not in r:
            r[A]=[B]
        else:
            r[A].append(B)
        if B not in r:
            r[B]=[A]
        else:
            r[B].append(A)
        # print(tmp[A[i]-1])
    # print(r)

    q=deque()
    q.append(1)
    visited=set()
    visited.add(1)
    out=[0]*(N-1)
    while len(q)>0:
        # print("q="+str(q))
        position=q.popleft()
        # print("p="+str(position))
        for des in r[position]: #今いる場所から行ける場所を探索
            if des not in visited:  #訪問済みでないなら
                q.append(des)   #行ける場所だった場合キューに追加
                visited.add(des)   #訪問済みにする
                out[des-2]=position
                # print("destination="+str(des)+" p="+str(position)+" q="+str(q))
    # print(visited)



    print('Yes')
    [print(x) for x in out]

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = deque()
q.append(1)
while q:
    p = q.popleft()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.append(c)
print('Yes')
for i in range(2,n+1): print(ans[i])

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

for a, b in AB:
    graph[a - 1].append(b)
    graph[b - 1].append(a)
    
queue = deque()
visited = [0] * N
sign_list = [0] * N 

queue.append(1)
visited[0] = 1

while queue:
    room = queue.popleft()
    next_rooms = graph[room - 1]
    for r in next_rooms:
        if visited[r - 1] == 0:
            queue.append(r)
            sign_list[r - 1] = room
            visited[r - 1] = 1

yes = True
for s in sign_list[1:]:
    if s == 0:
        yes = False

if yes:
    print("Yes")
    for s in sign_list[1:]:
        print(s)
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

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


q = deque([0])
visited = [False] * n
visited[0] = True

while q:
    now = q.popleft()
    
    for i in graph[now]:
        if visited[i]: continue
        
        visited[i] = True
        ans[i] = now
        q.append(i)
        

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

Submission status: Accepted

Solution code:
from collections import deque
 
def bfs():
  que = deque([])
  que.append(0)
  
  while que:
    now = que.popleft()
    for next in g[now]: #部屋1から行ける場所で回す
      if d[next] == 0:
        que.append(next)
        d[next] = now +1
        
n,m = map(int,input().split())
g = [[] for i in range(n)]
d = [0]*n
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)
  
bfs()
print('Yes')
for i in range(1,n):
  print(d[i])

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
V = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
ans = [-1]*(n+1)
q = deque()
q.append(1)
while len(q):
    p = q.popleft()
    for c in V[p]:
        if c > 1 and ans[c] < 0:
            ans[c] = p
            q.append(c)
print('Yes')
for i in range(2,n+1): print(ans[i])

Submission status: Accepted

Solution code:
def function():
    N,M = map(int, input().split())
    paths = [[] for _ in range(N+1)]
    for _ in range(M):
        A,B = map(int, input().split())
        paths[A].append(B)
        paths[B].append(A)
    
    depths = [-1]*(N+1)
    depths[1] = 0
    pre = [-1]*(N+1)
    q = [1] # 1からスタート
    while len(q) != 0:
        i = q.pop(0)
        for ne in paths[i]:
            if depths[ne] == -1: # -1 は未踏破
                depths[ne] = depths[i]+1
                pre[ne] = i
                q.append(ne)
    print('Yes')
    for p in pre[2:]: print(p)

if __name__ == '__main__':
    function()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
n, m = map(int, input().split())
x = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    x[a] += [b]
    x[b] += [a]
ans = [0] * (n + 1)
ans[1] = 1
que = deque([1])
while que:
    q = que.popleft()
    for i in x[q]:
        if ans[i] == 0:
            ans[i] = q
            que.append(i)
print("Yes")
print(*ans[2:], sep="\n")

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7
n, m = map(int, input().split())
# 幅優先？
ans = [-1 for i in range(n)]  # i+1番目の部屋にある道しるべ
visited = [False for i in range(n)]
visited[0] = True
dicab = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in dicab.keys():
        dicab[a].append(b)
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]
    else:
        dicab[a] = [b]
        if b in dicab.keys():
            dicab[b].append(a)
        else:
            dicab[b] = [a]


def bfs():
    q = deque([0])
    while q:
        now = q.popleft()
        nlist = dicab[now]
        for nextnode in nlist:
            if visited[nextnode] == False:
                visited[nextnode] = True
                ans[nextnode] = now
                q.append(nextnode)


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

Submission status: Accepted

Solution code:
def function():
    N,M = map(int, input().split())
    paths = []
    for _ in range(N+1):
        paths.append([])
    
    for _m in range(M):
        A,B = map(int, input().split())
        paths[A].append(B)
        paths[B].append(A)
    
    dist = [-1]*(N+1)
    dist[1] = 0
    pre = [-1]*(N+1)
    q = [1] # 1からスタート
    while len(q) != 0:
        i = q.pop(0)
        for ne in paths[i]:
            if dist[ne] == -1:
                dist[ne] = dist[i]+1
                pre[ne] = i
                q.append(ne)
    #print(dist)
    print('Yes')
    pre.pop(0)
    pre.pop(0)
    for d in pre:
        print(d)

if __name__ == '__main__':
    function()