34069번 - 자리 바꾸기 스페셜 저지

문제

준혁이는 여름방학을 맞아 교실에 작은 장난을 계획하고 있다. 바로 학생들의 자리를 살짝 바꿔 놓는 것이다.

교실은 $N$개의 행과 $M$개의 열로 구성된 2차원 격자 형태로, $i$행 $j$열에는 출석번호 $A_{i,j}$번 학생이 앉아 있다. 모든 학생의 출석번호는 다르다.

자리를 너무 멀리 바꾸면 선생님에게 들킬 수 있기 때문에, 학생은 자신의 자리에서 상하좌우로 인접한 칸으로만 이동할 수 있다. 즉, $i$행 $j$열에 있는 학생은 $|i-i'|+|j-j'|=1$이 성립할 때만 $i'$행 $j'$열로 이동할 수 있다. 또한, 자리가 전혀 바뀌지 않은 학생이 생기면 소외감을 느낄 수 있으므로, 모든 학생은 반드시 정확히 한 번만 자리를 바꿔야 한다.

준혁이를 위해 위의 조건들을 모두 만족하는 새로운 자리 배치가 가능한지 판단하고, 가능하다면 그중 하나를 출력해 보자.

입력

첫째 줄에 두 정수 $N,M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 $M$개의 정수가 공백으로 구분되어 주어진다. $i+1(1\leq i\leq N)$번째 줄의 $j(1\leq j\leq M)$번째 수는 $A_{i,j}$를 의미한다.

출력

조건을 만족하는 배치가 가능하다면 첫째 줄에 Yes를 출력한다.

이어 둘째 줄부터 $N$개의 줄에 걸쳐 $M$개의 정수를 공백으로 구분하여 출력한다. $i+1(1\leq i\leq N)$번째 줄의 $j(1\leq j\leq M)$번째 수는 조건을 만족하는 배치에서 $i$번째 행 $j$번째 열에 위치하는 학생의 출석번호를 의미한다.

조건을 만족하는 배치가 불가능하다면 첫째 줄에 No를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\leq N,M\leq 500$
• 1ドル\leq A_{i,j}\leq N\times M$ (1ドル\le i\le N$; 1ドル\le j\le M$)
• $A_{i,j}$는 모두 서로 다르다.

힌트