题目描述

给定两个长度为 $n$ 的排列 $a$ 和 $b$。排列是一个长度为 $n$ 的数组，包含 $1$ 到 $n$ 的所有不同元素。例如，数组 $[2,1,3]$ 是一个排列，但 $[0,1]$ 和 $[1,3,1]$ 不是。

你可以进行任意多次如下操作：选择两个下标 $i$ 和 $j$，同时交换 $a_i$ 与 $a_j$，以及 $b_i$ 与 $b_j$。

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

在排列 $p$ 中，逆序对是满足 $i < j$ 且 $p_i > p_j$ 的一对下标 $(i, j)$。例如，如果 $p=[3,1,4,2,5]$，则其中有 $3$ 个逆序对（下标对为 $(1,2)$、$(1,4)$ 和 $(3,4)$）。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 20000$）——表示测试用例的数量。

每个测试用例包含三行。第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）——表示排列 $a$ 和 $b$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）——排列 $a$。第三行以相同格式给出排列 $b$。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

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

如果有多组解，输出任意一组均可。

说明/提示

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

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

• 同时交换两个排列中第 $1$ 和第 $3$ 个元素。操作后，$a = [2,1,3]$，$b = [2,1,3]$。
• 再交换第 $1$ 和第 $2$ 个元素。操作后，$a$ 和 $b$ 都已排序。

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

由 ChatGPT 4.1 翻译

样例

3
5
1 2 3 4 5
5 4 3 2 1
3
3 1 2
3 1 2
6
2 5 6 1 3 4
1 5 3 6 2 4

3 2 5 1 4
3 4 1 5 2
1 2 3
1 2 3
2 3 4 6 5 1
1 2 4 3 5 6