{"problem":{"name":"[SNOI2024] 拉丁方","description":{"content":"我们定义一个 $n \\times n$ 的矩阵 $A$ 为拉丁方，当且仅当，每行每列都是一个 $1 \\sim n$ 的排列。 现在给你一个矩阵 $A$ 左上角的一个 $R \\times C$ 的子矩阵，也就是 $A_{i, j}$（$1 \\le i \\le R$，$1 \\le j \\le C$）。问能不能将剩下的位置填上数使得它是一个拉丁方。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10062"},"statements":[{"statement_type":"Markdown","content":"我们定义一个 $n \\times n$ 的矩阵 $A$ 为拉丁方，当且仅当，每行每列都是一个 $1 \\sim n$ 的排列。\n\n现在给你一个矩阵 $A$ 左上角的一个 $R \\times C$ 的子矩阵，也就是 $A_{i, j}$（$1 \\le i \\le R$，$1 \\le j \\le C$）。问能不能将剩下的位置填上数使得它是一个拉丁方。\n\n## Input\n\n多组测试数据，第一行一个整数 $T$ 表示测试数据组数。  \n对于每组测试数据，第一行三个整数 $n, R, C$ 表示矩阵大小和已知的矩阵大小。  \n接下来 $R$ 行，每行 $C$ 个数，其中第 $i$ 行的第 $j$ 个数表示 $A_{i, j}$。\n\n## Output\n\n对于每组数据，第一行输出一个字符串 `Yes` 或者 `No`，表示能否找到满足条件的拉丁方。  \n如果能找到满足条件的拉丁方，那么在接下来 $n$ 行，每行输出 $n$ 个数，表示一个满足条件的拉丁方。如果有多组满足条件的方案，输出任意一种即可。\n\n[samples]\n\n## Note\n\n**【样例 \\#1 解释】**\n\n在第一个样例中，对于第二组数据，根据前两行可以发现，$A_{1, 3} = A_{2, 3} = 3$，所以不存在满足条件的拉丁方。\n\n对于第三组数据，可以发现输出是一个满足条件的拉丁方，并且左上角是输入的矩阵。下面也是一个满足条件的方案。\n$$\\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}$$\n\n---\n\n**【样例 \\#2】**\n\n见附件中 `latin/latin2.in` 与 `latin/latin2.ans`，这个样例满足测试点 $6 \\sim 7$ 的条件限制。\n\n---\n\n**【样例 \\#3】**\n\n见附件中 `latin/latin3.in` 与 `latin/latin3.ans`，这个样例满足测试点 $11 \\sim 12$ 的条件限制。\n\n---\n\n**【数据范围】**\n\n对于所有的数据，保证 $1 \\le T \\le 10$，$1 \\le n \\le 500$，$1 \\le R, C \\le n$，$1 \\le A_{i, j} \\le n$，保证输入的子矩阵不存在一行或者一列有两个相同的数。\n\n具体如下：\n\n| 测试点编号 | $n \\le$ | 特殊性质 |\n|:-:|:-:|:-:|\n| $1 \\sim 2$ | $6$ | 无 |\n| $3 \\sim 4$ | $10$ | 无 |\n| $5$ | $500$ | A |\n| $6 \\sim 7$ | $100$ | B |\n| $8 \\sim 9$ | $300$ | B |\n| $10$ | $500$ | B |\n| $11 \\sim 12$ | $500$ | C |\n| $13 \\sim 14$ | $100$ | 无 |\n| $15 \\sim 16$ | $300$ | 无 |\n| $17 \\sim 20$ | $500$ | 无 |\n\n特殊性质 A：保证 $R = 1$。  \n特殊性质 B：保证 $C = n$。  \n特殊性质 C：保证 $R, C \\le \\frac{n}{2}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10062","tags":["各省省选","2024","Special Judge","O2优化","陕西"],"sample_group":[["3\n2 1 1\n1\n3 2 2\n1 2\n2 1\n5 2 3\n1 2 3\n4 3 2\n","Yes\n1 2\n2 1\nNo\nYes\n1 2 3 4 5\n4 3 2 5 1\n2 4 5 1 3\n3 5 1 2 4\n5 1 4 3 2\n"]],"created_at":"2026-03-03 11:09:25"}}