P9890 [ICPC 2018 Qingdao R] Tournament

DreamGrid，Gridland 的国王，正在举办一场骑士锦标赛。有 $n$ 名骑士，编号从 1 到 $n$，参加这次锦标赛。锦标赛的规则如下： - 锦标赛由 $k$ 轮组成。每一轮由若干场决斗组成。每场决斗恰好在两名骑士之间进行。 - 每名骑士在每一轮中必须参加一场决斗。 - 对于每对骑士，在所有 $k$ 轮中最多只能有一场决斗。 - 设 $1 \le i, j \le k$，$i \neq j$，且 $1 \le a, b, c, d \le n$，$a, b, c, d$ 是四个不同的整数。如果 - 骑士 $a$ 在第 $i$ 轮对战骑士 $b$，并且 - 骑士 $c$ 在第 $i$ 轮对战骑士 $d$，并且 - 骑士 $a$ 在第 $j$ 轮对战骑士 $c$， - 那么骑士 $b$ 必须在第 $j$ 轮对战骑士 $d$。 作为 DreamGrid 的将军，你需要编写一个程序来安排所有 $k$ 轮中的所有决斗，以便结果安排满足上述规则。

有多个测试用例。输入的第一行是一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $k$ ($1 \le n, k \le 1000$)，表示参加锦标赛的骑士数量和轮数。 保证所有测试用例中 $n$ 和 $k$ 的总和不超过 5000。

对于每个测试用例： - 如果可以进行有效的安排，输出 $k$ 行。在第 $i$ 行，输出 $n$ 个整数 $c_{i, 1}, c_{i, 2}, \dots, c_{i, n}$，用空格分隔，表示在第 $i$ 轮中，骑士 $j$ 将与骑士 $c_{i, j}$ 对战，所有 $1 \le j \le n$。如果有多个有效答案，输出字典序最小的答案。考虑两个答案 $A$ 和 $B$，记 $a_{i, j}$ 为答案 $A$ 中第 $i$ 行的第 $j$ 个整数，$b_{i, j}$ 为答案 $B$ 中第 $i$ 行的第 $j$ 个整数。答案 $A$ 在字典序上小于答案 $B$，如果存在两个整数 $p$ ($1 \le p \le k$) 和 $q$ ($1 \le q \le n$)，使得 - 对于所有 $1 \le i < p$ 和 $1 \le j \le n$，$a_{i, j} = b_{i, j}$，并且 - 对于所有 $1 \le j < q$，$a_{p, j} = b_{p, j}$，最终 $a_{p, q} < b_{p, q}$。 - 如果无法进行有效的安排，输出一行 “Impossible”（不带引号）。 请不要在每行末尾输出多余的空格，否则你的答案可能会被视为不正确！

题面翻译由 ChatGPT-4o 提供。