06756. USACO·表格还原 未做

Bessie 有一个 $N\times N$（$1\le N\le 1000$）的加法表，其中对于所有 $1\le r,c\le N$，第 $r$ 行第 $c$ 列的方格中的整数为 $r+c$。例如，对于 $N=3$，表格如下所示：

2 3 4

3 4 5

4 5 6

不幸的是，Elsie 得到了这张表格，并通过执行若干次以下三种类型的操作对表格进行了变换。

• 交换两行；
• 交换两列；
• 选择两个同时存在于表格中的值 $a$ 和 $b$，然后同时将每一个 $a$ 更改为 $b$，每一个 $b$ 更改为 $a$。

Elsie 总是按类型顺序执行操作；也就是说，她首先执行任意数量（可能为零）的类型 $1$ 操作，然后是类型 $2$ 操作，最后是类型 $3$ 操作。

请帮助 Bessie 恢复 Elsie 在执行完所有类型 $1$ 和 $2$ 操作后，但在执行任意类型 $3$ 操作之前，表格的一种可能状态。可能存在多种可能的答案，在这种情况下你应当输出字典序最小的答案。

按字典序比较两个表格时，比较它们在自然顺序（行间从上到下，行内从左到右）下读取时第一个不同的项。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

以下 $N$ 行每行包含 $N$ 个整数，表示 Elsie 变换后的 Bessie 的加法表。

输出所有类型 1 和 2 操作后，类型 3 操作前，表格的字典序最小可能状态。输入保证答案存在。

【样例解释】

• 测试点 6-7：$N\le 8$。

• 测试点 8-11：$N\le 100$。

• 测试点 12-15：没有额外限制。

【数据规模与约定】

• 测试点 4-5：$N\le 6$。

• 测试点 6-7：$N\le 8$。

• 测试点 8-11：$N\le 100$。

• 测试点 12-15：没有额外限制。

供题：Benjamin Qi