← 返回题目列表

AtCoder · xmascontest2015_b

B. 破碎的圣诞树

中文机器翻译题面 查看原题

問題文

现在是圣诞节。兔子正在为圣诞晚会制作一棵圣诞树。然而,由于兔子笨手笨脚,他根本无法创造一棵树。更糟糕的是,我折断了几根属于树的树枝。聚会马上就要开始了,我得赶紧做一棵圣诞树了。

兔子想要制作的圣诞树是 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