20220207 - 连理树

有一片mn列树林,从地上看每个格子都有一棵树,但实际上有些同行或同列相邻的树木在地下的根系是相连的,此时它们被称为连理树。若将连理树记作一棵树,这片森林有多少颗树木?

输入

第一行,有单个空格分隔的3个正整数m,n,k分别表示树林的行数、列数以及后续数据的组数。

接下来k行,每行2个正整数,表示横向或纵向相邻的格子上的两棵树在地下的根系相连。

对于100%的数据:

1 \le m,n \le 10^3

1 \le k \le 10^5

行列的编号方式为从1开始,逐行逐列,详见样例1解释。

输出

一个整数,表示树林实际有多少颗树。

样例

输入

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

提示

样例1解释:

时间限制 1000 毫秒
内存限制 128 MB
统计
上一题 下一题