配点 : $1800$ 点

問題文

長さ $3N$ の数列 $A, B$ が与えられます。この $2$ つの数列は、共に $1, 2, \dots, N$ をちょうど $3$ 個ずつ含みます。 言い換えると、$(1, 1, 1, 2, 2, 2, \dots, N, N, N)$ の並び替えになっています。

高橋くんは、数列 $A$ に以下の操作を好きな回数繰り返し行えます。

• $1, 2, \dots, N$ から値を一つ選び、$x$ とする。$A$ は $x$ をちょうど $3$ つ含むが、このうち 中央の要素を削除する。その後、$A$ の先頭か末尾に $x$ を追加する。

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

出力

変更可能な場合は最小の操作回数、不可能な場合は $-1$ を出力してください。

3
2 3 1 1 3 2 2 1 3
1 2 2 3 1 2 3 1 3

4

例えば以下のように操作するとよいです。

• 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$ を選び、末尾に追加)

3
1 1 1 2 2 2 3 3 3
1 1 1 2 2 2 3 3 3

0

3
2 3 3 1 1 1 2 2 3
3 2 2 1 1 1 3 3 2

-1

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

7