有 $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