2023 - E. Mogu Mogu

問題

縦$H$マス、横$W$マスのグリッド上に、$N$個のおにぎりが置かれている。置かれているおにぎりの数が0個になるまで、oさんは次の操作を繰り返す。

操作：任意の1行または1列を選び、その行か列に置かれているおにぎりを食べてグリッド上から取り除く。

操作回数の最小値を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $N$
$r_1$ $c_1$
$r_2$ $c_2$
...
$r_N$ $c_N$

1行目にグリッドの大きさ$H$,$W$と、 おにぎりの数$N$が与えられる。
次の$N$行では、おにぎりの位置が与えられる。具体的には、
$i$番目($1 \leq i \leq N$)のおにぎりは上から$r_i$行目、左から$c_i$列目のグリッドに置かれている。

出力

操作回数の最小値を出力せよ。
出力の最後に改行すること。

制約

全ての入出力ケースについて以下を満たす。

• $ 1\leq H,W \leq 16$
• $ 1\leq N \leq HW$
• 同じグリッドにおにぎりが$2$個以上存在することはない。

入出力例

入力例1

3 3 3
1 1
1 2
1 3

出力例1

1

この例の状況を図示すると、次の通り。(Xがおにぎりの位置)
XXX
ooo
ooo
おにぎりを取り除く操作を1行目について行えばよい。

入力例2

3 3 5
1 2
2 1
2 2
2 3
3 2

出力例2

2

この例の状況を図示すると、次の通り。(Xがおにぎりの位置)
oXo
XXX
oXo
操作を2行目について行い、その後操作を2列目について行えばよい。

入力例3

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

出力例3

5