E - 炸弹手

分数：$500$ 分

问题描述

我们有一个二维网格，大小为 $H \times W$。在这个网格上有 $M$ 个目标需要破坏，第 $i$ 个目标的位置为 $\left(h_i, w_i \right)$。

高桥想要选择一个方块，在那里放置一个炸弹并引爆。炸弹会破坏所在行和列的所有目标。可以将炸弹放在有目标的方块上。

高桥想要最大化破坏的目标数量。请找出最大可以破坏的目标数量。

约束条件

• 输入中的所有值均为整数。
• $1 \leq H, W \leq 3 \times 10^5$
• $1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)$
• $1 \leq h_i \leq H$
• $1 \leq w_i \leq W$
• $\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)$

输入

输入的格式如下：

$H$ $W$ $M$

$h_1$ $w_1$

$\vdots$

$h_M$ $w_M$

输出

输出答案。

2 3 3
2 2
1 1
1 3

3

我们可以在位置 $\left(1, 2\right)$ 放置炸弹来破坏所有目标。

3 3 4
3 3
3 1
1 1
1 2

3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

6