题目描述

塔尖岛的水域可以视为一个有 $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$ 次地壳运动后变为连通的。

数据范围

对于 $100\%$ 的数据满足：$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 c_i \le w$。所有陆地的位置互不相同。

• 子任务 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$ 分）无附加限制。