← 返回题目列表

AtCoder · xmascon22_c

C. 有条件交换

中文机器翻译题面 查看原题

配点 : 100 点

狐狸排成一行,但在交换顺序时会关注周围。

問題文

(1,2,\ldots,N) 的置换 P=(P_1,P_2,\ldots,P_N) 和 Q=(Q_1,Q_2,\ldots,Q_N) 被给出。以下操作最多 N^2 回去 P 的 Q 判断是否能匹配,并在可能的情况下,按照 1 求出这样的操作序列。

  • 选择至少满足以下条件之一的整数 i ,并交换P_i 和 P_{i+1} 的值。
    • 1 \leq i \leq N-2 和 满足 \min(P_i,P_{i+1}) < P_{i+2} < \max(P_i,P_{i+1})
    • 2 \leq i \leq N-1 和 满足 \min(P_i,P_{i+1}) < P_{i-1} < \max(P_i,P_{i+1})

制約

  • 2 \leq N \leq 1000.
  • (P_1,P_2,\ldots,P_N) 是 由于它被视为 (1,2,\ldots,N) 的排列顺序。
  • (Q_1,Q_2,\ldots,Q_N) 是 由于它被视为 (1,2,\ldots,N) 的排列顺序。

入力

输入是按以下格式从标准输入给出的。

N
P_1 P_2 \cdots P_N
Q_1 Q_2 \cdots Q_N

出力

P 的 Q 如果可以匹配,按照以下格式输出操作序列。

k
i_1 i_2 \cdots i_k

在此,k 是操作的次数(0 \leq k \leq N^2),表示选择i_j 是 由于它被视为 j 在第 n 次操作中 i=i_j 。如果无法与

P 的 Q 匹配,则输出-1 。有


入力例 1

3
2 1 3
2 3 1

出力例 1

1
2

入力例 2

3
1 2 3
1 3 2

出力例 2

-1