配点 : 200 点
問題文
H 行 W 由 列组成的方格,每个方格的颜色为白色或黑色。
i 行目 j 在 列的方格,将方格 (i,j) 。
所有满足
黑色方块 N 可用,i 第几只黑色的马是马(x_i, y_i) 。
另外,不是黑色的剩下的 HW-N 个格子的颜色是白色的。
你可以对格子执行以下操作。
- 正整数的组 (a,b) (1 \leq a \leq H, 1 \leq b \leq W) , 1 \leq i \leq a 和 1 \leq j \leq b 满足的所有方格 (i,j) 将颜色反转(如果是白色就变为黑色,如果是黑色就变为白色)。
HW 求使所有方格变为白色所需的操作次数的最小值。
制約
- 1 \leq H,W \leq 2 \times 10^5
- 1 \leq N \leq \mathrm{min}(2 \times 10^5, H \times W)
- 1 \leq x_i \leq H
- 1 \leq y_i \leq W
- (x_i, y_i) \neq (x_j, y_j) (i \neq j)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
H W N x_1 y_1 \vdots x_N y_N
出力
将答案打印为整数。
入力例 1
2 2 2 1 2 2 1
出力例 1
2
始,质量 一块被放置在 (1,2) 和正方形 看看 (2,1) 只有黑色方块,其他是白色方块。
首先, 交换第 (a,b) = (2,1) 作为操作进行时, (1,1) 会从白色变为黑色, (2,1) 会从黑色变为白色。 输出由
接下来, (a,b) = (1,2) 作为操作进行时, (1,1) 和正方形 看看 (1,2) 会从黑色变为白色。 输出由
这样,2 操作 如果你能匹配 4 我能够将所有方块变成白色。 让它成为
入力例 2
2 4 3 1 2 1 3 2 3
出力例 2
4