← 返回题目列表

Codeforces · 2034/E

E. 排列和谐

中文机器翻译题面 查看原题

Rayan 想向 Reyhaneh 赠送一份礼物以赢得她的心。然而,Reyhaneh 是特殊的,并且只接受 k 调和排列集。

我们将 k 调和排列集定义为一组 $$$k$$$ 成对不同排列 $$$p_1, p_2, \ldots, p_k$$$,大小为 $$$n$$$,这样对于每对索引 $$$i$$$ 和 $$$j$$$(其中 $$$1 \leq i, j \leq n$$$),满足以下条件持有:

$$$$$$ p_1[i] + p_2[i] + \ldots + p_k[i] = p_1[j] + p_2[j] + \ldots + p_k[j] $$$$$$

您的任务是通过为 $$$n$$$ 和 $$$k$$$ 的给定值提供有效的 k 调和排列集合或确定这样的集合不存在来帮助 Rayan。

如果长度 $$$n$$$ 的序列包含从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好一次,我们将其称为排列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$),测试用例的数量。

每个测试用例由两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n, k \leq 10^5$$$) 组成。所有测试用例的 $$$n \cdot k$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,如果存在 k 谐波排列集,则在第一行打印 YES。然后,打印 $$$k$$$ 行,每行包含从 $$$1$$$ 到 $$$n$$$ 的整数的不同排列。

如果不存在这样的集合,则在第一行打印“NO”。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

如果可能有多个答案,则可以输出其中任何一个。

示例

输入 #1

4
3 3
4 2
5 1
3 2

输出 #1

YES
1 2 3
2 3 1
3 1 2
YES
1 2 3 4
4 3 2 1
NO
YES
1 2 3
3 2 1

注意

在示例 1 中,我们有 $$$p_1 = [1, 2, 3]$$$、$$$p_2 = [2, 3, 1]$$$ 和 $$$p_3 = [3, 1, 2]$$$。很容易看出$$$p_1[1] + p_2[1] + p_3[1] = p_1[2] + p_2[2] + p_3[2] = p_1[3] + p_2[3] + p_3[3] = 6$$$。

在示例 2 中,我们有 $$$p_1 = [1, 2, 3, 4]$$$ 和 $$$p_2 = [4, 3, 2, 1]$$$。很容易看出 $$$p_1[1] + p_2[1] = p_1[2] + p_2[2] = p_1[3] + p_2[3] = p_1[4] + p_2[4] = 5$$$。

在示例 3 中,由于 $$$p_1$$$ 中有五个不同的元素,因此显然答案是“否”。