配点 : 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