← 返回题目列表

Codeforces · 1713/E

E. 交叉交换

中文机器翻译题面 查看原题

给定一个方阵 $$$A$$$,大小为 $$$n \times n$$$,其元素为整数。我们将第 $$$i$$$ 行和第 $$$j$$$ 列的交集上的元素表示为 $$$A_{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$$$ 且对于所有索引 $$$j$$$ 使得 $$$1 \leq j < i$$$、$$$a_j = b_j$$$ 时,矩阵 $$$A$$$ 按字典顺序小于矩阵 $$$B$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) — 矩阵的大小。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含 $$$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$$$ 整数 — 按字典顺序排列的最小矩阵。

示例

输入 #1

2
3
2 1 2
2 1 2
1 1 2
4
3 3 1 2
1 1 3 1
3 2 3 2
2 3 3 1

输出 #1

2 1 1
2 1 1
2 2 2
3 1 1 2
3 1 2 1
3 3 3 3
2 3 2 1

注意

请注意,在下面的每张图片中,矩阵都以蓝色行与绿色列交换的方式进行转换。

在第一个测试用例中,我们可以对 $$$k = 3$$$ 执行 $$$1$$$ 操作。矩阵将变换如下: