만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Superdoku

시간 제한2초메모리 제한512 MB

요약
n x n 격자의 처음 k개 행이 주어질 때, 모든 행과 열에 1부터 n까지 숫자가 한 번씩 들어가도록 나머지 행을 채울 수 있는지 판단하고 한 가지 답을 출력합니다.
난이도

보통10점 중 6점

유형
그래프, 행렬, 그리디
정답자
아직 제출이 없습니다

문제

Alice와 Bob은 수학을 좋아한다. 숫자로 하는 게임에 푹 빠져 있어서, 스도쿠 같은 퍼즐을 보면 그냥 지나치지 못하고 풀곤 한다. 스도쿠의 목표는 9×99 \times 9 격자를 숫자로 채워서 각 행, 각 열, 그리고 아홉 개의 3×33 \times 3 상자 안에 1부터 9까지의 숫자가 모두 들어가도록 만드는 것이다. 출제자는 일부만 채워진 격자를 주며, 잘 만들어진 퍼즐의 해는 하나뿐이다.

문제

Superdoku는 n×nn \times n 격자를 쓴다. 상자 제약은 없다. 대신 각 행과 각 열에 1부터 nn까지의 정수가 모두 들어 있어야 한다. 게임을 단순하게 만들려고 Alice와 Bob은 시작 전에 처음 kk개 행을 모두 채워 두기로 했다. 이 격자를 끝까지 채울 수 있는지 판단하라.

입력

첫 줄에 공백으로 구분된 두 정수 nn (1≤n≤1001 \le n \le 100)과 kk (0≤k≤n0 \le k \le n)가 주어진다. 이어지는 kk개 줄에는 격자의 처음 kk개 행이 각각 nn개의 정수로 주어진다. 모든 정수는 1 이상 nn 이하이다.

출력

해가 존재하면 첫 줄에 yes를 출력하고, 이어서 공백으로 구분된 nn개의 정수로 이루어진 nn개 줄을 출력하여 유효한 격자 하나를 보여라. 해가 없으면 no만 출력한다. 해가 여러 개라면 그중 아무거나 하나를 출력하면 된다.

예제2

  1. 예제 1

    입력
    4 2
1 2 3 4
2 3 4 1
    예상 출력
    yes
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

  2. 예제 2

    입력
    4 2
1 2 3 4
2 2 2 2
    예상 출력
    no