#P5327. [Jsoi2017]魔法
[Jsoi2017]魔法
[JSOI2017] 魔法
题目描述
JYY 从朋友那里得到了一本魔法书,正在练习 JSOI 魔法。
魔法阵是一个二分图:左侧有 个点,编号为 ;右侧有 个点,编号为 。初始有 条无向边,每条边连接一个左侧点和一个右侧点。
接下来从第 轮开始,依次在第 轮加入一条边,连接左侧编号为 的点与右侧编号为 的点。
当整个二分图连通时,魔法阵被激活,添加过程停止。求激活所需添加的边数,即进行的轮数。如果初始已经连通,则为 。保证魔法阵最终一定能被激活。
输入格式
从标准输入读入。
第一行三个整数 。
接下来 行,每行两个整数 ,表示初始存在一条连接左侧 和右侧 的无向边。
输出格式
向标准输出写出一个整数,表示激活所需添加的边数。
样例
样例输入
3 5 2
1 3
2 0
样例输出
5
数据范围
,,,。