CF9E Interesting Graph and Apples

Hexadecimal 喜欢画画。她已经画了许多图，有有向的，也有无向的。最近，她开始制作一个静物画“有趣的图与苹果”。一个无向图被称为“有趣的”，如果它的每一个顶点只属于一个环——即“有趣环”，且不属于任何其它环。一个“有趣环”就是一个通过所有顶点一次且仅一次的环。此外，自环也被认为是有趣环。 她已经画好了苹果和图中的一些边。但现在还不清楚怎样连接剩下的顶点，使得最终结果是一个有趣的图。你需要给出添加最少数量边的答案。同时，答案应按字典序最小。边集合 $ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n}) $（其中 $ x_{i} \leq y_{i} $ ），在字典序上小于集合 $ (u_{1},v_{1}),(u_{2},v_{2}),...,(u_{n},v_{n}) $（其中 $ u_{i} \leq 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 会吃掉你……活生生地吃掉你。

输入数据的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \leq n \leq 50 $，$ 0 \leq m \leq 2500 $）——表示顶点数和边数。接下来 $ m $ 行，每行包含一对整数 $ x_{i} $ 和 $ y_{i} $（$ 1 \leq x_{i},y_{i} \leq n $）——表示已经连接的两个顶点。初始图中可能包含多重边和自环。

在第一行输出“YES”或“NO”，表示是否可以构造出一个有趣的图。如果可以，第二行输出 $ k $——表示还需添加的边的数量。接下来的 $ k $ 行，每行输出一对顶点编号 $ x_{j} $ 和 $ y_{j} $，表示需要连接的两点。结果可以包含多重边和自环。$ k $ 可能为零。

由 ChatGPT 5 翻译