#5327. [Jsoi2017]魔法

内存限制:256 MiB 时间限制:10 Sec

题目描述

JYY 最近从朋友那里获得了一本魔法书,现在他正在练习里面的JSOI 魔法。JSOI 魔法施放过程是这样的:有一个
左右各有N和M个点的二分图构成一个魔法阵,左边N个点由0到N - 1标号,右边M个点由0到M - 1标号。初始时这个
二分图已经有了K个连接(每个连接相当于二分图的一条无向边)。施法分为从0 开始编号的若干轮,在第i轮中,
将会添加一条从左边编号为 i mod N 的点到右边编号为 i mod N 的点的连接。这个过程将会一直继续下去直到整
个二分图节点都能通过连接互通(即二分图连通)。此时魔法阵会被激活,JSOI 就会送你一个萌萌哒的Accept!J
YY 想知道对于给定的初始条件,魔法阵激活所需的轮数(即加入的边数)。

输入格式

第一行三个正整数N、M、K,表示二分图左边、右边的点数和初始的边数。
接下来K行,每行两个整数ui、vi。表示初始时存在从左边标号ui到右边标号vi的一个连接。
1 ≤ N,M ≤ 10^9, 0 ≤ K ≤ 10,000。

输出格式

输出一个整数,表示一共进行的轮数。JSOI 保证魔法阵一定能被激活。

样例

样例输入


			
3 5 2
1 3
2 0

样例输出


			
5

数据范围与提示