题目描述

有一个 $2\times n$ 的蛋糕，每个格子有一种颜色。一次操作可以选择相邻两列构成的 $2\times2$ 小方块，并将其旋转 $180^\circ$。

给出初始颜色配置和目标颜色配置，求最少操作次数；若无法达到目标配置，输出 $-1$。

输入格式

第一行整数 $z$ 表示测试组数。每组数据第一行一个整数 $n$。接下来两行给出初始配置，再接下来两行给出目标配置。每行有 $n$ 个整数，表示颜色编号。

输出格式

每组数据输出一个整数，表示最少操作次数；无解输出 $-1$。

数据范围

$1\le z\le10000$，$2\le n\le500000$，颜色编号在 $[1,10^9]$ 内，所有测试的 $n$ 之和不超过 $2\times10^6$。

样例

输入：

2
4
1 2 3 2
4 3 1 3
3 2 1 1
2 3 4 3
2
1 2
3 4
3 4
1 2

输出：

3
-1

难度评估

• 知识点：等价变换、相邻交换、逆序数。
• 思维难度：中等偏高。关键是对偶数列上下交换后，每次 $2\times2$ 旋转等价于交换相邻两列。
• 代码实现：中等，重复颜色需要用队列映射目标位置。
• CF 估分：1900。

标程

见 solutions/C_Cake.cpp。