There are $2N$ balls and $N+1$ boxes. Each ball has a color from $1,2,\ldots,N$, and exactly two balls have each color. Each box can hold at most two balls. Initially, boxes $1$ through $N$ each contain two balls, and box $N+1$ is empty. In box $i$, the top ball has color $A_i$ and the bottom ball has color $B_i$.

You may move a ball from one box to another by taking the top ball out of one box and putting it on top of another box.

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

• The destination box is completely empty.
• The destination box contains exactly one ball, and its color is the same as that of the ball being moved.

Write a program that finds the minimum number of moves needed to put balls of the same color in the same box.

For example, the following moves in the figure above achieve this in 6 moves, and fewer than 6 moves cannot achieve the goal.

• 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.

Constraints

• All given numbers are integers.
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• For every $i$ ($1\le i\le N$), exactly two values among $A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ equal $i$.

Subtasks

1. (2 points) $N\le2$.
2. (23 points) $N\le20$.
3. (15 points) There exists a way to move the balls so that balls of the same color are in the same box.
4. (15 points) $N\le2\,000$.
5. (45 points) No additional constraints.

Input

The first line contains $N$.

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

Output

On the first line, output the minimum number of moves needed to put balls of the same color in the same box.

If this is impossible, output $-1$.

Examples

Input 1

5
4 1
3 5
2 4
3 2
5 1

Output 1

6

Input 2

2
1 1
2 2

Output 2

0

Input 3

4
2 1
3 1
2 4
3 4

Output 3

-1