Es gibt $2N$ Kugeln und $N+1$ Kisten. Jede Kugel hat eine Farbe aus $1,2,\ldots,N$, und von jeder Farbe gibt es genau zwei Kugeln. Jede Kiste fasst höchstens zwei Kugeln. Anfangs enthalten die Kisten $1$ bis $N$ jeweils zwei Kugeln, die Kiste $N+1$ ist leer. In Kiste $i$ hat die obere Kugel die Farbe $A_i$ und die untere die Farbe $B_i$.

Man darf eine Kugel zwischen Kisten bewegen, indem man die oberste Kugel einer Kiste herausnimmt und oben in eine andere Kiste legt.

Die Kugeln sollen so bewegt werden, dass beide Kugeln jeder Farbe in derselben Kiste liegen. Jeder Zug muss eine der folgenden Bedingungen erfüllen.

• Die Zielkiste ist vollständig leer.
• Die Zielkiste enthält genau eine Kugel, deren Farbe mit der bewegten Kugel übereinstimmt.

Schreibe ein Programm, das die minimale Anzahl von Zügen bestimmt, um gleichfarbige Kugeln in derselben Kiste unterzubringen.

Zum Beispiel erreichen die folgenden Züge in der obigen Abbildung das Ziel in 6 Zügen; mit weniger als 6 Zügen ist es unmöglich.

• Bewege die Kugel der Farbe 3 aus Kiste 4 in Kiste 6.
• Bewege die Kugel der Farbe 2 aus Kiste 3 in Kiste 4.
• Bewege die Kugel der Farbe 4 aus Kiste 1 in Kiste 3.
• Bewege die Kugel der Farbe 3 aus Kiste 2 in Kiste 6.
• Bewege die Kugel der Farbe 5 aus Kiste 5 in Kiste 2.
• Bewege die Kugel der Farbe 1 aus Kiste 5 in Kiste 1.

Beschränkungen

• Alle gegebenen Zahlen sind ganzzahlig.
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• Für jedes $i$ ($1\le i\le N$) sind genau zwei Werte unter $A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ gleich $i$.

Teilaufgaben

1. (2 Punkte) $N\le2$.
2. (23 Punkte) $N\le20$.
3. (15 Punkte) Es gibt eine Möglichkeit, die Kugeln so zu bewegen, dass gleichfarbige Kugeln in derselben Kiste liegen.
4. (15 Punkte) $N\le2\,000$.
5. (45 Punkte) Keine weiteren Beschränkungen.

Eingabe

Die erste Zeile enthält $N$.

Die folgenden $N$ Zeilen geben die Farben der beiden Kugeln jeder Kiste an. Die $i$-te dieser Zeilen enthält $A_i$ und $B_i$, getrennt durch ein Leerzeichen.

Ausgabe

Gib in der ersten Zeile die minimale Anzahl von Zügen aus, um gleichfarbige Kugeln in derselben Kiste unterzubringen.

Falls dies unmöglich ist, gib $-1$ aus.

Beispiele

Eingabe 1

5
4 1
3 5
2 4
3 2
5 1

Ausgabe 1

6

Eingabe 2

2
1 1
2 2

Ausgabe 2

0

Eingabe 3

4
2 1
3 1
2 4
3 4

Ausgabe 3

-1