← 返回题目列表

Codeforces · 2048/E

E. 凯文和二分图

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

军工厂需要海报设计图案,找到凯文帮忙。

海报设计模式是一个二部图,左侧有 $$$ 2n $$$ 个顶点,右侧有 $$$ m $$$ 个顶点,其中左侧每个顶点和右侧每个顶点之间都有一条边,总共有 $$$ 2nm $$$ 边。

Kevin 必须使用 $$$ [1, n] $$$ 范围内的正整数为每条边着色。如果二分图中没有单色循环$$$^{\text{*}}$$$,则海报设计模式是好的。

凯文需要您的帮助来构建一个好的二部图,或者如果不可能的话请通知他。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$ t $$$ ($$$ 1 \le t \le 100 $$$)。

每个测试用例的唯一行包含两个整数 $$$ n $$$ 和 $$$ m $$$ ($$$ 1 \le n, m \leq 10^3 $$$) - 二分图左侧有 $$$ 2n $$$ 顶点,右侧有 $$$ m $$$ 顶点。

保证所有测试用例的 $$$ n $$$ 之和以及 $$$ m $$$ 之和不超过 $$$ 10^3 $$$。

输出

对于每个测试用例,如果没有解,则输出No。

否则,输出Yes,然后输出$$$ 2n $$$行,每行包含$$$ m $$$正整数。第 $$$ i $$$ 行的第 $$$ j $$$ 整数表示左侧第 $$$ i $$$ 个顶点和右侧第 $$$ j $$$ 个顶点之间的边的颜色。

如果有多个答案,您可以打印其中任何一个。

您可以在任何情况下输出每个字母(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定答案)。

示例

输入 #1

3
2 2
3 7
5 4

输出 #1

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

注意

对于第一个测试用例,图形如下所示:

对于第二个测试用例,可以证明没有有效的解决方案。