添加一条边

题目描述

我们有一个无向图,包含 $(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)$ 总是连通的;设 $d$ 为顶点 $1$ 和顶点 $(N_1+N_2)$ 之间的一条最短路径的长度(边数)。

求通过添加一条合适的边所能得到的最大可能的 $d$。

「连通」的定义:无向图的两个顶点 $u$ 和 $v$ 被称为连通的,当且仅当存在一条连接顶点 $u$ 和顶点 $v$ 的路径。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

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

5

若取 $u=2$、$v=5$,操作后得到 $d=5$,这是所能达到的最大值。

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

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)$ 不连通。
• 输入中的所有值均为整数。