伊诺波利斯大学的科学家们继续研究元素周期表。有 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),然后在以后的融合中使用它。