Migrated from Lutece 2986 恩雪结婚了，懂？

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

书接上回 ——雪莉实验机，maco强烈建议你点击这里以便了解剧情[doge]

恩雪结婚了，懂？ 懂，那挺好；如果不懂，那就不必懂了。

恩佐在酝酿一个魔法阵，这个魔法阵由点和无向边构成，这个魔法阵中的点被分为两类，一类代表善良，一类代表邪恶。善恶对立，因此图中所有边的两个端点都满足：这条边的一个端点代表善良，另一个端点代表邪恶。每当恩佐施法一个点，魔法力量就会顺着这个点蔓延开来，激活与这个点相邻的所有边。被激活的边可以被再次激活，被多次激活的边与被激活一次的边都被同等地视作被激活。 只要恩佐能够成功激活图中的所有边，雪莉老师就能复活！ 每当恩佐施法一个点，他就会饱受对雪莉老师的相思之苦痛不欲生。因为maco不希望看到恩佐痛苦的样子，所以maco拜托你帮恩佐计算出最少的施法次数。

Input

第一行三个正整数 $n,m,e(1\le n\le 500,1\le m\le 500,1\le e\le 5\times 10^4)$，分别代表魔法阵中善良的点的个数，邪恶的点的个数，边数。 接下来 $e$ 行每行两个整数 $u,v$，$u,v$ 代表一条善良的点中编号为 $u$ 的点和邪恶的点中编号为 $v$ 的点之间有一条边

Output

输出一个整数，本题的答案

Samples

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

2

Resources

2023 UESTC ICPC Training for Graph