벽 칠하기

어린 소녀 마샤가 자기 방의 벽을 보고 있다. 벽은 정사각형 타일로 덮여 있는데, 일부 타일은 램프로 교체되어 있다. 따라서 벽을 n × m 크기의 직사각형으로 생각할 수 있고, 어떤 칸에는 타일이, 다른 칸에는 램프가 들어 있다.

마샤에게는 k가지 색의 물감이 있다. 가로 또는 세로로 연속한 타일 구간 중 양 끝이 벽의 모서리이거나 램프인 것을 생각하자. 마샤는 모든 타일을 칠하되, 그러한 구간에 속한 타일들이 모두 서로 다른 색으로 칠해지도록 하려고 한다. 마샤는 램프는 칠하지 않는다. 모든 색을 다 쓸 필요는 없다.

마샤가 벽을 칠하도록 도와주자.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 수 t가 주어진다.

각 테스트 케이스는 여러 줄로 주어진다. 첫째 줄에는 세 정수 n, m, k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ max(n, m))가 주어진다. 이는 벽의 크기와 마샤가 가진 물감의 수이다.

다음 n개의 줄에는 각각 m개의 정수 aij가 주어진다.

• aij = 0이면 위치 (i, j)에 램프가 있다.
• aij = 1이면 위치 (i, j)에 타일이 있다.

한 입력 안의 모든 테스트 케이스에서 타일과 램프의 총 개수는 105을 넘지 않는다.

각 테스트 케이스마다 답을 출력한다.

• 벽을 칠할 방법이 없으면 NO를 출력한다.
• 벽을 칠할 방법이 하나라도 있으면 YES를 출력한다. 이 경우 다음 n개의 줄에는 각각 m개의 정수 bij가 주어져야 한다. bij는 위치 (i, j)에 있는 타일의 색이고, 그 위치에 램프가 있으면 0이다. 칠하는 방법이 여러 가지라면 아무거나 하나를 출력해도 된다.