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