Il y a $2N$ boules et $N+1$ boîtes. Chaque boule a une couleur parmi $1,2,\ldots,N$, et il y a exactement deux boules de chaque couleur. Chaque boîte peut contenir au plus deux boules. Initialement, les boîtes $1$ à $N$ contiennent chacune deux boules et la boîte $N+1$ est vide. Dans la boîte $i$, la boule du dessus a la couleur $A_i$ et celle du dessous la couleur $B_i$.

On peut déplacer une boule entre boîtes en prenant celle du dessus d’une boîte et en la plaçant au-dessus dans une autre boîte.

Vous devez déplacer les boules pour que les deux boules de chaque couleur soient dans la même boîte. Chaque déplacement doit respecter l’une des conditions suivantes.

• La boîte de destination est complètement vide.
• La boîte de destination contient exactement une boule, de la même couleur que la boule déplacée.

Écrivez un programme qui calcule le nombre minimal de déplacements pour réunir les boules de même couleur dans la même boîte.

Par exemple, les déplacements suivants dans la figure ci-dessus atteignent l’objectif en 6 déplacements ; moins de 6 ne suffisent pas.

• Déplacez la boule de couleur 3 de la boîte 4 vers la boîte 6.
• Déplacez la boule de couleur 2 de la boîte 3 vers la boîte 4.
• Déplacez la boule de couleur 4 de la boîte 1 vers la boîte 3.
• Déplacez la boule de couleur 3 de la boîte 2 vers la boîte 6.
• Déplacez la boule de couleur 5 de la boîte 5 vers la boîte 2.
• Déplacez la boule de couleur 1 de la boîte 5 vers la boîte 1.

Contraintes

• Tous les nombres donnés sont entiers.
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• Pour chaque $i$ ($1\le i\le N$), exactement deux valeurs parmi $A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ sont égales à $i$.

Sous-tâches

1. (2 points) $N\le2$.
2. (23 points) $N\le20$.
3. (15 points) Il existe une façon de déplacer les boules pour que celles de même couleur soient dans la même boîte.
4. (15 points) $N\le2\,000$.
5. (45 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient $N$.

Les $N$ lignes suivantes donnent les couleurs des deux boules de chaque boîte. La $i$-ème contient $A_i$ et $B_i$, séparés par une espace.

Sortie

Sur la première ligne, affichez le nombre minimal de déplacements pour réunir les boules de même couleur dans la même boîte.

Si c’est impossible, affichez $-1$.

Exemples

Entrée 1

5
4 1
3 5
2 4
3 2
5 1

Sortie 1

6

Entrée 2

2
1 1
2 2

Sortie 2

0

Entrée 3

4
2 1
3 1
2 4
3 4

Sortie 3

-1