题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

现在有 $2N$ 个彩球和 $N + 1$ 个盒子。彩球的颜色为 $1, 2, \dots, N$ 中的某一个。对于每种颜色，恰好有两个彩球被涂成该颜色。每个盒子最多可以容纳两个彩球。

最开始，第 $1$ 到第 $N$ 个盒子中每个盒子内都放有两个彩球，第 $N + 1$ 个盒子是空的。第 $i$ 个盒子中，最上面那个彩球的颜色为 $A_i$，下面那个彩球的颜色为 $B_i$。

你可以将一个盒子顶部的彩球取出，放入另一个盒子的顶部，完成一次移动操作。

你的目标是使得每种颜色的两个彩球都被放入同一个盒子中。每次移动操作必须满足下列两个条件之一：

• 被放入彩球的目标盒子是空的；
• 被放入彩球的目标盒子中恰好已有一个彩球，并且该彩球与被放入的彩球颜色相同。

请你编写程序，计算为了实现目标——使每种颜色的两个彩球在同一个盒子中，所需的最小移动次数。如果无法实现目标，请输出 $-1$。

输入格式

第一行输入一个整数 $N$。
接下来的 $N$ 行中，第 $i$ 行输入两个整数 $A_i$ 和 $B_i$，以空格分隔，表示第 $i$ 个盒子中从上到下的两个彩球的颜色。

输出格式

如果存在解决方案，输出最小的移动次数；如果不存在解决方案，输出 $-1$。

5
4 1
3 5
2 4
3 2
5 1

6

2
1 1
2 2

0

4
2 1
3 1
2 4
3 4

-1

提示

样例 1 说明

可以按照如下步骤完成：

1. 将第 4 号盒子中的颜色为 $3$ 的球移动到第 6 号盒子；
2. 将第 3 号盒子中的颜色为 $2$ 的球移动到第 4 号盒子；
3. 将第 1 号盒子中的颜色为 $4$ 的球移动到第 3 号盒子；
4. 将第 2 号盒子中的颜色为 $3$ 的球移动到第 6 号盒子；
5. 将第 5 号盒子中的颜色为 $5$ 的球移动到第 2 号盒子；
6. 将第 5 号盒子中的颜色为 $1$ 的球移动到第 1 号盒子。

约束条件

• 所有输入均为整数。
• $1 \leq N \leq 200\,000$
• $1 \leq A_i, B_i \leq N$
• 对于每个 $1 \leq i \leq N$，$A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_N$ 中恰好有两个数等于 $i$。

子问题

1. （2 分）$N \leq 2$
2. （23 分）$N \leq 20$
3. （15 分）存在使所有同色彩球放入同一盒子的方法
4. （15 分）$N \leq 2\,000$
5. （45 分）无附加限制条件

翻译由 ChatGPT-4o 完成