E - Flip Puzzle

問題

縦 $H$ マス、横 $W$ マスのグリッドがあり、上から $p$ 番目、左から $q$ 番目のマスをマス $(p, q)$ と書きます。
$N$ 個のマスは黒色に塗られており、それぞれマス $(p_i, q_i)$ $(1 \leq i \leq N)$です。それ以外のマスは白色に塗られています。

あなたは以下の操作を好きな回数（ $0$ 回でも良い）行うことができます。

• $1$ 以上 $H-1$ 以下の整数 $x$ と、 $1$ 以上 $W-1$ 以下の整数 $y$ を好きに選ぶ。
• マス $(x, y),$ マス $(x+1, y),$ マス $(x, y+1),$ マス $(x+1, y+1)$ について、色の反転を行う。

色の反転とは、そのマスが黒色で塗られていた場合は白色に、白色で塗られていた場合は黒色に塗り替えることを指します。

あなたの目標は、グリッドの全てのマスを白色にすることです。
目標の達成に必要な最小の操作回数を求めてください。不可能ならば -1 を出力してください。

制約

• $0 \leq N \leq 2 \times 10^5$
• $2 \leq H, W \leq 2 \times 10^5$
• $1 \leq p_i \leq H$
• $1 \leq q_i \leq W$
• $i \ne j \Longrightarrow (p_i, q_i) \ne (p_j, q_j)$
• 入力は全て整数

入力

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

出力

答えを出力せよ。

サンプル 1

4 3 2
1 1
1 2
3 1
3 2

2

グリッドは始めこのようになっています。ここで、 # は黒色に塗られているマス、 . は白色に塗られているマスとします。

##
..
##

以下の操作で目標を達成できます。

• $x = 2, y = 1$ を選ぶ。グリッドは次のように変わる。

##
##
..

• $x = 1, y = 1$ を選ぶ。グリッドは次のように変わる。

..
..
..

これで目標を達成できました。これが最小の操作回数となるため、 $2$ を出力します。

サンプル 2

3 5 5
2 4
5 3
2 3

-1

このグリッドで全てのマスを白色にすることは不可能です。

サンプル 3

12 60 48
52 19
59 45
34 19
1 45
52 36
59 22
8 19
1 19
34 45
8 36
52 22
52 45

883