{"problem":{"name":"F. Minimal k-covering","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF976F"},"statements":[{"statement_type":"Markdown","content":"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.\n\nLet'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.\n\nYour task is to find minimal _k_\\-covering for each , where _minDegree_ is the minimal degree of any vertex in graph _G_.\n\n## Input\n\nThe 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.\n\nThe _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\n## Output\n\nFor each print the subset of edges (minimal _k_\\-covering) in separate line.\n\nThe 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"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 \"}]\"","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (U, V, E) $ be a bipartite graph, where:  \n- $ U = \\{u_1, \\dots, u_{n_1}\\} $, $ V = \\{v_1, \\dots, v_{n_2}\\} $ are disjoint vertex sets.  \n- $ 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 $.  \n- Each edge $ e_j $ has a unique index $ j \\in \\{1, \\dots, m\\} $.  \n\nLet $ \\delta = \\min_{x \\in U \\cup V} \\deg_G(x) $ be the minimum degree of any vertex in $ G $.  \n\nFor $ 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 $.  \nA **minimal $ k $-covering** is a $ k $-covering of minimum cardinality.\n\n**Constraints**  \n1. $ 1 \\leq n_1, n_2 \\leq 2000 $  \n2. $ 0 \\leq m \\leq 2000 $  \n3. For each edge $ e_j = (u_i, v_\\ell) $: $ 1 \\leq u_i \\leq n_1 $, $ 1 \\leq v_\\ell \\leq n_2 $  \n\n**Objective**  \nFor each $ k \\in \\{1, 2, \\dots, \\delta\\} $, find a minimal $ k $-covering $ F_k \\subseteq E $, and output:  \n- The size $ |F_k| $,  \n- The list of original edge indices $ j $ such that $ e_j \\in F_k $, in any order.  \n\nOutput $ \\delta $ lines, one for each $ k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF976F","tags":["flows","graphs"],"sample_group":[["3 3 7\n1 2\n2 3\n1 3\n3 2\n3 3\n2 1\n2 1","0 \n3 3 7 4 \n6 1 3 6 7 4 5"],["1 1 5\n1 1\n1 1\n1 1\n1 1\n1 1","0 \n1 5 \n2 4 5 \n3 3 4 5 \n4 2 3 4 5 \n5 1 2 3 4 5"]],"created_at":"2026-03-03 11:00:39"}}