A7787 | Interesting Graph and Apples

Hexadecimal likes drawing. She has drawn many graphs already, both directed and not. Recently she has started to work on a still-life «interesting graph and apples». An undirected graph is called interesting, if each of its vertices belongs to one cycle only — a funny ring — and does not belong to any other cycles. A funny ring is a cycle that goes through all the vertices just once. Moreover, loops are funny rings too.

She has already drawn the apples and some of the graph edges. But now it is not clear, how to connect the rest of the vertices to get an interesting graph as a result. The answer should contain the minimal amount of added edges. And furthermore, the answer should be the lexicographically smallest one. The set of edges $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n})$ , where $x_{i}<=y_{i}$ , is lexicographically smaller than the set $(u_{1},v_{1}),(u_{2},v_{2}),...,(u_{n},v_{n})$ , where $u_{i}<=v_{i}$ , provided that the sequence of integers $x_{1},y_{1},x_{2},y_{2},...,x_{n},y_{n}$ is lexicographically smaller than the sequence $u_{1},v_{1},u_{2},v_{2},...,u_{n},v_{n}$ . If you do not cope, Hexadecimal will eat you. ...eat you alive.

有趣的图与苹果

Hexadecimal 喜欢绘画。她已经画了许多图形，既有有向图，也有无向图。最近，她开始着手制作一幅静物画《有趣的图形和苹果》。

一个无向图被称为有趣的，如果它的每个顶点只属于一个环 —— 一个有趣的环 —— 并且不属于任何其他环。一个有趣的环是一个通过所有顶点仅一次的环。此外，环中的自环也被认为是有趣的环。

她已经画了苹果和一些图的边。但现在不清楚如何连接剩下的顶点，以便得到一个有趣的图形。答案应包含最小数量的添加边。此外，答案应该是按字典顺序最小的。

边集合 $(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)$，其中 $x_i ≤ y_i$，按字典顺序小于边集合 $(u_1, v_1), (u_2, v_2), ..., (u_n, v_n)$，其中 $u_i ≤ v_i$，前提是整数序列 $x_1, y_1, x_2, y_2, ..., x_n, y_n$ 按字典顺序小于序列 $u_1, v_1, u_2, v_2, ..., u_n, v_n$。

如果你无法解决，Hexadecimal 将会吃掉你... 生吃你。（翻译人认为：真有趣）

感谢[Macw](https://www.acgo.cn/person/929871)提供翻译

The first line of the input data contains a pair of integers $n$ and $m$ ( $1<=n<=50$ , $0<=m<=2500$ ) — the amount of vertices and edges respectively. The following lines contain pairs of numbers $x_{i}$ and $y_{i}$ ( $1<=x_{i}$ , $y_{i}<=n$ ) — the vertices that are already connected by edges. The initial graph may contain multiple edges and loops.

输入包含多行。
第一行输入两个整数 $n, k$，分别代表图中点的数量和边的数量。其中 $1 \le n \le 50, 0 \le k \le 2050$。接下来的 $k$ 行，每一行输入两个整数 $x, y$，表示图中的初始边。（请注意，图中有可能出现自环的情况）

In the first line output «YES» or «NO»: if it is possible or not to construct an interesting graph. If the answer is «YES», in the second line output $k$ — the amount of edges that should be added to the initial graph. Finally, output $k$ lines: pairs of vertices $x_{j}$ and $y_{j}$ , between which edges should be drawn. The result may contain multiple edges and loops. $k$ can be equal to zero

输出包含多行。
第一行输出YES或者NO，表示是否可以根据输入数据构造出一个有趣的图。
如果答案为YES，在第二行输出一个整数 $k$，表示需要加入到初始图的数量。
接下来的 $k$ 行，每一行输出两个整数 $x, y$，表示每一条边。（请注意，$k$可以为零）