CF1835F.Good Graph

You are given a bipartite graph $G$ with the vertex set in the left part $L$, in the right part $R$, and $m$ edges connecting these two sets. We know that $|L| = |R| = n$.

For any subset $S \subseteq L$, let $N(S)$ denote the set of all neighbors of vertices in $S$. We say that a subset $S \subseteq L$ in graph $G$ is tight if $|S| = |N(S)|$. We say that graph $G$ is good if $\forall_{S \subseteq L}, |S| \leq |N(S)|$.

Your task is to verify whether the graph is good and, if so, to optimize it. If the graph is not good, find a subset $S \subseteq L$ such that $|S| \gt |N(S)|$. However, if the graph is good, your task is to find a good bipartite graph $G'$ with the same set of vertices $L \cup R$, in which $\forall_{S \subseteq L}$, $S$ is tight in $G$ if and only if $S$ is tight in $G'$. If there are multiple such graphs, choose one with the smallest possible number of edges. If there are still multiple such graphs, print any.

给你一个二分图 $G$，其左部顶点集为 $L$，右部顶点集为 $R$，共有 $m$ 条连接这两个集合的边。已知 $|L| = |R| = n$。

对任意子集 $S \subseteq L$，记 $N(S)$ 为 $S$ 中所有顶点的邻点构成的集合。若 $|S| = |N(S)|$，则称子集 $S \subseteq L$ 在图 $G$ 中是紧的（tight）。若对所有 $S \subseteq L$ 均满足 $|S| \leq |N(S)|$，则称图 $G$ 是好的（good）。

你的任务是：

• 验证图 $G$ 是否为好图；
• 若图 $G$ 不是好图，则找出一个子集 $S \subseteq L$，使得 $|S| > |N(S)|$；
• 若图 $G$ 是好图，则需构造一个具有相同顶点集 $L \cup R$ 的好二分图 $G'$，使得对任意 $S \subseteq L$，$S$ 在 $G$ 中是紧的当且仅当 $S$ 在 $G'$ 中是紧的。在所有满足该条件的图中，选择边数最少的一个；若仍存在多个这样的图，则任选其一输出即可。

The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 10^3$, $0 \leq m \leq n^2$), separated by a single space. The number $n$ denotes the number of vertices in each of the sets $L$ and $R$, and the number $m$ denotes the number of edges between them.

The following $m$ lines describe the edges. Each of them contains two integers $l$ and $r$ ($1 \leq l \leq n$, $n+1 \leq r \leq 2 \cdot n$), separated by a single space, indicating that there is an edge from vertex $l \in L$ to vertex $r \in R$.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^3$，$0 \leq m \leq n^2$），由一个空格分隔。其中 $n$ 表示集合 $L$ 和 $R$ 中各自所含顶点的数量，$m$ 表示它们之间的边数。

接下来的 $m$ 行描述这些边。每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq n$，$n+1 \leq r \leq 2 \cdot n$），由一个空格分隔，表示存在一条从顶点 $l \in L$ 到顶点 $r \in R$ 的边。

If the graph $G$ given in the input is not good, output one word "NO" in the first line of the output. In the second line of the output, output the number $k$, and in the third line, output $k$ numbers $l_1, l_2, \dots, l_k$, separated by single spaces. These numbers should indicate that for the set $S = {l_1, l_2, \dots, l_k}$, $|S| \gt |N(S)|$.

However, if the graph $G$ given in the input is good, output one word "YES" in the first line of the output. In the second line of the output, output the number $m'$, indicating the number of edges in the new, also good graph $G'$. Then, in the following $m'$ lines, output the edges of the graph $G'$ in the same format as given in the input.

如果输入中给出的图 $G$ 不是好图，则在输出的第一行输出一个单词 “NO”。在输出的第二行输出数字 $k$，在第三行输出 $k$ 个数字 $l_1, l_2, \dots, l_k$，各数字之间以单个空格分隔。这些数字应表明：对于集合 $S = \{l_1, l_2, \dots, l_k\}$，有 $|S| \gt |N(S)|$。

然而，如果输入中给出的图 $G$ 是好图，则在输出的第一行输出一个单词 “YES”。在输出的第二行输出数字 $m'$，表示新图 $G'$（它也必须是好图）中的边数。随后的 $m'$ 行中，以与输入中相同的格式输出图 $G'$ 的各条边。

In the first sample test, the graph $G$ is good; thus, we are looking for an equivalent graph with the same tight sets. The only tight set is ${ 1, 2, 3 }$, which remains tight in the resulting graph. Moreover, no other set is tight in the resulting graph. One can prove that no graph with less than $6$ edges and the same tight sets exists.

In the second sample test, the graph $G$ is not good. Set ${ 2, 3 }$ has only one neighbour — vertex $6$. Thus, $|{ 2, 3 }| \gt |{ 6 }|$, which is a prove that the input graph is not good.

在第一个样例测试中，图 $G$ 是良构的；因此，我们需要寻找一个具有相同紧集的等价图。唯一的紧集是 $\{ 1, 2, 3 \}$，它在结果图中仍保持为紧集。此外，结果图中不存在其他紧集。可以证明：不存在边数少于 $6$ 且具有相同紧集的图。

在第二个样例测试中，图 $G$ 不是良构的。集合 $\{ 2, 3 \}$ 仅有一个邻点——顶点 $6$。因此，$|\{ 2, 3 \}| > |\{ 6 \}|$，这证明了输入图不是良构的。