$2N$ 個の球と $N+1$ 個の箱がある。球の色は $1,2,\ldots,N$ のいずれかで、各色の球はちょうど 2 個ある。各箱には球を最大 2 個入れられる。最初、箱 $1$ から箱 $N$ にはそれぞれ 2 個の球が入り、箱 $N+1$ は空である。箱 $i$ の上の球の色は $A_i$、下の球の色は $B_i$ である。

ある箱の一番上の球を取り出して別の箱の一番上に置くことで、球を箱から箱へ移動できる。

同じ色の 2 個の球が同じ箱に入るように移動しなければならない。各移動では次の 2 条件のいずれかを満たす必要がある。

• 移動先の箱が完全に空である。
• 移動先に球がちょうど 1 個あり、その色が移動する球と同じである。

同じ色の球を同じ箱に入れるために必要な移動回数の最小値を求めるプログラムを作成せよ。

例えば、上図で以下のように移動すると 6 回で目標を達成でき、6 回未満では達成できない。

• 箱 4 の色 3 の球を箱 6 に移す。
• 箱 3 の色 2 の球を箱 4 に移す。
• 箱 1 の色 4 の球を箱 3 に移す。
• 箱 2 の色 3 の球を箱 6 に移す。
• 箱 5 の色 5 の球を箱 2 に移す。
• 箱 5 の色 1 の球を箱 1 に移す。

制約

• 与えられる数はすべて整数である。
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• 各 $i$（$1\le i\le N$）について、$A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ のうちちょうど 2 個が $i$ に等しい。

小課題

1. (2 点) $N\le2$.
2. (23 点) $N\le20$.
3. (15 点) 同じ色の球が同じ箱に入るように移動する方法が存在する。
4. (15 点) $N\le2\,000$.
5. (45 点) 追加の制約はない。

入力

最初の行に $N$ が与えられる。

続く $N$ 行に各箱の 2 個の球の色が与えられる。そのうち $i$ 行目には $A_i$ と $B_i$ が空白区切りで与えられる。

出力

最初の行に、同じ色の球を同じ箱に入れるために必要な移動回数の最小値を出力せよ。

不可能なら $-1$ を出力せよ。

入出力例

入力 1

5
4 1
3 5
2 4
3 2
5 1

出力 1

6

入力 2

2
1 1
2 2

出力 2

0

入力 3

4
2 1
3 1
2 4
3 4

出力 3

-1