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.

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

她已画好了苹果以及图中的一部分边。但现在尚不清楚：应如何连接剩余的顶点，才能最终得到一个“有趣的图”。答案中所添加的边数应为最少；并且，在所有满足最少边数的方案中，答案应是字典序最小的一个。
设两组边分别为 $(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)$，其中对所有 $i$ 均有 $x_i \le y_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 \leq n \leq 50$，$0 \leq m \leq 2500$），分别表示顶点数和边数。接下来的若干行每行包含一对整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq 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$ 可以为零。