CF1835F Good Graph

给定一个二分图 $G$，其顶点集合分别属于左部 $L$ 和右部 $R$，并且有 $m$ 条连接这两个部分的边。我们知道 $\left\vert{L}\right\vert = \left\vert{R}\right\vert = n。$ 对于任意子集 $S \subseteq L$，记 $N(S)$ 为 $S$ 中顶点的所有邻点的集合。如果 $G$ 中子集 $S$ 满足 $\left\vert{S}\right\vert = \left\vert{N(S)}\right\vert$，则称该子集 $S$ 是紧密的。如果对图 $G$ 中的任意子集 $S\ (S \subseteq L)$，都有 $\left\vert{S}\right\vert \le \left\vert{N(S)}\right\vert$，则称图 $G$ 是“好”的。 你的任务是验证这个图是否是“好”的，如果图是“好”的，并进行优化。如果图不“好”，则找到一个子集 $S \subseteq L$，使得 $\left\vert{S}\right\vert > \left\vert{N(S)}\right\vert$。如果图是“好”的，你的任务是找到一个“好”二分图 $G'$ 与 $L\cup R$ 拥有相同的顶点集合，其中对于任意子集 $S(S\subseteq L)$，$S$ 在 $G$ 中也是紧密的，当且仅当 $S$ 在 $G'$ 中是紧密的。如果存在多个这样的图，选择边数最少的一个。如果仍然存在多个这样的图，可以随意输出其中任意一个。

输入的第一行包含两个整数 $n$ 和 $m$ $(1\le n \le 10^3,0\le m\le n^2)$，中间用一个空格隔开。数字 $n$ 表示集合 $L$ 和集合 $R$ 中的顶点数量，而数字 $m$ 表示它们之间的边的数量。 接下来 $m$ 行描述边。每一行读入两个整数 $l$ 和 $r$ $(1\le l\le n,n+1\le r\le 2\cdot n)$，中间用空格隔开，表示 $l\in L$ 与 $r\in R$ 之间有一条边。 ### **说明/提示** 在样例一中，图 $G$ 是"好"的；因此，我们寻找一个具有相同紧密集的等价图。唯一的紧密集是 $\{1, 2, 3\}$，其在生成的图中仍然是紧密的。此外，在生成的图中没有其他集合是紧密的。可以证明不存在具有少于 $6$ 条边且具有相同紧密集的图。 在样例二中，图 $G$ 不是“好”的。集合 $\{2,3\}$ 只有一个相邻点—定点 $6$。所以，$\left\vert{\{2,3\}}\right\vert > \left\vert{\{6\}}\right\vert$，这可以证明输入的图不是“好”的。

如果输入中给定的图 $G$ 不是“好”的，则在输出的第一行输出一个单词 "NO"。在输出的第二行输出一个数字 $k$，接下来在第三行输出 $k$ 个数 $l_1,l_2,...,l_k$，两两之间用空格隔开。这 $k$ 个数表示一个集合 $S=\{l_1,l_2,...,l_k\}$，$\left\vert{s}\right\vert > \left\vert{N(S)}\right\vert$。

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 \}| > |\{ 6 \}| $ , which is a prove that the input graph is not good.