P10062 [SNOI2024] Latin Square

We define an $n \times n$ matrix $A$ to be a Latin square if and only if each row and each column is a permutation of $1 \sim n$. Now you are given an $R \times C$ submatrix in the top-left corner of matrix $A$, i.e., the entries $A_{i, j}$ ($1 \le i \le R$, $1 \le j \le C$). Determine whether it is possible to fill the remaining entries so that the whole matrix becomes a Latin square.

Multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case, the first line contains three integers $n, R, C$, representing the matrix size and the size of the known submatrix. Then follow $R$ lines, each containing $C$ numbers. The $j$-th number in the $i$-th line represents $A_{i, j}$.

For each test case, output a string `Yes` or `No` in the first line, indicating whether a Latin square satisfying the conditions can be found. If it can be found, then output $n$ more lines, each containing $n$ numbers, representing one valid Latin square. If multiple valid solutions exist, output any one of them.

**[Sample \#1 Explanation]** In the first sample, for the second test case, from the first two rows we can see that $A_{1, 3} = A_{2, 3} = 3$, so no Latin square satisfying the conditions exists. For the third test case, we can see that the output is a valid Latin square, and its top-left corner matches the input matrix. The following is also a valid solution. $$\begin{bmatrix} 1 & 2 & 3 & 5 & 4 \\ 4 & 3 & 2 & 1 & 5 \\ 3 & 5 & 1 & 4 & 2 \\ 2 & 4 & 5 & 3 & 1 \\ 5 & 1 & 4 & 2 & 3 \end{bmatrix}$$ --- **[Sample \#2]** See the attachments `latin/latin2.in` and `latin/latin2.ans`. This sample satisfies the constraint limits of test points $6 \sim 7$. --- **[Sample \#3]** See the attachments `latin/latin3.in` and `latin/latin3.ans`. This sample satisfies the constraint limits of test points $11 \sim 12$. --- **[Constraints]** For all testdata, it is guaranteed that $1 \le T \le 10$, $1 \le n \le 500$, $1 \le R, C \le n$, $1 \le A_{i, j} \le n$. It is guaranteed that in the input submatrix, no row or column contains two identical numbers. Details are as follows: | Test Point ID | $n \le$ | Special Property | |:-:|:-:|:-:| | $1 \sim 2$ | $6$ | None | | $3 \sim 4$ | $10$ | None | | $5$ | $500$ | A | | $6 \sim 7$ | $100$ | B | | $8 \sim 9$ | $300$ | B | | $10$ | $500$ | B | | $11 \sim 12$ | $500$ | C | | $13 \sim 14$ | $100$ | None | | $15 \sim 16$ | $300$ | None | | $17 \sim 20$ | $500$ | None | Special property A: It is guaranteed that $R = 1$. Special property B: It is guaranteed that $C = n$. Special property C: It is guaranteed that $R, C \le \frac{n}{2}$. Translated by ChatGPT 5