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'$ 中是紧密的。如果存在多个这样的图，选择边数最少的一个。如果仍然存在多个这样的图，可以随意输出其中任意一个。

无

无

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.