又到了一年一度的情人节。
今年,尼西亚会准备在圣慧星兰学院中,举办一个“礼物交换”活动。
不过,正如Amitié制度从二人变为三人一样,今年的“礼物交换”活动也不太平······
现在,有 $n$ 位同学想参加“礼物交换”活动。
尼西亚会对这场不一样的情人节活动做出了以下规定:
八代让叶作为尼西亚会会长,想要让你帮她找到 任意的 一种合法的礼物交换方案。
若存在一种合法方案,请输出 “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
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$ 位同学交换礼物。
可以证明,不存在任何一种满足题目中四个要求的合法方案。
小御门奈莉奈:“一位同学和多位同学交换情人节礼物,这真的没问题吗?”(皱眉)