問題文

harurun 王国には $1\sim N$ の番号が付いた $N$ 人の男性と $1\sim M$ の番号が付いた $M$ 人の女性がいます。

国王のharurun君は 男女のペアをできるだけ多く作ろうとしています。

以下の条件を全て満たすようにペアを作ったとき、最大で何ペアできますか？

条件

• 複数のペアに同じ人が属することはできない。

• $Q$ 個の要素の配列 $a,b$ が与えられる。男性 $x$ と女性 $y$ がペアを作れるのは、$a_i=x$, $b_i=y$ となる $i$ が存在するときに限る

• 作った $i$ 番目のペアを $C_i=(x_i,y_i)$ としたとき、$i<j$ ならば $x_i<x_j$ かつ $y_i<y_j$ でなければならない。( $x_i$ は男性を、 $y_i$ は女性を表す)

入力

$N\ M\ Q$
$a_1\ b_1$
$\vdots$
$a_Q\ b_Q$

• $1$ 行目は $N$,$M$,$Q$ が空白区切りで与えられる

• $2\sim Q+1$ 行目は $a_i$,$b_i$ が空白区切りで与えられる

制約

• $1≤N,M≤10^3$

• $1≤Q≤N\times M$

• $1≤a_i≤N$

• $1≤b_i≤M$

• $i\neq j$ のとき $(a_i,b_i)\neq(a_j,b_j)$

• 入力は全て整数

出力

答えを1行に出力してください。 最後に改行してください。

サンプル

1 1 1
1 1

1

3 3 2
1 2
2 3

2

3 3 3
1 2
2 3
3 1

2