G - Rearranging Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 行 M 列のグリッドがあります。上から i 行目左から j 列目のマスには整数 A_{i,j} が書かれています。
ここで、グリッドのマスに書かれている計 NM 個の整数は 1,\ldots,N をちょうど M 個ずつ含みます。

あなたは次の手順でマスに書かれた数を入れ替える操作を行います。

  • i=1,\ldots,N の順に次を行う。
    • i 行目に書かれた数を自由に並び替える。すなわち、1,\ldots,M の並び替えである長さ 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 つずつ含むようにすることです。そのようなことが可能であるか判定し、可能であれば操作後のグリッドの状態を出力してください。

制約

  • 1 \leq N,M \leq 100
  • 1 \leq A_{i,j} \leq N
  • 入力は全て整数である
  • NM 個の数 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 を 1 つずつ含むようにするのが不可能ならば No と出力せよ。
可能であるとき、1 行目に Yes と出力し、続く N 行に、全ての列が 1,\ldots,N を 1 つずつ含むように操作したあとのグリッドの状態を次の形式で出力せよ。
グリッドの上から i 行目左から j 列目のマスに書かれた数を B_{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

Score : 600 points

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 N
  • 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