P15660 [ICPC 2025 Jakarta R] Two Sets

给定一个具有 $N$ 个顶点和 $M$ 条边的无向图，顶点编号从 $1$ 到 $N$。 你需要选择两个整数 $p$ 和 $q$，使得： - $N < (p + 1)(q + 1)$ - 存在一个非空顶点集合 $S_1$，满足对于每个顶点 $u \in S_1$，在 $S_1$ 中**至少**有 $p$ 个其他顶点与 $u$ 有边相连。 - 存在一个大小**至少**为 $q$ 的顶点集合 $S_2$，满足对于每个顶点 $u \in S_2$，在 $S_2$ 中没有顶点与 $u$ 有边相连。 你需要找出满足上述要求的 $p$、$q$，以及任意一组满足条件的 $S_1$ 和 $S_2$。可以证明这样的 $p$ 和 $q$ 总是存在的。

第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq 2000$；$0 \leq M \leq \min(\frac{N(N-1)}{2}, 200\;000$)）。 接下来的 $M$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u < v \leq N$），表示一条连接顶点 $u$ 和 $v$ 的边。 给定的所有边都是不同的。

第一行输出两个整数 $p$ 和 $q$。 第二行输出一个整数 $|S_1|$，后跟 $|S_1|$ 个整数，表示 $S_1$ 中的顶点编号。 第三行输出一个整数 $|S_2|$，后跟 $|S_2|$ 个整数，表示 $S_2$ 中的顶点编号。

**样例 1 解释：** 你选择了 $p = 1$，$q = 2$，$S_1 = \{1, 2\}$，以及 $S_2 = \{1, 3\}$。 翻译由 DeepSeek V3.2 完成