AtCoder Beginner Contest 168 [ D - .. (Double Dots) ] https://atcoder.jp/contests/abc168/tasks/abc168_d

abc168_d.py

'''
[問題]
https://atcoder.jp/contests/abc168/tasks/abc168_d

[解説]
https://img.atcoder.jp/abc168/editorial.pdf

https://blog.hamayanhamayan.com/entry/2020/05/17/224335
"
競プロの考察方針の一つとして、典型問題に似ていないかという糸口がある。

このある始点から移動コスト1で移動したときの最短距離を求めるのは、典型問題であり、
BFSで解けることが知られている。
まず、今回の問題はBFSで最短経路問題を解く方法を知っていると解法が分かりやすい。
"
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

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

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

# 幅優先探索(BFS)
que = [0]
dist = [None] * N   # 距離
dist[0] = 0
ans = [None] * N

for v in que:
    for vv in route[v]:
        if dist[vv] is None:
            dist[vv] = dist[v] + 1
            que.append(vv)  # 次の探索キューに追加
            ans[vv] = v

# ansが埋まってないところがあるなら、No
for i in range(1,N):
    if ans[i] is None:
        print("No")
        exit()

# ansが全て埋まっているならYes
print("Yes")
for i in range(1,N):
    print(ans[i] + 1)