CF2023A.Concatenation of Arrays

给定 $n$ 个数组 $a_1, \ldots, a_n$，每个数组的长度均为 $2$，即 $a_i = [a_{i,1}, a_{i,2}]$。你需要将这些数组按某种顺序拼接成一个长度为 $2n$ 的数组，使得最终数组中的逆序对数 $^\dagger$ 最小。注意，你不需要实际计算逆序对的数量。

更正式地说，你需要选择一个长度为 $n$ 的排列 $^\ddagger$ $p$，使得数组 $b = [a_{p_1,1}, a_{p_1,2}, a_{p_2,1}, a_{p_2,2}, \ldots, a_{p_n,1}, a_{p_n,2}]$ 的逆序对数尽可能少。

$^\dagger$ 一个数组 $c$ 的逆序对数是指满足 $i < j$ 且 $c_i > c_j$ 的下标对 $(i, j)$ 的数量。

$^\ddagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但数组中有 $4$）。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的数量。

接下来的 $n$ 行，每行包含两个整数 $a_{i,1}$ 和 $a_{i,2}$（$1 \le a_{i,j} \le 10^9$），表示第 $i$ 个数组的两个元素。

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

对于每个测试用例，输出 $2n$ 个整数，表示你得到的数组的元素。如果有多种方案，输出任意一种均可。

在第一个测试用例中，我们按顺序 $2, 1$ 拼接数组，得到的数组 $b = [2, 3, 1, 4]$，其逆序对如下：

• $i = 1$，$j = 3$，因为 $b_1 = 2 > 1 = b_3$；
• $i = 2$，$j = 3$，因为 $b_2 = 3 > 1 = b_3$。

因此，逆序对数为 $2$。可以证明这是最小的逆序对数。

在第二个测试用例中，我们按顺序 $3, 1, 2$ 拼接数组，得到 $b = [2, 1, 3, 2, 4, 3]$，其逆序对如下：

• $i = 1$，$j = 2$，因为 $b_1 = 2 > 1 = b_2$；
• $i = 3$，$j = 4$，因为 $b_3 = 3 > 2 = b_4$；
• $i = 5$，$j = 6$，因为 $b_5 = 4 > 3 = b_6$。

因此，逆序对数为 $3$。可以证明这是最小的逆序对数。

在第三个测试用例中，我们按顺序 $4, 2, 1, 5, 3$ 拼接数组。

由 ChatGPT 4.1 翻译