Flipping Puzzle

問題文

縦 $H$ 行 横 $W$ 列のグリッドがあります。上から $i$ 番目、左から $j$ 番目のマスを $(i, j)$ と表します。
$N$ 個のマスの色は黒であり、それぞれ $(r_k, c_k) ~ (1 \le k \le N)$ です。それ以外のマスの色は白です。

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

• グリッド上に含まれる $2 \times 2$ の矩形領域を選ぶ。その中に含まれる $4$ つのマスの色を反転する。

色を反転するとは、そのマスの色が黒であるとき白に、そうでないとき黒に色を変更することを表します。

グリッドのすべてのマスの色を白にすることが可能か判定し、可能ならば必要な操作回数の最小値を求めてください。

制約

• $0 \le N \le 5 \times 10^5$
• $2 \le H, W \le 5 \times 10^5$
• $1 \le r_k \le H$
• $1 \le c_k \le W$
• $(r_k, c_k) \ne (r_{k'}, c_{k'}) \enspace (k \ne k')$
• 入力される値はすべて整数

入力

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

出力

グリッドのすべてのマスの色を白にすることが不可能であるとき -1 を出力せよ。
可能であるとき、必要な操作回数の最小値を出力せよ。

サンプル 1

入力

4 3 2
1 1
1 2
3 1
3 2

出力

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