P10062 [SNOI2024] 拉丁方

我们定义一个 $n \times n$ 的矩阵 $A$ 为拉丁方，当且仅当，每行每列都是一个 $1 \sim n$ 的排列。 现在给你一个矩阵 $A$ 左上角的一个 $R \times C$ 的子矩阵，也就是 $A_{i, j}$（$1 \le i \le R$，$1 \le j \le C$）。问能不能将剩下的位置填上数使得它是一个拉丁方。

无

无

**【样例 \#1 解释】** 在第一个样例中，对于第二组数据，根据前两行可以发现，$A_{1, 3} = A_{2, 3} = 3$，所以不存在满足条件的拉丁方。 对于第三组数据，可以发现输出是一个满足条件的拉丁方，并且左上角是输入的矩阵。下面也是一个满足条件的方案。 $$\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}$$ --- **【样例 \#2】** 见附件中 `latin/latin2.in` 与 `latin/latin2.ans`，这个样例满足测试点 $6 \sim 7$ 的条件限制。 --- **【样例 \#3】** 见附件中 `latin/latin3.in` 与 `latin/latin3.ans`，这个样例满足测试点 $11 \sim 12$ 的条件限制。 --- **【数据范围】** 对于所有的数据，保证 $1 \le T \le 10$，$1 \le n \le 500$，$1 \le R, C \le n$，$1 \le A_{i, j} \le n$，保证输入的子矩阵不存在一行或者一列有两个相同的数。 具体如下： | 测试点编号 | $n \le$ | 特殊性质 | |:-:|:-:|:-:| | $1 \sim 2$ | $6$ | 无 | | $3 \sim 4$ | $10$ | 无 | | $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$ | 无 | | $15 \sim 16$ | $300$ | 无 | | $17 \sim 20$ | $500$ | 无 | 特殊性质 A：保证 $R = 1$。 特殊性质 B：保证 $C = n$。 特殊性质 C：保证 $R, C \le \frac{n}{2}$。