CF9E.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.

十六进制喜欢画画。她已经画出了许多图，包括有向图和无向图。最近，她开始创作一幅静物画——《有趣的图与苹果》。一个无向图被称为“有趣的”，当且仅当它的每个顶点恰好属于唯一一个环（即一个“有趣的环”），且不属于任何其他环。“有趣的环”是指恰好经过每个顶点一次的环；此外，自环（loop）也被视为“有趣的环”。

她已画好了苹果以及图中的一部分边。但现在还不清楚该如何连接剩余的顶点，才能最终得到一个“有趣的图”。答案需满足：所添加的边数最少；并且，在所有满足边数最少的方案中，所选边集应为字典序最小者。设边集为 $(x_1,\,y_1),\,(x_2,\,y_2),\,\dots,\,(x_n,\,y_n)$，其中对所有 $i$ 均有 $x_i \le y_i$；另一边集为 $(u_1,\,v_1),\,(u_2,\,v_2),\,\dots,\,(u_n,\,v_n)$，其中对所有 $i$ 均有 $u_i \le v_i$。则前者字典序小于后者，当且仅当整数序列 $x_1,\,y_1,\,x_2,\,y_2,\,\dots,\,x_n,\,y_n$ 的字典序小于序列 $u_1,\,v_1,\,u_2,\,v_2,\,\dots,\,u_n,\,v_n$。若你无法解决此题，十六进制将吃掉你……活生生地吃掉你。

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$ 和 $m$（$1 ≤ n ≤ 50$，$0 ≤ m ≤ 2500$），分别表示顶点数和边数。接下来的若干行每行包含一对数字 $x_i$ 和 $y_i$（$1 ≤ x_i, y_i ≤ n$），表示已由边连接的顶点。初始图可能包含重边和自环。

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_j$ 和 $y_j$，表示应在它们之间添加一条边。结果中允许存在重边和自环。$k$ 可以为零。