English · Original
Chinese · Translation
Formal · Original
Innopolis University scientists continue to investigate the periodic table. There are _n_·_m_ known elements and they form a periodic table: a rectangle with _n_ rows and _m_ columns. Each element can be described by its coordinates (_r_, _c_) (1 ≤ _r_ ≤ _n_, 1 ≤ _c_ ≤ _m_) in the table.
Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (_r_1, _c_1), (_r_1, _c_2), (_r_2, _c_1), where _r_1 ≠ _r_2 and _c_1 ≠ _c_2, then we can produce element (_r_2, _c_2).
<center></center>Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.
Innopolis University scientists already have samples of _q_ elements. They want to obtain samples of all _n_·_m_ elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.
## Input
The first line contains three integers _n_, _m_, _q_ (1 ≤ _n_, _m_ ≤ 200 000; 0 ≤ _q_ ≤ _min_(_n_·_m_, 200 000)), the chemical table dimensions and the number of elements scientists already have.
The following _q_ lines contain two integers _r__i_, _c__i_ (1 ≤ _r__i_ ≤ _n_, 1 ≤ _c__i_ ≤ _m_), each describes an element that scientists already have. All elements in the input are different.
## Output
Print the minimal number of elements to be purchased.
[samples]
## Note
For each example you have a picture which illustrates it.
The first picture for each example describes the initial set of element samples available. Black crosses represent elements available in the lab initially.
The second picture describes how remaining samples can be obtained. Red dashed circles denote elements that should be purchased from other labs (the optimal solution should minimize the number of red circles). Blue dashed circles are elements that can be produced with nuclear fusion. They are numbered in order in which they can be produced.
**Test 1**
We can use nuclear fusion and get the element from three other samples, so we don't need to purchase anything.
<center></center>**Test 2**
We cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.
<center></center>**Test 3**
There are several possible solutions. One of them is illustrated below.
Note that after purchasing one element marked as red it's still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.
<center></center>
Innopolis University 的科学家们正在继续研究元素周期表。目前共有 $n\cdot m$ 种已知元素，它们构成一个周期表：一个包含 $n$ 行和 $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)$。
用于聚变的样本不会被消耗，可以重复用于未来的聚变。新生成的元素也可以用于未来的聚变。
Innopolis University 的科学家们已经拥有 $q$ 种元素的样本。他们希望获得所有 $n\cdot m$ 种元素的样本。为此，他们将从其他实验室购买一些样本，然后通过任意顺序的多次核聚变生成剩余的所有元素。请帮助他们找出最少需要购买的元素数量。
第一行包含三个整数 $n$、$m$、$q$（$1\leq n,\,m\leq 200\,000$；$0\leq q\leq \min(n\cdot m,\,200\,000)$），分别表示化学表的行数、列数和科学家已有的元素数量。
接下来的 $q$ 行，每行包含两个整数 $r_i$、$c_i$（$1\leq r_i\leq n$，$1\leq c_i\leq m$），描述科学家已有的一个元素。输入中的所有元素均不相同。
请输出最少需要购买的元素数量。
每个示例都配有图示。
每个示例的第一个图描述了初始可用的元素样本集合。黑色十字表示实验室初始已有的元素。
第二个图描述了如何获取剩余样本。红色虚线圆圈表示需要从其他实验室购买的元素（最优解应最小化红色圆圈的数量）；蓝色虚线圆圈是可以用核聚变生成的元素，编号表示生成顺序。
*测试 1*
我们可以使用核聚变，通过其他三个样本获得目标元素，因此无需购买任何元素。
*测试 2*
由于只有一行，无法进行任何核聚变，因此必须购买所有缺失的元素。
*测试 3*
存在多种可能的解决方案，其中一种如下图所示。
注意：在购买一个标记为红色的元素后，仍无法立即生成底部行中间的元素（标记为 4）。因此，我们首先生成左上角的元素（标记为 1），然后在未来的聚变中使用它。
## Input
第一行包含三个整数 $n$、$m$、$q$（$1\leq n,\,m\leq 200\,000$；$0\leq q\leq \min(n\cdot m,\,200\,000)$），分别表示化学表的行数、列数和科学家已有的元素数量。接下来的 $q$ 行，每行包含两个整数 $r_i$、$c_i$（$1\leq r_i\leq n$，$1\leq c_i\leq m$），每个描述一个科学家已有的元素。输入中的所有元素均不相同。
## Output
请输出最少需要购买的元素数量。
[samples]
## Note
每个示例都配有图示。
每个示例的第一个图描述了初始可用的元素样本集合。黑色十字表示实验室初始已有的元素。
第二个图描述了如何获取剩余样本。红色虚线圆圈表示需要从其他实验室购买的元素（最优解应最小化红色圆圈的数量）；蓝色虚线圆圈是可以用核聚变生成的元素，编号表示生成顺序。
*测试 1*
我们可以使用核聚变，通过其他三个样本获得目标元素，因此无需购买任何元素。
*测试 2*
由于只有一行，无法进行任何核聚变，因此必须购买所有缺失的元素。
*测试 3*
存在多种可能的解决方案，其中一种如下图所示。
注意：在购买一个标记为红色的元素后，仍无法立即生成底部行中间的元素（标记为 4）。因此，我们首先生成左上角的元素（标记为 1），然后在未来的聚变中使用它。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of rows and columns of the periodic table.
Let $ Q \subseteq \{1, \dots, n\} \times \{1, \dots, m\} $ be the set of coordinates of elements already available, with $ |Q| = q $.
A *rectangle rule* is defined as follows: for any two distinct rows $ r_1, r_2 \in \{1, \dots, n\} $ and two distinct columns $ c_1, c_2 \in \{1, \dots, m\} $, if three of the four positions $ (r_1, c_1), (r_1, c_2), (r_2, c_1), (r_2, c_2) $ are available, then the fourth can be generated via nuclear fusion.
**Constraints**
1. $ 1 \leq n, m \leq 200{,}000 $
2. $ 0 \leq q \leq \min(nm, 200{,}000) $
3. All elements in $ Q $ are distinct.
**Objective**
Find the minimum number of elements to purchase such that, after applying the rectangle rule arbitrarily many times, all $ nm $ elements in the table can be generated.
**Key Insight (Formalized)**
Model the problem as a bipartite graph $ G = (R \cup C, E) $, where:
- $ R = \{r_1, \dots, r_n\} $ is the set of row nodes,
- $ C = \{c_1, \dots, c_m\} $ is the set of column nodes,
- An edge $ (r_i, c_j) \in E $ exists if and only if element $ (i, j) \in Q $.
The rectangle rule corresponds to the following: if there are edges $ (r_1, c_1), (r_1, c_2), (r_2, c_1) $, then edge $ (r_2, c_2) $ can be added. This is equivalent to the closure under the *bipartite clique completion* rule: if two rows share two common columns, then any missing row-column connection within the induced subgraph can be filled.
This is equivalent to the problem of computing the number of connected components in the bipartite graph.
- Initially, each connected component in $ G $ can generate all possible edges between its row and column nodes (i.e., the complete bipartite subgraph on those nodes).
- To cover the entire $ n \times m $ grid, we must have a single connected component spanning all rows and columns.
- If the bipartite graph has $ k $ connected components, then we need to add $ k - 1 $ edges (i.e., purchase $ k - 1 $ elements) to connect them all.
**Objective (Reformulated)**
Let $ k $ be the number of connected components in the bipartite graph $ G $.
Then the minimal number of elements to purchase is:
$$
k - 1
$$
API Response (JSON)
{
"problem": {
"name": "B. Chemical table",
"description": {
"content": "Innopolis University scientists continue to investigate the periodic table. There are _n_·_m_ known elements and they form a periodic table: a rectangle with _n_ rows and _m_ columns. Each element can",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1012B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Innopolis University scientists continue to investigate the periodic table. There are _n_·_m_ known elements and they form a periodic table: a rectangle with _n_ rows and _m_ columns. Each element can...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Innopolis University 的科学家们正在继续研究元素周期表。目前共有 $n\\cdot m$ 种已知元素，它们构成一个周期表：一个包含 $n$ 行和 $m$ 列的矩形。每个元素可以用其在表中的坐标 $(r,\\,c)$（其中 $1\\leq r\\leq n$，$1\\leq c\\leq m$）来描述。\n\n最近，科学家们发现，对于表中任意四个构成矩形（边与表的边平行）的不同元素，如果他们拥有...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of rows and columns of the periodic table. \nLet $ Q \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the set of coordinates of e...",
"is_translate": false,
"language": "Formal"
}
]
}