Innopolis University scientists continue to investigate the periodic table. There are \(n \cdot 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 \le r \le n\), \(1 \le c \le m\)) in the table. Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to sides of the table, if they have samples of three of 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 \neq r_2\) and \(c_1 \neq c_2\), then we can produce element \((r_2, c_2)\).
Original samples of elements as well as newly crafted elements can be used again in future fusions.
Innopolis University scientists already have samples of \(q\) elements. They want to obtain samples of all \(n \cdot m\) elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using arbitrary number of nuclear fusions in some order. Help them find the minimal number of elements they need to purchase.
First line contains three integers \(n\), \(m\), \(q\) (\(1 \le n, m \le 200\,000\); \(0 \le q \le \min(n \cdot m, 200\,000)\))—chemical table dimensions and the number of elements scientists already have. Following \(q\) lines contain two integers \(r_i\), \(c_i\) (\(1 \le r_i \le n\), \(1 \le c_i \le m\)) each—descriptions of the elements that scientists already have. All elements in the input are different.
In the only line print \(k\)—the minimal number of elements to be purchased.
You will get points for the subtask if you pass all tests from this subtask and all subtasks that subtask depends on.
| Constraints | |||||
|---|---|---|---|---|---|
| [0cm][0cm]Subtask | [0cm][0cm]Score | \(n\) | \(m\) | \(q\) | [0cm][0cm] Dependencies |
| 0 | 0 | — | — | — | — |
| 1 | 10 | \(n = 2\) | \(m = 2\) | \(0 \le q \le 4\) | — |
| 2 | 8 | \(n = 1\) | \(1 \le m \le 20\) | \(0 \le q \le 20\) | — |
| 3 | 9 | \(n = 2\) | \(1 \le m \le 20\) | \(0 \le q \le 40\) | 1 |
| 4 | 8 | \(1 \le n \le 20\) | \(1 \le m \le 20\) | \(q = 0\) | — |
| 5 | 20 | \(1 \le n \le 20\) | \(1 \le m \le 20\) | \(0 \le q \le 400\) | 1—4 |
| 6 | 10 | \(1 \le n \le 100\) | \(1 \le m \le 100\) | \(0 \le q \le 10\,000\) | 1—5 |
| 7 | 10 | \(1 \le n \le 250\) | \(1 \le m \le 250\) | \(0 \le q \le 62\,500\) | 1—6 |
| 8 | 10 | \(1 \le n \le 10\,000\) | \(1 \le m \le 10\,000\) | \(0 \le q \le 100\,000\) | 1—7 |
| 9 | 15 | \(1 \le n \le 200\,000\) | \(1 \le m \le 200\,000\) | \(0 \le q \le 200\,000\) | 1—8 |
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
Pictures below explain examples.
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 another labs (optimal solution should minimize number of red circles). Blue dashed circles are elements which can be produced with nuclear fusion. They are numbered starting in order in which they can be produced.
Test 1
We can use nuclear fusion and get the element from other three samples, so we don’t need to purchase anything.
Test 2
We cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.
Test 3
Note that after purchasing one element it’s still not possible to produce the middle element in the top row (marked as 4). So we produce the element in the left-bottom corner first (marked as 1), and then use it in future fusions.