给定一个二部图 G = (U, V, E),U 是第一部分的顶点集,V 是第二部分的顶点集,E 是边集。可能有多个边。
我们将其边的某个子集称为 $$\widetilde{E}$$ k 覆盖,当且仅当图 $${ \bar { G } } = ( U, V, { \bar { E } } )$$ 的每个顶点都关联到至少 k 个边。最小 k 覆盖是指子集 $$\widetilde{E}$$ 的大小尽可能最小的 k 覆盖。
你的任务是找到 [0..minDegree]$$ 中每个 $$k 的最小 k 覆盖,其中 minDegree 是图 G 中任何顶点的最小度数。
输入
第一行包含三个整数 n1、n2 和 m (1 ≤ n1, n2 ≤ 2000, 0 ≤ m ≤ 2000) — 分别是第一部分中的顶点数、第二部分中的顶点数和边数。
接下来 m 行的第 i 行包含两个整数 ui 和 vi (1 ≤ ui ≤ n1, 1 ≤ vi ≤ n2) — 第 i 条边的描述,ui 是第一部分中顶点的索引,vi 是第二部分中顶点的索引。
输出
对于每个 $$k \in [0..minDegree]$$ 在单独的行中打印边缘的子集(最小 k 覆盖)。
第 k 行的第一个整数 cntk 是图的最小 k 覆盖中的边数。然后是 cntk 整数 — 属于最小 k 覆盖的边的原始索引,这些索引应该是成对不同的。边按照在输入中给出的顺序编号为 1 到 m。
示例
输入 #1
3 3 7 1 2 2 3 1 3 3 2 3 3 2 1 2 1
输出 #1
0 3 3 7 4 6 1 3 6 7 4 5
输入 #2
1 1 5 1 1 1 1 1 1 1 1 1 1
输出 #2
0 1 5 2 4 5 3 3 4 5 4 2 3 4 5 5 1 2 3 4 5