CF2062G.Permutation Factory

给定两个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$ 和 $q_1, q_2, \ldots, q_n$。每次操作中，你可以选择两个不同的整数 $1 \leq i, j \leq n$ 并交换 $p_i$ 和 $p_j$。该操作的成本为 $\min(|i - j|, |p_i - p_j|)$。

请找到使 $p_i = q_i$ 对所有 $1 \leq i \leq n$ 成立的最小总成本，并输出达成该目标的交换操作序列。

一个长度为 $n$ 的排列是由 $1$ 到 $n$ 的不同整数按任意顺序组成的数组。例如，$[2, 3, 1, 5, 4]$ 是排列，但 $[1, 2, 2]$ 不是排列（$2$ 重复出现），$[1, 3, 4]$ 也不是排列（当 $n=3$ 时出现 $4$）。

第一行输入包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例数量。

每个测试用例：

• 第一行包含一个整数 $n$（$2 \le n \le 100$）——排列 $p$ 和 $q$ 的长度。
• 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）——排列 $p$。保证 $p$ 是 $1, 2, \ldots, n$ 的排列。
• 第三行包含 $n$ 个整数 $q_1, q_2, \ldots, q_n$（$1 \leq q_i \leq n$）——排列 $q$。保证 $q$ 是 $1, 2, \ldots, n$ 的排列。

保证所有测试用例的 $n^3$ 之和不超过 $10^6$。

对于每个测试用例：

• 第一行输出操作总次数 $k$（$0 \le k \le n^2$）。
• 接下来 $k$ 行每行输出两个整数 $i, j$（$1 \le i, j \le n$，$i \neq j$），表示按顺序执行的交换操作。

可以证明最优解的操作序列长度不会超过 $n^2$。

第二个测试用例中，交换 $p_1$ 和 $p_3$ 的成本为 $\min(|1 - 3|, |1 - 3|) = 2$，此时 $p$ 等于 $q$，总成本为 $2$。

第三个测试用例中，可执行以下操作：
初始时 $p = [2, 1, 4, 3]$。

1. 交换 $p_1$ 和 $p_4$，成本 $\min(|1 - 4|, |2 - 3|) = 1$，得到 $p = [3, 1, 4, 2]$。
2. 交换 $p_2$ 和 $p_4$，成本 $\min(|2 - 4|, |1 - 2|) = 1$，得到 $p = [3, 2, 4, 1]$。
3. 交换 $p_1$ 和 $p_3$，成本 $\min(|1 - 3|, |3 - 4|) = 1$，此时 $p$ 等于 $q$，总成本为 $3$。

翻译由 DeepSeek R1 完成