锦标赛 - 题目

Gridland 的国王 DreamGrid 正在举办一场骑士锦标赛。共有 $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$ 个整数。如果存在两个整数 $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}$，则称答案 $A$ 在字典序上小于答案 $B$。
如果无法做出有效的安排，则输出一行 "Impossible"（不含引号）。

请注意，不要在每行末尾输出多余的空格，否则你的答案可能会被判定为错误！

2
3 1
4 3

Impossible
2 1 4 3
3 4 1 2
4 3 2 1

QOJ.ac