색깔 모으기

$2N$개의 공과 $N+1$개의 상자가 있다. 공의 색깔은 $1, 2, \cdots, N$ 중 하나이고, 각 색깔의 공은 정확히 $2$개씩 있다. 한 상자에는 공을 최대 $2$개까지 담을 수 있다. 처음에는 $1$번 상자부터 $N$번 상자까지 각 상자에 공이 $2$개씩 들어 있고, $N+1$번 상자는 비어 있다. $i$번 상자의 위에 있는 공의 색깔은 $A_i$이고, 아래에 있는 공의 색깔은 $B_i$이다.

한 상자에서 다른 상자로 공을 옮길 수 있다. 상자의 가장 위에 있는 공을 빼서 다른 상자의 가장 위에 넣는 작업이다.

같은 색으로 칠해진 공 2개가 같은 상자에 들어가도록 공을 옮겨야 한다. 공을 옮길 때마다 다음 두 조건 중 하나를 만족해야 한다.

• 공을 놓으려는 상자가 완전히 비어 있어야 한다.
• 공을 놓으려는 상자에 공이 정확히 하나 들어 있고, 옮기는 공과 그 상자에 있는 공의 색깔이 같아야 한다.

같은 색깔의 공이 같은 상자에 들어가도록 하는 데 필요한 공의 이동 횟수의 최솟값을 구하라.

위 그림의 경우 다음과 같이 공을 옮기면 6번의 이동으로 목표를 달성한다. 6번보다 적게 옮겨서는 목표를 달성할 수 없다.

• 4번 상자의 색깔이 3인 공을 6번 상자로 옮긴다.
• 3번 상자의 색깔이 2인 공을 4번 상자로 옮긴다.
• 1번 상자의 색깔이 4인 공을 3번 상자로 옮긴다.
• 2번 상자의 색깔이 3인 공을 6번 상자로 옮긴다.
• 5번 상자의 색깔이 5인 공을 2번 상자로 옮긴다.
• 5번 상자의 색깔이 1인 공을 1번 상자로 옮긴다.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 각 상자에 들어 있는 두 공의 색깔이 주어진다. $i$번째 줄에는 $A_i$와 $B_i$가 공백으로 구분되어 주어진다.

같은 색깔의 공이 같은 상자에 들어가도록 하는 데 필요한 공의 이동 횟수의 최솟값을 첫 번째 줄에 출력한다. 불가능하다면 $-1$을 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 \le N \le 200\,000$
• $1 \le A_i, B_i \le N$
• 각 $i$ ($1 \le i \le N$)에 대해 $A_1, \cdots, A_N, B_1, \cdots, B_N$ 중 정확히 $2$개의 값이 $i$와 같다.