#PQJ124x564. QOJ 124_564
QOJ 124_564
第二轮第二试 魔法
魔法
【故事背景】
JYY 最近从朋友那里获得了一本魔法书,现在他正在练习里面的JSOI 魔法。
【问题描述】
JSOI 魔法施放过程是这样的:有一个左右各有𝑁和𝑀个点的二分图构成一个
魔法阵,左边𝑁个点由0到𝑁−1标号,右边𝑀个点由0到𝑀−1标号。初始时这个
二分图已经有了𝐾个连接(每个连接相当于二分图的一条无向边)。
施法分为从0 开始编号的若干轮,在第𝑖轮中,将会添加一条从左边编号为
𝒊 𝒎𝒐𝒅 𝑵的点到右边编号为𝒊 𝒎𝒐𝒅 𝑴的点的连接。这个过程将会一直继续下去直
到整个二分图节点都能通过连接互通(即二分图连通)。此时魔法阵会被激活,
JSOI 就会送你一个萌萌哒的Accept!
JYY 想知道对于给定的初始条件,魔法阵激活所需的轮数(即加入的边数)。
【输入格式】
从文件magic.in 中读入数据。
第一行三个正整数𝑁、𝑀、𝐾,表示二分图左边、右边的点数和初始的边数。
接下来𝐾行,每行两个整数𝑢7、𝑣7。表示初始时存在从左边标号𝑢7到右边标
号𝑣7的一个连接。
【输出格式】
输出到文件magic.out 中。
输出一个整数,表示一共进行的轮数。JSOI 保证魔法阵一定能被激活。
【样例输入】
3 5 2
1 3
2 0
【样例输出】
5
【数据规模】
对于20%的数据满足𝑁, 𝑀≤105;
对于另外20%的数据满足𝐾= 0;
对于100%的数据满足1 ≤𝑁, 𝑀≤100, 0 ≤𝐾≤10,000。