Jest $2N$ kul i $N+1$ pudełek. Każda kula ma kolor z zakresu $1,2,\ldots,N$, a każdego koloru są dokładnie dwie kule. Pudełko mieści najwyżej dwie kule. Początkowo pudełka od $1$ do $N$ zawierają po dwie kule, a pudełko $N+1$ jest puste. W pudełku $i$ górna kula ma kolor $A_i$, a dolna $B_i$.

Można przenieść kulę z jednego pudełka do drugiego, wyjmując górną kulę i umieszczając ją na wierzchu drugiego pudełka.

Należy przenieść kule tak, aby dwie kule każdego koloru znalazły się w tym samym pudełku. Każdy ruch musi spełniać jeden z poniższych warunków.

• Pudełko docelowe jest całkowicie puste.
• Pudełko docelowe zawiera dokładnie jedną kulę tego samego koloru co przenoszona kula.

Napisz program obliczający minimalną liczbę ruchów potrzebnych do umieszczenia kul tego samego koloru w jednym pudełku.

Na przykład na powyższym rysunku następujące ruchy osiągają cel w 6 ruchach; mniej niż 6 ruchów nie wystarczy.

• Przenieś kulę koloru 3 z pudełka 4 do pudełka 6.
• Przenieś kulę koloru 2 z pudełka 3 do pudełka 4.
• Przenieś kulę koloru 4 z pudełka 1 do pudełka 3.
• Przenieś kulę koloru 3 z pudełka 2 do pudełka 6.
• Przenieś kulę koloru 5 z pudełka 5 do pudełka 2.
• Przenieś kulę koloru 1 z pudełka 5 do pudełka 1.

Ograniczenia

• Wszystkie podane liczby są całkowite.
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• Dla każdego $i$ ($1\le i\le N$) dokładnie dwie wartości spośród $A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ są równe $i$.

Podzadania

1. (2 pkt) $N\le2$.
2. (23 pkt) $N\le20$.
3. (15 pkt) Istnieje sposób przeniesienia kul tak, aby kule tego samego koloru znalazły się w tym samym pudełku.
4. (15 pkt) $N\le2\,000$.
5. (45 pkt) Brak dodatkowych ograniczeń.

Wejście

Pierwszy wiersz zawiera $N$.

Kolejne $N$ wierszy podaje kolory dwóch kul w każdym pudełku. W $i$-tym z nich podane są $A_i$ i $B_i$, oddzielone spacją.

Wyjście

W pierwszym wierszu wypisz minimalną liczbę ruchów potrzebnych do umieszczenia kul tego samego koloru w tym samym pudełku.

Jeśli jest to niemożliwe, wypisz $-1$.

Przykład

Wejście 1

5
4 1
3 5
2 4
3 2
5 1

Wyjście 1

6

Wejście 2

2
1 1
2 2

Wyjście 2

0

Wejście 3

4
2 1
3 1
2 4
3 4

Wyjście 3

-1