CF976F Minimal k-covering

##### 题目大意 给你一张二分图 $G = (U, V, E)$ ， $U$ 是图的 $X$ 部， $V$ 是图的 $Y$ 部， $E$ 是边集，可能有重边。 我们称 $E$ 的某个子集 $\overline E$ 是 *k-覆盖* 的，当且仅当图 $\overline G = (U, V, \overline E)$ 的每个顶点至少连接了 $k$ 条边；若 $\overline E$ 是 k-覆盖 的且不存在元素个数比它更小的边集也是 k-覆盖 的，则称 $\overline E$ 是一个 *最小k-覆盖* 。 你的任务是对于所有 $k \in [0, minDegree]$ ，求出 最小k-覆盖，其中 $minDegree$ 是图 $G$ 的所有点度数的最小值。

第一行输入三个整数 $n_1$ ， $n_2$ 和 $m$ （ $1 \le n_1, n_2 \le 2000$ ， $0 \le m \le 2000$ ），分别代表 $U$ 的点数， $V$ 的点数和边数。 接下来 $m$ 行每行两个整数 $u_i$ 和 $v_i$ ，表示第 $i$ 条边在 $U$ 中的端点为 $u_i$ ，在 $V$ 中的端点为 $v_i$ 。

输出包含 $minDegree + 1$ 行，每行首先输出一个整数 $cnt_k$ ，表示 最小k-覆盖 的边集大小，紧接着输出 $cnt_k$ 个整数，表示属于 最小k-覆盖 的边的标号。边按输入顺序从 $1$ 开始标号。输出时不必按标号从小到大输出。 感谢@OrangeLee 提供的翻译