← 返回题目列表

AtCoder · abc309_d

G. 添加一条边

中文机器翻译题面 查看原题

分数: 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