← 返回题目列表

Codeforces · 976/F

F. 最小 k 覆盖

中文机器翻译题面 查看原题

给定一个二部图 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