分数: 1800 点
问题陈述
给出的是整数序列 A 和 B 长度 3N。这两个序列中的每一个都包含三个拷贝 1, 2, \dots, N。 换句话说, A 和 B 都是以下安排 (1, 1, 1, 2, 2, 2, \dots, N, N, N).
Tak可以对序列执行以下操作 A 任意多次:
- 从中选择一个值 1, 2, \dots, N 并调用它 x. A 恰好包含三个副本 x。删除这三个元素的中间元素。之后,追加 x 到开头或结尾 A.
检查他是否可以转弯 A 进入 B。如果可以的话,打印实现该目标所需的最少操作数。
约束
- 1 \leq N \leq 33
- A 和 B 都是以下安排 (1, 1, 1, 2, 2, 2, \dots, N, N, N).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 ... A_{3N}
B_1 B_2 ... B_{3N}
输出
如果Tak可以转弯 A 进入 B,打印实现该目标所需的最少操作数。否则,打印 -1.
示例输入 1
3 2 3 1 1 3 2 2 1 3 1 2 2 3 1 2 3 1 3
示例输出 1
4
例如,Tak 可以执行如下操作:
2 3 1 1 3 2 2 1 3(初始状态)2 2 3 1 1 3 2 1 3(选择 x = 2 并将其附加到开头)2 2 3 1 3 2 1 3 1(选择 x = 1 并将其附加到末尾)1 2 2 3 1 3 2 3 1(选择 x = 1 并将其附加到开头)1 2 2 3 1 2 3 1 3(选择 x = 3 并将其附加到末尾)
示例输入 2
3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3
示例输出 2
0
示例输入 3
3 2 3 3 1 1 1 2 2 3 3 2 2 1 1 1 3 3 2
示例输出 3
-1
示例输入 4
8 3 6 7 5 4 8 4 1 1 3 8 7 3 8 2 4 7 5 2 2 6 5 6 1 7 5 8 1 3 6 7 5 4 8 1 3 3 8 2 4 2 6 5 6 1 4 7 2
示例输出 4
7