CF1783F.Double Sort II

You are given two permutations $a$ and $b$, both of size $n$. A permutation of size $n$ is an array of $n$ elements, where each integer from $1$ to $n$ appears exactly once. The elements in each permutation are indexed from $1$ to $n$.

You can perform the following operation any number of times:

• choose an integer $i$ from $1$ to $n$;
• let $x$ be the integer such that $a_x = i$. Swap $a_i$ with $a_x$;
• let $y$ be the integer such that $b_y = i$. Swap $b_i$ with $b_y$.

Your goal is to make both permutations sorted in ascending order (i. e. the conditions $a_1 \lt a_2 \lt \dots \lt a_n$ and $b_1 \lt b_2 \lt \dots \lt b_n$ must be satisfied) using minimum number of operations. Note that both permutations must be sorted after you perform the sequence of operations you have chosen.

给你两个长度均为 $n$ 的排列 $a$ 和 $b$。长度为 $n$ 的排列是指一个包含 $n$ 个元素的数组，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。每个排列中的元素下标从 $1$ 到 $n$。

你可以执行以下操作任意多次：

• 选择一个整数 $i$，满足 $1 \le i \le n$；
• 设 $x$ 是满足 $a_x = i$ 的整数，交换 $a_i$ 与 $a_x$；
• 设 $y$ 是满足 $b_y = i$ 的整数，交换 $b_i$ 与 $b_y$。

你的目标是通过最少的操作次数，使两个排列均按升序排列（即满足 $a_1 \lt a_2 \lt \dots \lt a_n$ 且 $b_1 \lt b_2 \lt \dots \lt b_n$）。注意：在你选定的操作序列执行完毕后，两个排列都必须已排好序。

The first line contains one integer $n$ ($2 \le n \le 3000$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$; all $a_i$ are distinct).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$; all $b_i$ are distinct).

第一行包含一个整数 $n$（$2 \le n \le 3000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$；所有 $a_i$ 互不相同）。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le n$；所有 $b_i$ 互不相同）。

First, print one integer $k$ ($0 \le k \le 2n$) — the minimum number of operations required to sort both permutations. Note that it can be shown that $2n$ operations are always enough.

Then, print $k$ integers $op_1, op_2, \dots, op_k$ ($1 \le op_j \le n$), where $op_j$ is the value of $i$ you choose during the $j$-th operation.

If there are multiple answers, print any of them.

首先，输出一个整数 $k$（$0 \le k \le 2n$）—— 即对两个排列同时完成排序所需的最少操作次数。可以证明，$2n$ 次操作总是足够的。

然后，输出 $k$ 个整数 $op_1, op_2, \dots, op_k$（$1 \le op_j \le n$），其中 $op_j$ 表示第 $j$ 次操作中所选择的 $i$ 值。

若存在多个合法答案，输出任意一个即可。