题目描述

给定一个具有 $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$ 中的顶点编号。

4 2
1 2
3 4

1 2
2 1 2
2 3 1

提示

样例 1 解释： 你选择了 $p = 1$，$q = 2$，$S_1 = \{1, 2\}$，以及 $S_2 = \{1, 3\}$。

翻译由 DeepSeek V3.2 完成