Hay $2N$ bolas y $N+1$ cajas. Cada bola tiene un color entre $1,2,\ldots,N$, y hay exactamente dos bolas de cada color. Cada caja admite como máximo dos bolas. Inicialmente, las cajas $1$ a $N$ contienen dos bolas cada una y la caja $N+1$ está vacía. En la caja $i$, la bola superior tiene color $A_i$ y la inferior $B_i$.

Se puede mover una bola de una caja a otra sacando la bola superior de una caja y colocándola encima de las bolas de otra.

Debes mover las bolas para que las dos de cada color queden en la misma caja. Cada movimiento debe cumplir una de las dos condiciones siguientes.

• La caja de destino está completamente vacía.
• La caja de destino contiene exactamente una bola, del mismo color que la que se mueve.

Escribe un programa que calcule el mínimo número de movimientos necesarios para reunir las bolas del mismo color en una caja.

Por ejemplo, los siguientes movimientos en la figura anterior logran el objetivo en 6 movimientos, y es imposible lograrlo con menos de 6.

• Mueve la bola de color 3 de la caja 4 a la caja 6.
• Mueve la bola de color 2 de la caja 3 a la caja 4.
• Mueve la bola de color 4 de la caja 1 a la caja 3.
• Mueve la bola de color 3 de la caja 2 a la caja 6.
• Mueve la bola de color 5 de la caja 5 a la caja 2.
• Mueve la bola de color 1 de la caja 5 a la caja 1.

Restricciones

• Todos los números dados son enteros.
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• Para cada $i$ ($1\le i\le N$), exactamente dos valores entre $A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ son iguales a $i$.

Subtareas

1. (2 puntos) $N\le2$.
2. (23 puntos) $N\le20$.
3. (15 puntos) Existe una forma de mover las bolas para que las del mismo color queden en la misma caja.
4. (15 puntos) $N\le2\,000$.
5. (45 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene $N$.

Las siguientes $N$ líneas dan los colores de las dos bolas de cada caja. La $i$-ésima de ellas contiene $A_i$ y $B_i$, separados por un espacio.

Salida

En la primera línea, imprime el mínimo número de movimientos para reunir las bolas del mismo color en la misma caja.

Si es imposible, imprime $-1$.

Ejemplos

Entrada 1

5
4 1
3 5
2 4
3 2
5 1

Salida 1

6

Entrada 2

2
1 1
2 2

Salida 2

0

Entrada 3

4
2 1
3 1
2 4
3 4

Salida 3

-1