B - Broken Christmas Tree
Editorial
/
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
クリスマスの季節になった。うさぎは、クリスマスパーティをするためにクリスマスツリーを作っている。しかし、うさぎは不器用なのでまったくツリーが作成できていない。さらに悪い事に、ツリーの部品となる枝を何本か折ってしまった。もうすぐパーティが始まるため急いでクリスマスツリーを作らなければならない。
うさぎの作ろうとしているクリスマスツリーは N 頂点 N-1 辺からなる無向連結グラフである。 頂点にはそれぞれ 1 から N までの整数の番号が付いている。基本的にクリスマスツリーには任意の頂点対 (u, v) からなる辺を使って良い。 しかし、うさぎが M 本の辺を折ってしまったため、この折れた M 本の辺をクリスマスツリーに使うことはできない。
うさぎの代わりにクリスマスツリーを作ってあげて欲しい。
入力
入力は以下の形式で標準入力から与えられる。
N M p_1 q_1 p_2 q_2 : p_M q_M
- 1 行目には 2 つの整数 N, M (1 ≦ N ≦ 2 \times 10^5, 0 ≦ M ≦ 2 \times 10^5) が空白区切りで与えられる。
- 続く M 行目には 2 つの整数 p_i, q_i (1 ≦ p_i, q_i ≦ N, p_i ≠ q_i)が入力される。これは辺 (p_i, q_i) が折れている辺であることを表す。入力される M 本の折れている辺は互いに異なることが保証されている。
出力
もし、与えられた条件のもとでクリスマスツリーを作れない場合、No
と出力せよ。
そうでない場合、はじめに Yes
と出力し、次の N-1 行に整数を 2 つ空白区切りで出力せよ。出力の i+1 (1 ≦ i ≦ N-1) 行目の 2 つの整数をそれぞれ u_i, v_i とすると、これはクリスマスツリーに辺 (u_i, v_i) が使われることを表す。
条件を満たす解が複数ある場合、どれを出力しても正解となる。
入出力例
入力例 1
5 1 1 5
出力例 1
Yes 1 2 1 3 1 4 2 5
入力例 2
4 3 1 2 1 3 2 3
出力例 2
Yes 1 4 2 4 3 4
入力例 3
5 8 3 5 3 4 2 4 5 1 2 3 5 4 4 1 1 3
出力例 3
No