配点: 100 点
日本列岛是一个构造运动活跃的群岛。 日本列岛所在海域有南北。 H 行,東西 W 它由列网格表示。 从北方 r 行,从西边 c 列目 (1 \leqq r \leqq H,1 \leqq c \leqq W) 它被称为 (r,c) 。 每个正方形都是 陸 或 至少 海 。 最初存在于海洋中的陆地只是 N 这是一个正方形,其他的正方形都是海。 最初,这些土地的位置是 (R_1, C_1), (R_2, C_2), \dots, (R_N, C_N) 。
日本列岛每天中午都会发生地壳运动。 t 日目 (t \geqq 1) 中午发生的地壳运动表示如下。
- 1 \leqq r \leqq H-1,1 \leqq c \leqq W 出 t 当天早上的弥撒 (r, c) 是陆地上的一个正方形。 所有这些都使得 (r+1, c) 是海洋 关于 (r, c) ,质量 (r+1, c) 成为一片新土地。
如果仅通过追踪北、南、东、西彼此相邻的陆地就可以从任何陆地到达任何陆地,则日本列岛被定义为连通的。 随着地壳变形的进展,日本列岛可能会变得相连。
给定一开始的海洋面积信息,编写一个程序,判断日本列岛是否会因为反复地壳变形而连接起来,如果是的话,判断地壳变形会发生多少次才会连接起来。
入力
输入是按以下格式从标准输入给出的。
H W N R_1 C_1 R_2 C_2 \vdots R_N C_N
出力
如果要连接日本列岛,标准输出将指示需要多少次地壳运动才能连接。
输出为 1 行。
但是,如果在开头连接
输出 0 。
还有,如果将来日本列岛不连通的话, -1 。
制約
- 1 \leqq H \leqq 200\,000.
- 1 \leqq W \leqq 200\,000.
- 2 \leqq N \leqq \min(H \times W,\ 200\,000).
- 1 \leqq R_i \leqq H (1 \leqq i \leqq N).
- 1 \leqq C_i \leqq W (1 \leqq i \leqq N).
- (R_i, C_i) \neq (R_j, C_j) (1 \leqq i < j \leqq N).
- 所有输入值都是整数。
小課題
- (5 点) W = 1.
- (9 点) N = 2.
- (8 点) H \leqq 500,W \leqq 500,N \leqq 500.
- (28 点) N \leqq 2\,000.
- (13 点) H \times W \leqq 200\,000.
- (13 点) H \times N \leqq 200\,000.
- (24 点)没有额外的限制。
入力例 1
4 4 5 1 1 1 3 3 2 3 3 4 4
出力例 1
2
下图是一开始海域的情况。实心方块代表陆地,空白方块代表海洋。
1 第二次地壳变形创造了新的陆地。 (2, 1), (2, 3), (4, 2), (4, 3) 可以得到第 4 。 1 第二次地壳变形后,质量 来自 (1, 1) 到 (4, 4) 日本列岛并不相连,因为仅追踪北、南、东、西相邻的陆地是无法到达的。 下图是 1 这是第二次地壳运动后不久海洋中的情况。阴影方块现在将变成陆地,其他方块将保持不变。
2 第二次地壳变形创造了新的陆地。 (3, 1) 可以得到第 1 。 2 第一次访问后立即海域的情况如下图所示。
2 由于日本列岛在第二次地壳运动中首次相连,2 。 你只需要砍掉
此输入示例是一个小作业。 3, 4, 5, 6, 7 满足约束。
入力例 2
3 3 2 1 1 3 3
出力例 2
-1
由于日本列岛永远不会连接,-1 。
你只需要砍掉
此输入示例是一个小作业。 2, 3, 4, 5, 6, 7 满足约束。
入力例 3
2 2 2 1 1 1 2
出力例 3
0
日本列岛甚至在地壳变形发生之前就已经相连,因此0 。
你只需要砍掉
此输入示例是一个小作业。 2, 3, 4, 5, 6, 7 满足约束。