P12649 [KOI 2024 Round 2] 收集彩球

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

现在有 $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$。

**样例 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 完成