Description

On planet $w$, there is a plantation divided into $m \times n$ small cells (with $m$ rows in the east-west direction and $n$ columns in the north-south direction). In each cell, one root-merging plant is planted.

This plant has a special trait: its roots may extend along the north-south or east-west direction, thus merging with the plant in another cell into one.

If we tell you which pairs of cells have root-merging, can you determine how many root-merging plants there are in total in this plantation?

Input Format

The first line contains two integers $m$ and $n$, separated by spaces, representing the number of rows and columns of the grid $(1<m,n<1000)$.

The next line contains an integer $k$, indicating that there are $k$ more lines of data $(0<k<10^5)$.

The next $k$ lines each contain two integers $a$ and $b$, indicating that the cell numbered $a$ and the cell numbered $b$ have merged roots.

Cell numbers are assigned row by row, from top to bottom, and from left to right.

For example, for a $5 \times 4$ grid, the numbering is:

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16
17 18 19 20

Output Format

One line with one integer, representing the answer.

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

5

Hint

Sample Explanation

Time limit: 1 second, 256M. Lanqiao Cup 2017, the 8th National Final.

Translated by ChatGPT 5