AT_abc309_d [ABC309D] Add One Edge

题目描述

有一个包含 $N_1+N_2$ 个顶点和 $M$ 条边的无向图。对于 $i=1,2,\ldots,M$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

此外，保证以下条件成立：

• 对于所有满足 $1\leq u,v\leq N_1$ 的整数 $u,v$，顶点 $u$ 和顶点 $v$ 是连通的。
• 对于所有满足 $N_1+1\leq u,v\leq N_1+N_2$ 的整数 $u,v$，顶点 $u$ 和顶点 $v$ 是连通的。
• 顶点 $1$ 和顶点 $N_1+N_2$ 不连通。

你需要恰好进行如下操作一次：

• 选择一个满足 $1\leq u\leq N_1$ 的整数 $u$ 和一个满足 $N_1+1\leq v\leq N_1+N_2$ 的整数 $v$，并在顶点 $u$ 和顶点 $v$ 之间添加一条边。

可以证明，经过操作后，顶点 $1$ 和顶点 $N_1+N_2$ 一定连通。此时，定义顶点 $1$ 到顶点 $N_1+N_2$ 的最短路径长度（即经过的边数）为 $d$。

请你求出通过合理选择要添加的边，使得可能的 $d$ 的最大值是多少。

连通的定义：在无向图中，若存在一条路径连接顶点 $u$ 和顶点 $v$，则称 $u$ 和 $v$ 是连通的。

输入格式

输入按以下格式从标准输入读入。

$N_1$ $N_2$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 4 6
1 2
2 3
4 5
4 6
1 3
6 7

输出 #1

5

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $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$
• 若 $i\neq j$，则 $(a_i,b_i)\neq (a_j,b_j)$
• 对于所有满足 $1\leq u,v\leq N_1$ 的整数 $u,v$，顶点 $u$ 和顶点 $v$ 是连通的。
• 对于所有满足 $N_1+1\leq u,v\leq N_1+N_2$ 的整数 $u,v$，顶点 $u$ 和顶点 $v$ 是连通的。
• 顶点 $1$ 和顶点 $N_1+N_2$ 不连通。
• 输入均为整数。

样例解释 1

通过选择 $u=2,v=5$ 进行操作，可以使 $d=5$，这是可能的最大值。

由 ChatGPT 4.1 翻译