AT_abc168_d [ABC168D] .. (Double Dots)

[problemUrl]: https://atcoder.jp/contests/abc168/tasks/abc168_d あるところに、洞窟があります。 洞窟には $ N $ 個の部屋と $ M $ 本の通路があり、部屋には $ 1 $ から $ N $ の、通路には $ 1 $ から $ M $ の番号がついています。通路 $ i $ は部屋 $ A_i $ と部屋 $ B_i $ を双方向につないでいます。どの $ 2 $ 部屋間も、通路をいくつか通って行き来できます。部屋 $ 1 $ は洞窟の入り口がある特別な部屋です。 洞窟の中は薄暗いので、部屋 $ 1 $ 以外の各部屋に $ 1 $ つずつ道しるべを設けることにしました。各部屋の道しるべは、その部屋と通路で直接つながっている部屋の $ 1 $ つを指すように置きます。 洞窟の中は危険なので、部屋 $ 1 $ 以外のどの部屋についても以下の条件を満たすことが目標です。 - その部屋から出発し、「いまいる部屋にある道しるべを見て、それが指す部屋に移動する」ことを繰り返すと、部屋 $ 1 $ に最小の移動回数でたどり着く。 目標を達成できる道しるべの配置が存在するか判定し、存在するならばそのような配置を $ 1 $ つ出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ : $ $ A_M $ $ B_M $

目標を達成できる道しるべの配置が存在しなければ `No` を出力せよ。 存在する場合、$ N $ 行出力せよ。$ 1 $ 行目には `Yes` を、$ i\ (2\ \leq\ i\ \leq\ N) $ 行目には部屋 $ i $ の道しるべが指す部屋の番号を出力せよ。

### 制約 - 入力はすべて整数 - $ 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 $ 部屋間も、通路をいくつか通って行き来できる ### Sample Explanation 1 出力例のように道しるべを置いたとき、 - 部屋 $ 2 $ から出発した場合 $ (2)\ \to\ 1 $ と $ 1 $ 回移動することになり、これが最小です。 - 部屋 $ 3 $ から出発した場合 $ (3)\ \to\ 2\ \to\ 1 $ と $ 2 $ 回移動することになり、これが最小です。 - 部屋 $ 4 $ から出発した場合 $ (4)\ \to\ 2\ \to\ 1 $ と $ 2 $ 回移動することになり、これが最小です。 したがって、出力例のように道しるべを置けば目標を達成できます。 ### Sample Explanation 2 答えが複数あり得る場合、どれを出力してもかまいません。