CF1713E Cross Swapping

给定一个 $n \times n$ 的方阵 $A$，其中元素均为整数。我们用 $A_{i,j}$ 表示第 $i$ 行第 $j$ 列的元素。 你可以对矩阵进行如下操作：每次操作可以选择一个整数 $k$，然后对于每个 $i$（$1 \leq i \leq n$），交换 $A_{i, k}$ 和 $A_{k, i}$。注意，$A_{k, k}$ 不会发生变化。 例如，对于 $n = 4$ 且 $k = 3$，矩阵会被如下方式变换：  操作 $k = 3$ 会将蓝色的行与绿色的列进行交换。你可以进行任意次数的这种操作。请你求出经过任意次数操作后，能够得到的字典序最小的矩阵$^\dagger$。 $^\dagger$ 对于两个 $n \times n$ 的矩阵 $A$ 和 $B$，记 $a_{(i-1) \cdot n + j} = A_{i,j}$，$b_{(i-1) \cdot n + j} = B_{i,j}$。如果存在某个下标 $i$（$1 \leq i \leq n^2$），使得 $a_i < b_i$，且对于所有 $1 \leq j < i$，都有 $a_j = b_j$，则称矩阵 $A$ 的字典序小于矩阵 $B$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示矩阵的大小。 接下来的 $n$ 行，每行包含 $n$ 个整数 $A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$（$1 \le A_{i, j} \le 10^9$），描述矩阵 $A$。 保证所有测试用例中 $n^2$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $n$ 行，每行 $n$ 个整数，表示字典序最小的矩阵。

注意，下方的图片中，每次操作都是将蓝色的行与绿色的列进行交换。 在第一个测试用例中，我们可以对 $k = 3$ 进行一次操作，矩阵会变成如下所示：  在第二个测试用例中，我们可以先对 $k = 1$，再对 $k = 3$ 进行两次操作：   由 ChatGPT 4.1 翻译