F. Minimal k-covering

[{"iden":"statement","content":"给定一个二分图 #cf_span[G = (U, V, E)]，#cf_span[U] 是第一部分的顶点集合，#cf_span[V] 是第二部分的顶点集合，#cf_span[E] 是边的集合。图中可能存在重边。\n\n称图的某条边的子集为 _#cf_span[k]-覆盖_，当且仅当图中每个顶点都至少与 #cf_span[k] 条边相关联。_最小 #cf_span[k]-覆盖_ 是指边数最少的 #cf_span[k]-覆盖。\n\n你的任务是为每个 求出最小 #cf_span[k]-覆盖，其中 #cf_span[minDegree] 是图 #cf_span[G] 中任意顶点的最小度数。\n\n第一行包含三个整数 #cf_span[n1]、#cf_span[n2] 和 #cf_span[m]（#cf_span[1 ≤ n1, n2 ≤ 2000]，#cf_span[0 ≤ m ≤ 2000]），分别表示第一部分的顶点数、第二部分的顶点数和边数。\n\n接下来的 #cf_span[m] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui ≤ n1]，#cf_span[1 ≤ vi ≤ n2]），描述第 #cf_span[i] 条边，其中 #cf_span[ui] 是第一部分的顶点编号，#cf_span[vi] 是第二部分的顶点编号。\n\n对每个 ，请在单独一行中输出一个边的子集（即最小 #cf_span[k]-覆盖）。\n\n第 #cf_span[k] 行的第一个整数 #cf_span[cntk] 表示最小 #cf_span[k]-覆盖中边的数量，随后是 #cf_span[cntk] 个整数——属于该最小 #cf_span[k]-覆盖的边的原始编号，这些编号必须互不相同。边按输入顺序编号为 #cf_span[1] 到 #cf_span[m]。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n1]、#cf_span[n2] 和 #cf_span[m]（#cf_span[1 ≤ n1, n2 ≤ 2000]，#cf_span[0 ≤ m ≤ 2000]），分别表示第一部分的顶点数、第二部分的顶点数和边数。第 #cf_span[i] 行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui ≤ n1]，#cf_span[1 ≤ vi ≤ n2]），描述第 #cf_span[i] 条边，其中 #cf_span[ui] 是第一部分的顶点编号，#cf_span[vi] 是第二部分的顶点编号。"},{"iden":"output","content":"对每个 ，请在单独一行中输出一个边的子集（即最小 #cf_span[k]-覆盖）。第 #cf_span[k] 行的第一个整数 #cf_span[cntk] 表示最小 #cf_span[k]-覆盖中边的数量，随后是 #cf_span[cntk] 个整数——属于该最小 #cf_span[k]-覆盖的边的原始编号，这些编号必须互不相同。边按输入顺序编号为 #cf_span[1] 到 #cf_span[m]。"},{"iden":"examples","content":"输入\n3 3 7\n1 2\n2 3\n1 3\n3 2\n3 3\n2 1\n2 1\n输出\n0 \n3 3 7 4 \n6 1 3 6 7 4 5 \n\n输入\n1 1 5\n1 1\n1 1\n1 1\n1 1\n1 1\n输出\n0 \n1 5 \n2 4 5 \n3 3 4 5 \n4 2 3 4 5 \n5 1 2 3 4 5 "}]"

**Definitions** Let $ G = (U, V, E) $ be a bipartite graph, where: - $ U = \{u_1, \dots, u_{n_1}\} $, $ V = \{v_1, \dots, v_{n_2}\} $ are disjoint vertex sets. - $ E = \{e_1, \dots, e_m\} $ is a multiset of edges, with each $ e_j = (u_{i}, v_{\ell}) $ for some $ u_i \in U $, $ v_\ell \in V $. - Each edge $ e_j $ has a unique index $ j \in \{1, \dots, m\} $. Let $ \delta = \min_{x \in U \cup V} \deg_G(x) $ be the minimum degree of any vertex in $ G $. For $ k \in \{1, \dots, \delta\} $, a subset $ F \subseteq E $ is called a **$ k $-covering** if every vertex $ x \in U \cup V $ satisfies $ \deg_F(x) \geq k $. A **minimal $ k $-covering** is a $ k $-covering of minimum cardinality. **Constraints** 1. $ 1 \leq n_1, n_2 \leq 2000 $ 2. $ 0 \leq m \leq 2000 $ 3. For each edge $ e_j = (u_i, v_\ell) $: $ 1 \leq u_i \leq n_1 $, $ 1 \leq v_\ell \leq n_2 $ **Objective** For each $ k \in \{1, 2, \dots, \delta\} $, find a minimal $ k $-covering $ F_k \subseteq E $, and output: - The size $ |F_k| $, - The list of original edge indices $ j $ such that $ e_j \in F_k $, in any order. Output $ \delta $ lines, one for each $ k $.