CF1918B.Minimize Inversions

You are given two permutations $a$ and $b$ of length $n$. A permutation is an array of $n$ elements from $1$ to $n$ where all elements are distinct. For example, an array [$2,1,3$] is a permutation, but [$0,1$] and [$1,3,1$] aren't.

You can (as many times as you want) choose two indices $i$ and $j$, then swap $a_i$ with $a_j$ and $b_i$ with $b_j$ simultaneously.

You hate inversions, so you want to minimize the total number of inversions in both permutations.

An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i \lt j$ and $p_i \gt p_j$. For example, if $p=[3,1,4,2,5]$ then there are $3$ inversions in it (the pairs of indices are $(1,2)$, $(1,4)$ and $(3,4)$).

给你两个长度为 $n$ 的排列 $a$ 和 $b$。排列是指由 $1$ 到 $n$ 中的 $n$ 个互不相同的数组成的数组。例如，数组 $[2,1,3]$ 是一个排列，但 $[0,1]$ 和 $[1,3,1]$ 不是。

你可以（任意多次）选择两个下标 $i$ 和 $j$，然后同时交换 $a_i$ 与 $a_j$，以及 $b_i$ 与 $b_j$。

你讨厌逆序对，因此希望最小化两个排列中逆序对的总数。

在排列 $p$ 中，一个逆序对是指一对下标 $(i, j)$，满足 $i \lt j$ 且 $p_i \gt p_j$。例如，若 $p=[3,1,4,2,5]$，则其中包含 $3$ 个逆序对（对应下标对为 $(1,2)$、$(1,4)$ 和 $(3,4)$）。

The first line contains an integer $t$ ($1 \leq t \leq 20\,000$) — the number of test cases.

Each test case consists of three lines. The first line contains an integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the permutations $a$ and $b$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — permutation $a$. The third line contains $b$ in a similar format.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 20\,000$）—— 测试用例的数量。

每个测试用例由三行组成。第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot10^5$）—— 排列 $a$ 和 $b$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）—— 排列 $a$。第三行以类似格式给出排列 $b$。

保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

For each test case, output two permutations $a'$ and $b'$ (in the same format as in the input) — the permutations after all operations. The total number of inversions in $a'$ and $b'$ should be the minimum possible among all pairs of permutations that can be obtained using operations from the statement.

If there are multiple solutions, print any of them.

对于每个测试用例，输出两个排列 $a'$ 和 $b'$（格式与输入中相同）——即执行完所有操作后的排列。$a'$ 和 $b'$ 中的逆序对总数应在所有可通过题目所述操作得到的排列对中达到最小值。

若存在多个解，输出任意一个即可。

In the first test case, the minimum possible number of inversions is $10$.

In the second test case, we can sort both permutations at the same time. For this, the following operations can be done:

• Swap the elements in the positions $1$ and $3$ in both permutations. After the operation, $a =$ [$2,1,3$], $b =$ [$2,1,3$].
• Swap the elements in the positions $1$ and $2$. After the operations, $a$ and $b$ are sorted.

In the third test case, the minimum possible number of inversions is $7$.

在第一个测试用例中，最少可能的逆序对数量为 $10$。

在第二个测试用例中，我们可以同时将两个排列排序。为此，可执行以下操作：

• 同时在两个排列中交换位置 $1$ 和 $3$ 上的元素。操作后，$a = [2,1,3]$，$b = [2,1,3]$。
• 交换位置 $1$ 和 $2$ 上的元素。操作后，$a$ 和 $b$ 均已排序。

在第三个测试用例中，最少可能的逆序对数量为 $7$。