CF976F.Minimal k-covering

You are given a bipartite graph G = (U, V, E), U is the set of vertices of the first part, V is the set of vertices of the second part and E is the set of edges. There might be multiple edges.

Let's call some subset of its edges k-covering iff the graph has each of its vertices incident to at least k edges. Minimal k-covering is such a k-covering that the size of the subset is minimal possible.

Your task is to find minimal k-covering for each , where minDegree is the minimal degree of any vertex in graph G.

给你一个二分图 $ G = (U, V, E) $，其中 $ U $ 是第一部分的顶点集，$ V $ 是第二部分的顶点集，$ E $ 是边集。图中可能存在重边。

我们称其某一边子集 $ \tilde{E} \subseteq E $ 为 **$ k $-覆盖**（$ k $-covering），当且仅当子图 $ \tilde{G} = (U, V, \tilde{E}) $ 中每个顶点的度数均至少为 $ k $。最小 $ k $-覆盖（minimal $ k $-covering）是指满足 $ k $-覆盖条件且边子集 $ \tilde{E} $ 的大小尽可能小的覆盖。

你的任务是：对每个 $ k = 1, 2, \dots, \text{minDegree} $，求出对应的最小 $ k $-覆盖，其中 $ \text{minDegree} $ 表示图 $ G $ 中任意顶点的最小度数。

The first line contains three integers _n_1, _n_2 and m (1 ≤ _n_1, _n_2 ≤ 2000, 0 ≤ m ≤ 2000) — the number of vertices in the first part, the number of vertices in the second part and the number of edges, respectively.

The i-th of the next m lines contain two integers u__i and v__i (1 ≤ u__i ≤ _n_1, 1 ≤ v__i ≤ _n_2) — the description of the i-th edge, u__i is the index of the vertex in the first part and v__i is the index of the vertex in the second part.

第一行包含三个整数 $n_1$、$n_2$ 和 $m$（$1 \leq n_1, n_2 \leq 2000$，$0 \leq m \leq 2000$），分别表示二分图第一部分的顶点数、第二部分的顶点数以及边的数量。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i \leq n_1$，$1 \leq v_i \leq n_2$），描述第 $i$ 条边：$u_i$ 是第一部分中顶点的编号，$v_i$ 是第二部分中顶点的编号。

For each print the subset of edges (minimal k-covering) in separate line.

The first integer cnt__k of the k-th line is the number of edges in minimal k-covering of the graph. Then cnt__k integers follow — original indices of the edges which belong to the minimal k-covering, these indices should be pairwise distinct. Edges are numbered 1 through m in order they are given in the input.

对于每个 $k$，在单独一行中输出边的子集（最小 $k$-覆盖）。

第 $k$ 行的第一个整数 $\text{cnt}_k$ 表示图的最小 $k$-覆盖中所含边的数量。随后是 $\text{cnt}_k$ 个整数——属于最小 $k$-覆盖的边的原始索引，这些索引应两两互异。边按输入顺序编号为 $1$ 至 $m$。