Gathering Colors

There are $2N$ balls and $N+1$ boxes. Each ball is colored with one of $1, 2, \cdots, N$, and each color is used on exactly $2$ balls. Each box can hold at most $2$ balls. At the start, boxes $1$ through $N$ each contain $2$ balls, and box $N+1$ is empty. The color of the top ball in box $i$ is $A_i$, and the color of the bottom ball is $B_i$.

You can move a ball from one box to another. You remove the top ball of one box and place it on top of another box.

You must move balls so that the two balls of each color end up in the same box. Every move must satisfy one of the following two conditions.

• The box you place the ball into is completely empty.
• The box you place the ball into contains exactly one ball, and that ball has the same color as the ball you are moving.

Find the minimum number of moves needed so that balls of the same color are in the same box.

In the figure above, the following moves reach the goal in $6$ moves, and it is impossible to do it in fewer moves.

• Move the ball of color $3$ from box $4$ to box $6$.
• Move the ball of color $2$ from box $3$ to box $4$.
• Move the ball of color $4$ from box $1$ to box $3$.
• Move the ball of color $3$ from box $2$ to box $6$.
• Move the ball of color $5$ from box $5$ to box $2$.
• Move the ball of color $1$ from box $5$ to box $1$.

The first line contains $N$.

The next $N$ lines describe the two balls in each box. The $i$-th of these lines contains $A_i$ and $B_i$, separated by a space.

Print the minimum number of moves needed so that balls of the same color are in the same box. If it is impossible, print $-1$.

• All input values are integers.
• $1 \le N \le 200\,000$
• $1 \le A_i, B_i \le N$
• For each $i$ ($1 \le i \le N$), exactly $2$ of the values $A_1, \cdots, A_N, B_1, \cdots, B_N$ equal $i$.