← 返回题目列表

Codeforces · 1012/B

B. 化学表

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

伊诺波利斯大学的科学家们继续研究元素周期表。有 n·m 个已知元素,它们形成一个元素周期表:一个 n 行 m 列的矩形。每个元素可以通过表中的坐标(r,c) (1≤r≤n,1≤c≤m)来描述。

最近科学家发现,对于这张桌子上的每四种不同元素,形成一个边长与桌子的边平行的矩形,如果他们有这四种元素中的三种元素的样本,他们可以利用核聚变产生第四种元素的样本。因此,如果我们在位置 (r1, c1)、(r1, c2)、(r2, c1) 中有元素,其中 r1 ≠ r2 且 c1 ≠ c2,那么我们可以生成元素 (r2, c2)。

融合中使用的样本不会浪费,可以在以后的融合中再次使用。新制作的元素也可以用于未来的融合。

Innopolis 大学的科学家已经拥有 q 元素的样本。他们想要获得所有n·m元素的样本。为了实现这一目标,他们将从其他实验室购买一些样品,然后按某种顺序使用任意数量的核聚变来生产所有剩余的元素。帮助他们找到需要购买的最少元素。

输入

第一行包含三个整数 n、m、q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000))、化学表维度和科学家已有的元素数量。

以下 q 行包含两个整数 ri、ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m),每个整数描述了科学家已经拥有的一个元素。输入中的所有元素都不同。

输出

打印要购买的最少元素数量。

示例

输入 #1

2 2 3
1 2
2 2
2 1

输出 #1

0

输入 #2

1 5 3
1 3
1 1
1 5

输出 #2

2

输入 #3

4 3 6
1 2
1 3
2 2
2 3
3 1
3 3

输出 #3

1

注意

对于每个示例,您都有一张说明它的图片。

每个示例的第一张图片描述了可用的初始元素样本集。黑色十字代表实验室最初可用的元素。

第二张图描述了如何获得剩余样本。红色虚线圆圈表示应从其他实验室购买的元素(最佳解决方案应尽量减少红色圆圈的数量)。蓝色虚线圆圈是可以通过核聚变产生的元素。它们按照生产顺序进行编号。

测试 1

我们可以使用核聚变并从其他三个样本中获取元素,因此我们不需要购买任何东西。

测试 2

我们根本无法使用任何核聚变,因为只有一排,所以我们必须购买所有缺失的元素。

测试 3

有几种可能的解决方案。其中之一如下图所示。

请注意,购买一个标记为红色的元素后,仍然无法立即生成底行的中间元素(标记为 4)。所以我们先生成左上角的元素(标记为1),然后在以后的融合中使用它。