题目描述

有一张 $(N_1 + N_2)$ 个点 $M$ 条边的无向图，且保证：

• 对于所有 $u, v \in [1, N_1]$，$u$ 点和 $v$ 点连通；
• 对于所有 $u, v \in [N_1 + 1, N_1+N_2]$，$u$ 点和 $v$ 点连通；
• $1$ 点和 $(N_1 + N_2)$ 点不连通。

现在你需要选择一个点 $u \in [1, N_1]$ 和一个点 $v \in [N_1 + 1, N_1+N_2]$，连接这两个点。

问连接后从 $1$ 点走到 $(N_1 + N_2)$ 点的最短路径（路径上的边数）最大是多少。

$1 \le N_1, N_2 \le 1.5 \times 10^5$，$0 \le M \le 3 \times 10^5$。

输入格式

按照下面格式输入

$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

提示

Sample Explanation 1

如果我们设置 $u=2$ 和 $v=5$ ，运算结果为 $d=5$ ，这是可能的最大值。