103176: [Atcoder]ABC317 G - Rearranging

Problem Statement

There is a grid with $N$ rows and $M$ columns. The square at the $i$-th row from the top and the $j$-th column from the left contains the integer $A_{i,j}$.
Here, the squares contain $M$ occurrences of each of $1,\ldots,N$, for a total of $NM$ integers.

You perform the following operations to swap the numbers written on the squares.

• For $i=1,\ldots,N$ in this order, do the following.
  • Freely rearrange the numbers written in the $i$-th row. That is, freely choose a permutation $P=(P_{1},\ldots,P_{M})$ of $1,\ldots,M$, and replace $A_{i,1},\ldots,A_{i,M}$ with $A_{i,P_{1}},\ldots,A_{i,P_{M}}$ simultaneously.

Your goal is to perform the operations so that each column contains each of $1,\ldots,N$ once. Determine if this is possible, and if so, print such a resulting grid.

Constraints

• $1 \leq N,M \leq 100$
• $1 \leq A_{i,j} \leq M$
• All input values are integers.
• The $NM$ numbers $A_{1,1},\ldots,A_{N,M}$ contain exactly $M$ occurrences of each of $1,\ldots,N$.

Input

The Input is given from Standard Input in the following format:

$N$ $M$
$A_{1,1}$ $\ldots$ $A_{1,M}$
$\vdots$
$A_{N,1}$ $\ldots$ $A_{N,M}$

Output

If it is impossible to perform the operations so that each column contains each of $1,\ldots,N$ once, print No.
Otherwise, print Yes in the first line, and in the subsequent $N$ lines, print a resulting grid where each column contains each of $1,\ldots,N$ once, in the following format.
Let $B_{i,j}$ be the number written in the square at the $i$-th row from the top and $j$-th column from the left of the grid. For each $1\leq i \leq N$, the $(i+1)$-th line should contain $B_{i,1},\ldots,B_{i,M}$ in this order, with spaces in between.

If multiple solutions exist, any of them is accepted.

Sample Input 1

3 2
1 1
2 3
2 3

Sample Output 1

Yes
1 1
3 2
2 3

Also, the following output is accepted.

Yes
1 1
2 3
3 2

Sample Input 2

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

Sample Output 2

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

问题描述

有一个包含$N$行和$M$列的网格。从顶部数第$i$行，从左数第$j$列的正方形包含整数$A_{i,j}$。
在这里，正方形包含$1,\ldots,N$的$M$次出现，总共包含$NM$个整数。

您执行以下操作来交换正方形上书写的数字。

• 按以下顺序对$i=1,\ldots,N$进行操作：
  • 自由地重新排列第$i$行中的数字。也就是说，自由地选择$1,\ldots,M$的排列$P=(P_{1},\ldots,P_{M})$，并将$A_{i,1},\ldots,A_{i,M}$同时替换为$A_{i,P_{1}},\ldots,A_{i,P_{M}}$。

你的目标是执行操作，使得每列都包含一次$1,\ldots,N$。确定这是否可能，如果可能，打印出这样的结果网格。

约束条件

• $1 \leq N,M \leq 100$
• $1 \leq A_{i,j} \leq N$
• 所有输入值都是整数。
• 数字$A_{1,1},\ldots,A_{N,M}$包含$1,\ldots,N$的$M$次出现。

输入

输入从标准输入中给出，格式如下：

$N$ $M$
$A_{1,1}$ $\ldots$ $A_{1,M}$
$\vdots$
$A_{N,1}$ $\ldots$ $A_{N,M}$

输出

如果无法执行操作，使得每列都包含一次$1,\ldots,N$，则打印No。
否则，在第一行打印Yes，然后在后续的$N$行中，以以下格式打印一个结果网格，其中每列都包含一次$1,\ldots,N$。
令$B_{i,j}$表示网格中从顶部数第$i$行，从左数第$j$列的正方形中书写的数字。对于每个$1\leq i \leq N$，第$(i+1)$行应包含$B_{i,1},\ldots,B_{i,M}$，中间用空格分隔。

如果存在多个解决方案，接受其中任何一个。

样例输入1

3 2
1 1
2 3
2 3

样例输出1

Yes
1 1
3 2
2 3

此外，以下输出也被接受。

Yes
1 1
2 3
3 2

样例输入2

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

样例输出2

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