← 返回题目列表

Codeforces · 1835/F

F. 好图

中文机器翻译题面 查看原题

给定一个二部图 $$$G$$$,其顶点设置在左侧部分 $$$L$$$,右侧部分 $$$R$$$,以及连接这两个集合的边 $$$m$$$。我们知道 $$$|L| =|R| = n$$$。

对于任何子集 $$$S \subseteq L$$$,设 $$$N(S)$$$ 表示 $$$S$$$ 中顶点的所有邻居的集合。我们说图 $$$G$$$ 中的子集 $$$S \subseteq L$$$ 是紧的,如果 $$$|S| = |N(S)|$$$。如果 $$$\forall_{S \subseteq L}, |S| ,我们说图 $$$G$$$ 是好的。 \leq |N(S)|$$$。

您的任务是验证图表是否良好,如果良好,则对其进行优化。如果图不好,找到一个子集 $$$S \subseteq L$$$ 使得 $$$|S| > |N(S)|$$$。然而,如果图很好,你的任务是找到一个好的二部图 $$$G'$$$,具有相同的顶点集 $$$L \cup R$$$,其中 $$$\forall_{S \subseteq L}$$$,$$$S$$$ 在 $$$G$$$ 中紧当且仅当 $$$S$$$ 在 $$$G'$$$ 中紧。如果有多个这样的图,请选择边数尽可能少的一个。如果仍有多个这样的图表,请打印其中一个。

输入

输入的第一行包含两个整数 $$$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$$$ 有一条边。

输出

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

但是,如果输入中给出的图形 $$$G$$$ 良好,则在输出的第一行中输出一个单词“YES”。在输出的第二行中,输出数字 $$$m'$$$,表示新的、也很好的图 $$$G'$$$ 中的边数。然后,在接下来的 $$$m'$$$ 行中,以与输入中给定的格式相同的格式输出图形 $$$G'$$$ 的边。

示例

输入 #1

3 8
1 4
1 5
1 6
2 4
2 5
2 6
3 5
3 6

输出 #1

YES
6
1 4
1 5
2 5
2 6
3 6
3 4

输入 #2

3 4
1 4
1 5
2 6
3 6

输出 #2

NO
2
2 3

注意

在第一个样本测试中,图形$$$G$$$很好;因此,我们正在寻找具有相同紧集的等效图。唯一的紧集是 $$$\{ 1, 2, 3 \}$$$,它在结果图中仍然是紧集。此外,结果图中没有其他集合是紧的。可以证明不存在小于 $$$6$$$ 边且具有相同紧集的图。

在第二个样本测试中,图形 $$$G$$$ 不好。集合 $$$\{ 2, 3 \}$$$ 只有一个邻居 — 顶点 $$$6$$$。因此,$$$|\{ 2, 3 \}| > |\{ 6 \}|$$$,证明输入图不好。