给定一个二部图 $$$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 \}|$$$,证明输入图不好。