题目描述

在遥远的银河系，星际炼金术士联盟正为重建失落的元素矩阵而努力。这个矩阵是一个神秘的矩形结构，包含了$n \cdot m$个稀有的星际元素，每个元素以它在矩阵中的坐标$(r, c)$表示，其中$1 \leq r \leq n, 1 \leq c \leq m$。

炼金术士们发现了一个惊人的规律：如果矩阵中的四个元素组成一个边平行于矩阵边的矩形，并且他们已经拥有其中三个元素的样本，那么他们可以通过星际核聚变技术合成出剩下的第四个元素。

例如，对于矩阵中的元素$(r_1, c_1)$, $(r_1, c_2)$, $(r_2, c_1)$，如果$r_1 \neq r_2$且$c_1 \neq c_2$，他们可以合成元素$(r_2, c_2)$。

但是，星际核聚变技术需要初始样本来启动。幸运的是，炼金术士们已经从银河系的各个角落收集到了一些样本。然而，矩阵中仍有许多元素缺失。他们需要购买一些初始样本来确保能够利用核聚变技术，最终合成出整个矩阵中的所有元素。

你的任务是帮助炼金术士们计算出，他们需要最少购买多少个元素样本，才能通过核聚变合成出矩阵中的所有元素。

输入格式

第一行包含三个整数$n, m, q$，分别表示元素矩阵的行数、列数以及炼金术士们已经拥有的样本数量。 接下来的$q$行，每行包含两个整数$r_i, c_i$，表示炼金术士们已经拥有的一个元素的坐标。

• $1 \leq n, m \leq 200,000$
• $0 \leq q \leq \min(n \cdot m, 200,000)$

保证输入中的所有元素坐标互不相同。

输出格式

输出一个整数，表示炼金术士们需要最少购买的样本数量。

样例

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

说明

• 在示例 1中，通过核聚变技术，炼金术士们能够合成矩阵中缺失的所有元素，因此不需要购买额外的样本。
• 在示例 2中，由于矩阵只有一行，无法使用核聚变技术，炼金术士们只能购买所有缺失的元素。
• 在示例 3中，只需购买一个样本，其余元素均可通过核聚变合成。

通过这个题目，让我们一同踏上这段充满智慧与策略的星际炼金之旅吧！ ✨