分数: 400 点
问题陈述
我们有一个无向图 (N_1+N_2) 顶点和 M 边缘。 对于 i=1,2,\ldots,M, i第一条边连接顶点 a_i 和顶点 b_i.
保证以下属性:
对于所有整数,
- 顶点 u 和顶点 v 已连接 u 和 v 与 1 \leq u,v \leq N_1.
- 顶点 u 和顶点 v 已连接 u 和 v 与 N_1+1 \leq u,v \leq N_1+N_2.
- 顶点 1 和顶点 (N_1+N_2) 已断开连接。
考虑仅执行一次以下操作:
- 选择一个整数 u 与 1 \leq u \leq N_1 和一个整数 v 与 N_1+1 \leq v \leq N_1+N_2,并添加一条连接顶点的边 u 和顶点 v.
我们可以显示该顶点 1 和顶点 (N_1+N_2) 在结果图中始终连接;所以让 d 是顶点之间路径的最小长度(边数) 1 和顶点 (N_1+N_2).
找到可能的最大值 d 通过添加适当的边来添加。
“连接”的定义
两个顶点 当且仅当顶点之间存在路径时,无向图的 u 和 v 被认为是连通的 u 和顶点 v.约束
- 1 \leq N_1,N_2 \leq 1.5 \times 10^5
- 0 \leq M \leq 3 \times 10^5
- 1 \leq a_i \leq b_i \leq N_1+N_2
- (a_i,b_i) \neq (a_j,b_j) if i \neq j.
- 顶点 u 和顶点 v 连接所有整数 u 和 v 这样 1 \leq u,v \leq N_1.
- 顶点 u 和顶点 v 连接所有整数 u 和 v 这样 N_1+1 \leq u,v \leq N_1+N_2.
- 顶点 1 和顶点 (N_1+N_2) 已断开连接。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N_1 N_2 M a_1 b_1 \vdots a_M b_M
输出
打印答案。
样本输入 1
3 4 6 1 2 2 3 4 5 4 6 1 3 6 7
示例输出 1
5
如果我们设置 u=2 和 v=5,操作产生 d=5,这是可能的最大值。

示例输入 2
7 5 20 10 11 4 5 10 12 1 2 1 5 5 6 2 4 3 5 9 10 2 5 1 4 11 12 9 12 8 9 5 7 3 7 3 6 3 4 8 12 9 11
示例输出 2
4