English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
Hexadecimal 喜欢画画。她已经画了很多图，包括有向图和无向图。最近她开始创作一幅静物画「有趣的图和苹果」。一个无向图被称为有趣的，当且仅当它的每个顶点恰好属于一个环——一个有趣的环——且不属于任何其他环。一个有趣的环是一个经过所有顶点恰好一次的环。此外，自环也是有趣的环。
她已经画好了苹果和部分图的边。但现在她不清楚如何连接剩下的顶点，使得最终得到一个有趣的图。答案应包含最少数量的添加边。此外，答案还应是字典序最小的。集合 #cf_span[(x1, y1), (x2, y2), ..., (xn, yn)]，其中 #cf_span[xi ≤ yi]，比集合 #cf_span[(u1, v1), (u2, v2), ..., (un, vn)]，其中 #cf_span[ui ≤ vi]，字典序更小，当且仅当整数序列 #cf_span[x1, y1, x2, y2, ..., xn, yn] 字典序小于序列 #cf_span[u1, v1, u2, v2, ..., un, vn]。如果你无法解决，Hexadecimal 会吃掉你……活生生地吃掉你。
输入数据的第一行包含一对整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 50]，#cf_span[0 ≤ m ≤ 2500]），分别表示顶点数和边数。接下来的行包含若干对数字 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi], #cf_span[yi ≤ n]），表示已经由边连接的顶点对。初始图可能包含重边和自环。
第一行输出 «_YES_» 或 «_NO_»：表示是否可能构造出一个有趣的图。如果答案是 «_YES_»，第二行输出 #cf_span[k] —— 需要添加到初始图中的边数。最后输出 #cf_span[k] 行：每行一对顶点 #cf_span[xj] 和 #cf_span[yj]，表示应在它们之间添加一条边。结果图中可以包含重边和自环。#cf_span[k] 可以为零。
## Input
输入数据的第一行包含一对整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 50]，#cf_span[0 ≤ m ≤ 2500]），分别表示顶点数和边数。接下来的行包含若干对数字 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi], #cf_span[yi ≤ n]），表示已经由边连接的顶点对。初始图可能包含重边和自环。
## Output
第一行输出 «_YES_» 或 «_NO_»：表示是否可能构造出一个有趣的图。如果答案是 «_YES_»，第二行输出 #cf_span[k] —— 需要添加到初始图中的边数。最后输出 #cf_span[k] 行：每行一对顶点 #cf_span[xj] 和 #cf_span[yj]，表示应在它们之间添加一条边。结果图中可以包含重边和自环。#cf_span[k] 可以为零。
[samples]
**Definitions**
* Let $V = \{1, 2, \dots, n\}$ be a set of vertices.
* Let $E_{in}$ be a multiset of initial edges, where $|E_{in}| = m$. Each edge is an unordered pair $\{u, v\}$ with $u, v \in V$.
* Let $G = (V, E)$ be a multigraph. The degree of a vertex $v$, denoted $\deg_G(v)$, is the number of edge ends incident to $v$ (a self-loop $\{v, v\}$ contributes 2 to the degree).
* A graph $G$ is defined as **interesting** if every vertex $v \in V$ belongs to exactly one simple cycle. This is structurally equivalent to $G$ being a 2-regular graph:
$$ \forall v \in V, \quad \deg_G(v) = 2 $$
* An edge $e = \{x, y\}$ is represented as an ordered pair $(x, y)$ such that $x \le y$.
* A set of edges $S = \{e_1, \dots, e_k\}$ is **lexicographically smaller** than a set $S' = \{e'_1, \dots, e'_k\}$ if the sequence of ordered pairs formed by sorting $S$, $L = ((x_1, y_1), \dots, (x_k, y_k))$, is lexicographically smaller than the corresponding sequence $L'$ for $S'$.
**Input**
* Integers $n$ and $m$ such that $1 \le n \le 50$ and $0 \le m \le 2500$.
* The multiset $E_{in} = \{(x_i, y_i) \mid 1 \le i \le m\}$.
**Objective**
Find a multiset of added edges $E_{add}$ such that if $E_{final} = E_{in} \cup E_{add}$ and $G_{final} = (V, E_{final})$:
1. **Feasibility:** $G_{final}$ is an **interesting** graph.
2. **Minimality:** The cardinality $|E_{add}|$ is minimized.
3. **Lexicographical Minimality:** Among all sets satisfying (1) and (2), $E_{add}$ is the lexicographically smallest.
**Output**
1. If no such $E_{add}$ exists, output `NO`.
2. Otherwise, output `YES`, followed by the integer $k = |E_{add}|$, and the $k$ pairs of vertices representing the edges in $E_{add}$.
API Response (JSON)
{
"problem": {
"name": "E. Interesting Graph and Apples",
"description": {
"content": "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 inte",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 65536
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF9E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 inte...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Hexadecimal 喜欢画画。她已经画了很多图，包括有向图和无向图。最近她开始创作一幅静物画「有趣的图和苹果」。一个无向图被称为有趣的，当且仅当它的每个顶点恰好属于一个环——一个有趣的环——且不属于任何其他环。一个有趣的环是一个经过所有顶点恰好一次的环。此外，自环也是有趣的环。\n\n她已经画好了苹果和部分图的边。但现在她不清楚如何连接剩下的顶点，使得最终得到一个有趣的图。答案应包含最少数量的添加...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions**\n\n* Let $V = \\{1, 2, \\dots, n\\}$ be a set of vertices.\n* Let $E_{in}$ be a multiset of initial edges, where $|E_{in}| = m$. Each edge is an unordered pair $\\{u, v\\}$ with $u, v \\in ...",
"is_translate": false,
"language": "Formal"
}
]
}