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\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 翻译