题目描述

日本列岛的地壳运动十分激烈。

日本列岛的水域可以视为一个在南北方向上有 $H$ 行、在东西方向上有 $W$ 列的网格，从北到南第 $i$ 行、从西到东第 $j$ 列记为 $(i,j)$。

初始时有恰好 $N$ 个格子是陆地，其他格子均为海洋。这 $N$ 块陆地分别位于格子 $(R_1,C_1),(R_2,C_2),\ldots,(R_N,C_N)$。

日本列岛每天中午都会发生地壳运动。第 $t(t\ge 1)$ 日中午的地壳运动可以描述为如下的过程：

• 若一个格子 $(r,c)$ 满足 $1\le r\le H-1$，$1\le c\le W$ 且 $(r,c)$ 在早上（即地壳运动发生之前）为陆地、$(r+1,c)$ 在早上为海洋，那么在地壳运动发生之后，$(r+1,c)$ 也将成为陆地。

如果从任何一个为陆地的格子出发，都能通过“反复移动到东、西、南、北相邻的陆地格子”到达任何一个其他的为陆地的格子，那么称日本列岛是“连通的”。随着不断的地壳运动，日本列岛可能会在某个时候变成连通的。

判断日本列岛是否会通过若干次地壳运动变为连通的。如果可以，试求出至少需要经过几天才可以变为连通的。

输入格式

第一行输入三个整数 $H,W,N$。

接下来 $N$ 行，第 $i$ 行输入两个整数 $R_i,C_i$。

输出格式

输出一行一个整数，表示日本列岛至少需要几天才能变为连通的。如果日本列岛一开始就是连通的，输出 0；如果不可能通过地壳运动变为连通的，输出 -1。

4 4 5
1 1
1 3
3 2
3 3
4 4

2

3 3 2
1 1
3 3

-1

2 2 2
1 1
1 2

0

提示

【样例解释 #1】

下图展示了初始时日本列岛的形态（深绿色为陆地，白色为海洋）：

第 $1$ 天之后，$(2,1),(2,3),(4,2),(4,3)$ 形成新的陆地。此时日本列岛并不连通（$(1,1)$ 无法通过反复向四个方向移动到达 $(4,4)$）。下图展示了第 $1$ 天之后日本列岛的形态（深绿色为初始时的陆地，浅绿色为新形成的陆地，白色为海洋）：

第 $2$ 天之后，$(3,1)$ 形成新的陆地。此时日本列岛连通了。下图展示了第 $2$ 天之后日本列岛的形态：

日本列岛在 $2$ 次地壳运动后变为连通的。

该样例满足子任务 $3,4,5,6,7$ 的限制。

【样例解释 #2】

日本列岛无法通过地壳运动变为连通的。

该样例满足子任务 $2,3,4,5,6,7$ 的限制。

【样例解释 #3】

日本列岛在所有地壳运动之前就是连通的。

该样例满足子任务 $2,3,4,5,6,7$ 的限制。

【数据范围】

• $1 \le H,W \le 2\times 10^5$；
• $2 \le N \le \min(H \times W,\ 2\times 10^5)$；
• $1 \le R_i \le H(1\le i\le N)$；
• $1 \le C_i \le W(1\le i\le N)$；
• $(R_i, C_i) \neq (R_j, C_j) (1\le i<j\le N)$。

【子任务】

1. （$5$ 分）$W = 1$；
2. （$9$ 分）$N = 2$；
3. （$8$ 分）$H,W,N \le 500$；
4. （$28$ 分）$N \le 2000$；
5. （$13$ 分）$H \times W \le 2\times 10^5$；
6. （$13$ 分）$H \times N \le 2\times 10^5$；
7. （$24$ 分）无附加限制。