题目描述

有一张 $(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$。

往后 $M$ 行，每行两个数，分别为道路的两端。

输出格式

一个数，代表答案。

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

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