← 返回题目列表

AtCoder · tupc2022_c

C. 翻转网格

中文机器翻译题面 查看原题

配点 : 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