16635번 - Superdoku 스페셜 저지다국어

Alice and Bob are big fans of math. In particular, they are very excited about playing games that are related to numbers. Whenever they see a puzzle like Sudoku, they cannot stop themselves from solving it. The objective of Sudoku is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine (3 × 3) subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

After many years of solving Sudoku problems, Alice and Bob are tired of Sudoku. They have been trying to develop a harder variation of Sudoku, which they are calling Superdoku. In Superdoku, the grid is bigger – n × n instead of just 9 × 9. However, the “block” constraints are impossible to formulate when there are no further constraints on n. Therefore, there are no block constraints in Superdoku. Instead, the goal is simply to make sure that each column and each row in the grid contains all of the integers from 1 to n. After playing for a while in the standard way (where any of the grid cells may have previously been filled in), they decide that the game is too difficult and they want to simplify it. Therefore, they decide to make the initial grid further constrained. They constrain the board by filling in the first k rows completely.

Alice and Bob both believe that Superdoku is solvable. However, since n could be very big, it may still take a long time to figure out a solution. They don’t want to spend too much time on this single game, so they are asking for your help!

The input consists of a single test case. The first line lists two space-separated integers 1 ≤ n ≤ 100 and 0 ≤ k ≤ n, denoting the size of the grid (n × n) and the number of rows k that are already filled in. Each of the following k lines contains n space-separated integers, denoting the first k given rows. All integers in these k lines are between 1 and n.

Output either “yes” or “no” on the first line, indicating if there is a solution. If there is no solution, do not output anything more. If there is a solution, output n more lines, each containing n space-separated integers, representing a solution. If there are multiple solutions, output any one of them.