配点: $400$ 点

問題文

あるところに、洞窟があります。

洞窟には $N$ 個の部屋と $M$ 本の通路があり、部屋には $1$ から $N$ の、通路には $1$ から $M$ の番号がついています。通路 $i$ は部屋 $A_i$ と部屋 $B_i$ を双方向につないでいます。どの $2$ 部屋間も、通路をいくつか通って行き来できます。部屋 $1$ は洞窟の入り口がある特別な部屋です。

洞窟の中は薄暗いので、部屋 $1$ 以外の各部屋に $1$ つずつ道しるべを設けることにしました。各部屋の道しるべは、その部屋と通路で直接つながっている部屋の $1$ つを指すように置きます。

洞窟の中は危険なので、部屋 $1$ 以外のどの部屋についても以下の条件を満たすことが目標です。

• その部屋から出発し、「いまいる部屋にある道しるべを見て、それが指す部屋に移動する」ことを繰り返すと、部屋 $1$ に最小の移動回数でたどり着く。

目標を達成できる道しるべの配置が存在するか判定し、存在するならばそのような配置を $1$ つ出力してください。

制約

• 入力はすべて整数
• $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)$
• どの $2$ 部屋間も、通路をいくつか通って行き来できる

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$A_1$ $B_1$

$:$

$A_M$ $B_M$

出力

目標を達成できる道しるべの配置が存在しなければ No を出力せよ。

存在する場合、$N$ 行出力せよ。$1$ 行目には Yes を、$i\ (2 \leq i \leq N)$ 行目には部屋 $i$ の道しるべが指す部屋の番号を出力せよ。

4 4
1 2
2 3
3 4
4 2

Yes
1
2
2

出力例のように道しるべを置いたとき、

• 部屋 $2$ から出発した場合 $(2) \to 1$ と $1$ 回移動することになり、これが最小です。
• 部屋 $3$ から出発した場合 $(3) \to 2 \to 1$ と $2$ 回移動することになり、これが最小です。
• 部屋 $4$ から出発した場合 $(4) \to 2 \to 1$ と $2$ 回移動することになり、これが最小です。

したがって、出力例のように道しるべを置けば目標を達成できます。

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

Yes
6
5
5
1
1

答えが複数あり得る場合、どれを出力してもかまいません。