有 $2N$ 個球和 $N+1$ 個盒子。每個球的顏色是 $1,2,\ldots,N$ 中的一種，每種顏色恰好有兩個球。每個盒子最多容納兩個球。最初，第 $1$ 至第 $N$ 個盒子各有兩個球，第 $N+1$ 個盒子為空。第 $i$ 個盒子中上面的球顏色為 $A_i$，下面的球顏色為 $B_i$。

可以將球從一個盒子移到另一個盒子，具體操作為取出一個盒子最上面的球，放到另一個盒子的最上面。

你需要移動球，使每種顏色的兩個球都位於同一個盒子中。每次移動必須滿足以下兩個條件之一。

• 目標盒子完全為空。
• 目標盒子中恰好有一個球，且該球的顏色與要移入的球相同。

請編寫程式，求使相同顏色的球位於同一個盒子中所需的最少移動次數。

例如，對於上圖，按下面的方法移動，可以透過 6 次移動達到目標，並且不可能透過少於 6 次移動達到目標。

• 將第 4 個盒子中顏色為 3 的球移到第 6 個盒子。
• 將第 3 個盒子中顏色為 2 的球移到第 4 個盒子。
• 將第 1 個盒子中顏色為 4 的球移到第 3 個盒子。
• 將第 2 個盒子中顏色為 3 的球移到第 6 個盒子。
• 將第 5 個盒子中顏色為 5 的球移到第 2 個盒子。
• 將第 5 個盒子中顏色為 1 的球移到第 1 個盒子。

資料範圍

• 給出的所有數均為整數。
• $1\le N\le200\,000$.
• $1\le A_i,B_i\le N$.
• 對於每個 $i$（$1\le i\le N$），$A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ 中恰好有兩個數等於 $i$。

子任務

1. (2 分) $N\le2$.
2. (23 分) $N\le20$.
3. (15 分) 存在一種移動方法，使相同顏色的球位於同一個盒子中。
4. (15 分) $N\le2\,000$.
5. (45 分) 沒有額外限制。

輸入格式

第一行給出 $N$。

接下來 $N$ 行給出每個盒子中兩個球的顏色。這些行中的第 $i$ 行給出 $A_i$ 和 $B_i$，以空格分隔。

輸出格式

第一行輸出使相同顏色的球位於同一個盒子中所需的最少移動次數。

如果無法實現，輸出 $-1$。

範例

輸入格式 1

5
4 1
3 5
2 4
3 2
5 1

輸出格式 1

6

輸入格式 2

2
1 1
2 2

輸出格式 2

0

輸入格式 3

4
2 1
3 1
2 4
3 4

輸出格式 3

-1