Time Limit : sec, Memory Limit : KB
Japanese

A: Undo Swapping

問題文

$N$ 行 $N$ 列のマス目の上に $N$ 個の石が置いてあります。 $i$ 番目の石は $R_i$ 行 $C_i$ 列にあります。同じマスに複数の石が置かれていることはありません。

あなたは次の2種類の操作を任意の順で任意の回数行うことができます。

  1. 2つの行を選び、それらを交換する
  2. 2つの列を選び、それらを交換する。

$N$ 個の石を、マス目の左上から右下にかけての対角線上に並べることが出来るかを判定するプログラムを作成してください。 可能な場合は必要な最小の操作回数を出力してください。不可能な場合は $-1$ を出力してください。

ただし、対角線上に並ぶ石の順番は関係無い ことに注意してください。 例えば、1番目の石を1行1列のマスに配置する必要はありません。

制約

  • 入力は全て整数
  • $1 \leq N \leq 10^5$
  • $1 \leq R_i, C_i \leq N$ $(1 \leq i \leq N)$
  • $R_i \ne R_j$ または $C_i \ne C_j$ $(i \ne j)$

入力

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

$N$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_N$ $C_N$

出力

問題文中の条件を満たせる場合は、必要な最小の操作回数を一行に出力してください。 不可能である場合、$-1$ を一行に出力してください。

入出力例

入力例1

3
2 1
3 2
1 3

出力例1

2

初めに列1と列3を入れ替え、次に行2と行3を入れ替えることで達成できます。 1回の操作で条件を満たすことは出来ないため、答えは2となります。

入力例2

3
1 1
1 2
3 3

出力例2

-1

入力例3

3
1 1
2 2
3 3

出力例3

0

入力例4

5
4 1
3 5
5 4
1 2
2 3

出力例4

4