seuOJ555 - MEX Should Be Same

题目描述

有一个 n×nn\times n 的二维数组，其中每个数都是 00 到 nn 的整数，请你至多修改数组中的 ⌊n×n2⌋\lfloor \frac{n\times n}{2}\rfloor 个数，将其改为另一个 00 到 nn 的整数。所有修改操作完成后，使得数组每一行、每一列的所有数字的 MEX 值都等于一个相同的数字。

MEX 是指所有数字中最小的未出现的非负整数，例如 MEX({1,2,3})=0MEX(\{1,2,3\})=0、MEX({1,0,5,7,4,1})=2MEX(\{1,0,5,7,4,1\})=2 和 MEX({0,0,1,1,1,3})=2MEX(\{0,0,1,1,1,3\})=2。

⌊x⌋\lfloor x\rfloor 代表对于 xx 向下取整，例如 ⌊12⌋=0\lfloor \frac{1}{2} \rfloor=0 、 ⌊92⌋=4\lfloor \frac{9}{2} \rfloor=4 和 ⌊162⌋=8\lfloor \frac{16}{2} \rfloor=8。

输入格式

第一行，一个整数 t(1≤t≤104)t(1\le t\le 10^4)，代表数据组数。

对于每组数据：

第一行，一个整数 n(1≤n≤1000)n(1\le n\le 1000)，代表二维数组的大小。

接下来的 nn 行，每行 nn 个数字，第 ii 行第 jj 列的数字 ai,j(0≤ai,j≤n)a_{i,j}(0\le a_{i,j}\le n) 代表数组中第 ii 行第 jj 列的数字。

保证同一测试点内的 n2n^2 的总和不超过 10610^6。

输出格式

对于每组数据，输出一个 n×nn\times n 的矩阵，代表修改后的矩阵，矩阵每行每列的 MEX 值需要相同。

可以被证明的是，在题目要求的条件下，一定存在一种修改数组的方案，满足题目的要求。

样例

输入样例

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

输出样例

1
0 1 2
1 2 0
2 0 1
1 2 0 2
2 0 1 0 
0 1 0 2
2 0 2 1
2 2
1 2