P13736 [JOIGST 2025] 日本浮现 / Japan Emerges

日本列岛的地壳运动十分激烈。 日本列岛的水域可以视为一个在南北方向上有 $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`。

#### 【样例解释 #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