← 返回题目列表

Codeforces · 9/E

E. 有趣的图表和苹果

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

十六进制喜欢画画。她已经画了很多图表,有向的,也有非向的。最近,她开始创作静物《有趣的图表和苹果》。如果无向图的每个顶点仅属于一个循环(有趣的环)并且不属于任何其他循环,则该无向图被称为有趣的。有趣的环是一个只经过所有顶点一次的循环。此外,循环也是有趣的环。

她已经绘制了苹果和一些图形边缘。但现在尚不清楚如何连接其余顶点以获得有趣的图。答案应该包含最少量的添加边。此外,答案应该是字典顺序上最小的答案。边集 (x1, y1), (x2, y2), ..., (xn, yn)(其中 xi ≤ yi)按字典顺序小于集合 (u1, v1), (u2, v2), ..., (un, vn)(其中 ui ≤ vi),前提是整数序列 x1, y1, x2, y2, ..., xn, yn 按字典顺序更小比序列 u1, v1, u2, v2, ..., un, vn 。如果你不应对,十六进制就会吃掉你。 ……活活吃掉你。

输入

输入数据的第一行包含一对整数 n 和 m (1 ≤ n ≤ 50, 0 ≤ m ≤ 2500) — 分别是顶点和边的数量。以下行包含数字对 xi 和 yi (1 ≤ xi, yi ≤ n) — 已通过边连接的顶点。初始图可能包含多个边和环。

输出

在第一行输出“YES”或“NO”:是否可以构建一个有趣的图表。如果答案是“是”,则在第二行中输出 k — 应添加到初始图中的边数。最后,输出 k 行:顶点对 xj 和 yj,应在它们之间绘制边。结果可能包含多个边和循环。 k可以等于0。

示例

输入 #1

3 2
1 2
2 3

输出 #1

YES
1
1 3