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