该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T4 共鸣矩阵

时间限制：1 s　　内存限制：128 MB

题目描述

有一块 $n$ 行 $m$ 列的共鸣矩阵，共 $n\times m$ 个位置。我们用 $(r,c)$ 表示第 $r$ 行第 $c$ 列的位置。

矩阵满足一条共鸣规则：若三个位置

都已被激活，则位置 $(r_2,c_2)$ 会自动激活。

注意：参与共鸣的位置不会消失，可以作为其他共鸣的素材反复使用；自动激活的位置同样可以继续参与共鸣。

现在你已拥有 $q$ 个已激活的位置。你可以额外购买任意位置使其立即激活。请问：至少还要购买多少个位置，才能最终激活矩阵中的全部 $n\times m$ 个位置？

输入格式

第一行三个整数 $n,m,q$，相邻整数之间用空格分隔。

接下来 $q$ 行，每行两个整数 $r_i,c_i$，表示已激活的位置。保证给出的位置两两不同。

输出格式

输出一行一个整数，表示最少需要购买的位置数量。

样例 1

输入

2 2 3
1 2
2 2
2 1

输出

0

解释

已激活 $(1,2),(2,2),(2,1)$，恰好是矩形右上、右下、左下三个角，可直接合成左上角 $(1,1)$，无需购买。

样例 2

输入

1 5 3
1 3
1 1
1 5

输出

2

解释

只有一行，无法使用共鸣规则，只能买下缺失的 $(1,2)$ 与 $(1,4)$，共 $2$ 个。

样例 3

输入

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

输出

1

数据范围与提示

对于 $100\%$ 的数据：

• $1\le n,m\le 2\times 10^5$；
• $0\le q\le \min\{n\times m,\ 2\times 10^5\}$；
• 保证给出的已激活位置两两不同。