Existem $2N$ bolas e $N+1$ caixas. Cada bola tem uma cor de $1,2,\ldots,N$, e existem exatamente duas bolas de cada cor. Cada caixa comporta no máximo duas bolas. Inicialmente, as caixas $1$ a $N$ contêm duas bolas cada, e a caixa $N+1$ está vazia. Na caixa $i$, a bola de cima tem cor $A_i$ e a de baixo cor $B_i$.

Pode-se mover uma bola entre caixas retirando a bola do topo de uma caixa e colocando-a no topo de outra.

É necessário mover as bolas para que as duas de cada cor fiquem na mesma caixa. Cada movimento tem de satisfazer uma das condições seguintes.

• A caixa de destino está completamente vazia.
• A caixa de destino contém exatamente uma bola da mesma cor da bola que será movida.

Escreva um programa que calcule o menor número de movimentos necessários para reunir as bolas da mesma cor na mesma caixa.

Por exemplo, na figura acima, os movimentos seguintes atingem o objetivo em 6 movimentos, e é impossível fazê-lo com menos de 6.

• Mova a bola de cor 3 da caixa 4 para a caixa 6.
• Mova a bola de cor 2 da caixa 3 para a caixa 4.
• Mova a bola de cor 4 da caixa 1 para a caixa 3.
• Mova a bola de cor 3 da caixa 2 para a caixa 6.
• Mova a bola de cor 5 da caixa 5 para a caixa 2.
• Mova a bola de cor 1 da caixa 5 para a caixa 1.

Restrições

• Todos os números fornecidos são inteiros.
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• Para cada $i$ ($1\le i\le N$), exatamente dois valores entre $A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ são iguais a $i$.

Subtarefas

1. (2 pontos) $N\le2$.
2. (23 pontos) $N\le20$.
3. (15 pontos) Existe uma forma de mover as bolas para que as da mesma cor fiquem na mesma caixa.
4. (15 pontos) $N\le2\,000$.
5. (45 pontos) Sem restrições adicionais.

Entrada

A primeira linha contém $N$.

As próximas $N$ linhas dão as cores das duas bolas de cada caixa. A $i$-ésima dessas linhas contém $A_i$ e $B_i$, separados por um espaço.

Saída

Na primeira linha, imprima o menor número de movimentos para colocar as bolas da mesma cor na mesma caixa.

Se for impossível, imprima $-1$.

Exemplos

Entrada 1

5
4 1
3 5
2 4
3 2
5 1

Saída 1

6

Entrada 2

2
1 1
2 2

Saída 2

0

Entrada 3

4
2 1
3 1
2 4
3 4

Saída 3

-1