配点 : $500$ 点

問題文

$H \times W$ マスの二次元グリッドがあります。この中には $M$ 個の爆破対象があります。 $i$ 個目の爆破対象の位置は $\left(h_i, w_i \right)$です。

高橋君は $1$ つのマスを選び、そのマスに爆弾を設置し、起爆します。爆弾と同じ行または同じ列に存在する爆破対象が爆破されます。爆破対象が存在するマスに爆弾を設置することも出来ます。

高橋君は、爆破する爆破対象の数を最大化しようとしています。最大でいくつの爆破対象を爆破出来るか答えてください。

制約

• 入力は全て整数
• $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