2041. 圣慧星兰学院的情人节

时间限制 1000 ms   内存限制 256 MB

又到了一年一度的情人节。

今年,尼西亚会准备在圣慧星兰学院中,举办一个“礼物交换”活动。

不过,正如Amitié制度从二人变为三人一样,今年的“礼物交换”活动也不太平······

现在,有 $n$ 位同学想参加“礼物交换”活动。

尼西亚会对这场不一样的情人节活动做出了以下规定:

  1. 每位同学需要和 $m$ 位同学交换情人节礼物;
  2. 每位同学 不能同一个人 重复交换礼物;
  3. 每位同学 不能自己 交换礼物;
  4. 如果同学 $i$ 和同学 $j$ 交换礼物,那么同学 $j$ 也必须和同学 $i$ 交换礼物。

八代让叶作为尼西亚会会长,想要让你帮她找到 任意的 一种合法的礼物交换方案。

若存在一种合法方案,请输出 “YES”,并输出一个满足以上四个条件的 $n$ 行 $m$ 列的矩阵。其中,第 $i$ 行第 $j$ 列的元素表示,第 $i$ 位同学和第 $a[i][j]$ 位同学交换了礼物。

如果 不存在 任何一种合法方案,请输出 “NO”。

输入数据

第一行包含一个正整数 $T\ (1 \leq T \leq 100)$,表示接下来有 $T$ 组测试点。

每组测试点只有一行,该行包含两个正整数 $n, m\ (1 \leq m < n \leq 10^6)$,分别表示 同学的个数 和 每位同学交换的礼物数量。

保证对于一次测试中,所有测试点的 $n \times m$ 之和不超过 $10^6$。

输出数据

对于每组测试点,若存在任意一种合法方案,那么请输出 “YES”,并在接下来的 $n$ 行每行输出 $m$ 个数,表示你找到的一种合法的礼物交换方案。其中,第 $i$ 行第 $j$ 个数表示,第 $i$ 位同学和第 $a[i][j]$ 位同学交换了礼物。

若不存在任何一种合法方案,请输出 “NO”。

若存在多种合法方案,请输出 任意 一种合法方案即可。

本题输出量较大,请勿频繁使用 endl 清空缓冲区,否则代码可能超过时间限制。

样例输入

复制
3
5 2
5 1
4 3 \n
 · \n
 · \n
 · \n

样例输出 special judge

复制
YES
5 2
1 4
4 5
2 3
3 1
NO
YES
2 3 4
1 3 4
1 2 4
1 2 3   \n
 · \n
 · \n
 · \n
 · \n
 · \n
  \n
   \n
 · · \n
 · · \n
 · · \n
 · · \n

样例说明

对于第一个测试点。有 $5$ 位同学,每位同学需要和 $2$ 位同学交换礼物。

存在一种合法方案,方案如下:①和②⑤交换礼物、②和①④交换礼物、③和④⑤交换礼物、④和②③交换礼物、⑤和①③交换礼物。

对于第二个测试点,有 $5$ 位同学,每位同学需要和 $1$ 位同学交换礼物。

可以证明,不存在任何一种满足题目中四个要求的合法方案。

小御门奈莉奈:“一位同学和多位同学交换情人节礼物,这真的没问题吗?”(皱眉)

提交

请先 登录

© 2024 FAQs Contact About