题目描述
本题译自 eJOI2018 Problem D. Chemical table
Innopolis 大学的教授正努力研究元素周期表。他们知道,有 n×m 种元素,形成了一个 n 行 m 列的矩阵。
研究表明,如果元素周期表上有一个元素 A,且元素 B 与它在同一列(A 与 B 不能在同一周期),元素 C 在同一周期(A 与 C 不能在同一列),那么,科学家就可以用这三种元素通过核聚变合成第四种元素 D 的样品,D 与 B 在同一周期,与 C 在同一列。
简而言之,如果有在元素周期表中位置为 (r1, c1),(r1, c2),(r2, c1) (其中 r1=r2,c1=c2)的三种元素的样品,就可以生成位置为 (r2, c2) 的样品。如图所示:
注意:在核聚变中被使用的样品并不会消失,它们可以参与之后的反应;反应得到的样品也可以参与反应。
他们已经获得了 q 种元素的样品。为了集齐所有元素的样品,他们会购买一些样品,然后利用核聚变制造出剩下元素的样品。
请求出他们至少需要购买的元素样品的数量。
输入格式
第一行, 3 个整数 n,m,q (1 ≤ n, m ≤ 2×105;0 ≤q ≤ min{n×m, 2×105}) 。
之后的 q 行,每行 2 个整数 ri,ci (1 ≤ ri ≤ n,1 ≤ ci ≤ m) 。保证给定的元素互不相同。
输出格式
输出一个整数,表示至少需要购买的元素样品的数量。
样例 1
2 2 3
1 2
2 2
2 1
0
说明:每个样例解释中有两个矩阵。
第一个表示初始状况(其中,打叉的是原本就有样品的元素)。
第二个表示最终集齐样品时的状况(其中,蓝圈代表核聚变得到的样品,蓝圈中的数字表示得到样品的顺序,红圈表示购买的样品)。
通过给定的三种元素,可以得到第四种元素的样品。
1 5 3
1 3
1 1
1 5
2
由于给定的元素只有一行,无法使用核聚变,只能购买剩余的两种元素的样品。
4 3 6
1 2
1 3
2 2
2 3
3 1
3 3
1
集齐所有元素的方法不唯一,以下是一种方法。其中,元素 (4,2) 只有在购买元素 (4,1) 的样品,和反应得到元素 (1,1)的样品后才能得到。
数据范围与提示
注意:当且仅当你通过了一个子任务下的所有测试点,并且通过了该子任务依赖的子任务时,你将获得此子任务的分数。
子任务编号 |
分数 |
n |
m |
q |
依赖的子任务 |
1 |
0 |
样例 |
无 |
2 |
10 |
n=2 |
m=2 |
0≤q≤4 |
3 |
8 |
n=1 |
1≤m≤20 |
0≤q≤20 |
4 |
9 |
n=2 |
2 |
5 |
8 |
1≤n≤20 |
q=0 |
无 |
6 |
20 |
0≤q≤400 |
2∼5 |
7 |
10 |
1≤n≤100 |
1≤m≤100 |
0≤q≤1×104 |
2∼6 |
8 |
1≤n≤250 |
1≤m≤250 |
0≤q≤6.25×104 |
2∼7 |
9 |
1≤n≤1×104 |
1≤m≤1×104 |
1≤q≤1×105 |
2∼8 |
10 |
15 |
1≤n≤2×105 |
1≤m≤2×105 |
1≤q≤2×105 |
2∼9 |