#CF2048E. 凯文与二分图
凯文与二分图
E. Kevin 与二分图
时间限制: 秒 内存限制: 兆字节
军火工厂需要一张海报设计图案,于是找到了 Kevin 帮忙。
一个海报设计图案是一张二分图:
- 左侧有 个顶点
- 右侧有 个顶点
- 左侧每个点与右侧每个点之间都有边
- 总边数为
Kevin 必须用之间的正整数给每条边染色。
如果这张二分图中不存在同色环,那么这个设计图案就是完美的。
同色环:指所有边颜色都相同的简单环。
你需要帮助 Kevin 构造出一张完美的二分图,或者告诉他这是不可能的。
输入格式
每个测试包含多组数据。 第一行一个整数 (),表示测试数据组数。
每组数据一行,包含两个整数 和 ()。 保证所有测试数据的 和 均不超过 。
输出格式
对每组测试数据:
- 如果无解,输出
No - 如果有解,先输出
Yes - 然后输出 行,每行 个正整数
- 第 行第 个数表示左侧第 个点与右侧第 个点之间边的颜色
如果有多种答案,输出任意一种即可。 大小写不敏感。
样例输入
3
2 2
3 7
5 4
样例输出
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
样例解释
-
第一组测试数据:存在合法染色方案
-

-
第二组测试数据:可以证明不存在合法方案
-
第三组测试数据:存在合法染色方案