#P5327. [Jsoi2017]魔法

    ID: 4340 传统题 1000ms 256MiB 尝试: 25 已通过: 5 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理二分答案线性代数与代数置换循环分解构造与建模断环成链数论模逆元扩展欧几里得算法二分查找图论缩点数据结构普通并查集CF2600

[Jsoi2017]魔法

[JSOI2017] 魔法

题目描述

JYY 从朋友那里得到了一本魔法书,正在练习 JSOI 魔法。

魔法阵是一个二分图:左侧有 NN 个点,编号为 0,1,…,N−10,1,\ldots,N-1;右侧有 MM 个点,编号为 0,1,…,M−10,1,\ldots,M-1。初始有 KK 条无向边,每条边连接一个左侧点和一个右侧点。

接下来从第 00 轮开始,依次在第 ii 轮加入一条边,连接左侧编号为 i mod Ni\bmod N 的点与右侧编号为 i mod Mi\bmod M 的点。

当整个二分图连通时,魔法阵被激活,添加过程停止。求激活所需添加的边数,即进行的轮数。如果初始已经连通,则为 00。保证魔法阵最终一定能被激活。

输入格式

从标准输入读入。

第一行三个整数 N,M,KN,M,K。

接下来 KK 行,每行两个整数 ui,viu_i,v_i,表示初始存在一条连接左侧 uiu_i 和右侧 viv_i 的无向边。

输出格式

向标准输出写出一个整数,表示激活所需添加的边数。

样例

样例输入

3 5 2
1 3
2 0

样例输出

5

数据范围

1≤N,M≤1091\le N,M\le10^9,0≤K≤100000\le K\le10000,0≤ui<N0\le u_i<N,0≤vi<M0\le v_i<M。