Kevin and Bipartite Graph
Contest: Codeforces Global Round 28
Difficulty rating: 2000
Tags: constructive algorithms, graphs, greedy

The Arms Factory needs a poster design pattern and finds Kevin for help.

A poster design pattern is a bipartite graph with $$$ 2n $$$ vertices in the left part and $$$ m $$$ vertices in the right part, where there is an edge between each vertex in the left part and each vertex in the right part, resulting in a total of $$$ 2nm $$$ edges.

Kevin must color each edge with a positive integer in the range $$$ [1, n] $$$. A poster design pattern is good if there are no monochromatic cycles$$$^{\text{∗}}$$$ in the bipartite graph.

Kevin needs your assistance in constructing a good bipartite graph or informing him if it is impossible.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$ t $$$ ($$$ 1 \le t \le 100 $$$).

The only line of each test case contains two integers $$$ n $$$ and $$$ m $$$ ($$$ 1 \le n, m \leq 10^3 $$$) — the bipartite graph has $$$ 2n $$$ vertices in the left part and $$$ m $$$ vertices in the right part.

It is guaranteed that both the sum of $$$ n $$$ and the sum of $$$ m $$$ over all test cases do not exceed $$$ 10^3 $$$.

Output format:
For each test case, if there is no solution, then output No.

Otherwise, output Yes, and then output $$$ 2n $$$ lines, with each line containing $$$ m $$$ positive integers. The $$$ i $$$-th line's $$$ j $$$-th integer represents the color of the edge between the $$$ i $$$-th vertex in the left part and the $$$ j $$$-th vertex in the right part.

If there are multiple answers, you can print any of them.

You can output each letter in any case (for example, the strings yEs, yes, Yes, and YES will be recognized as a positive answer).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, the graph is shown as follows:

For the second test case, it can be proven that there is no valid solution.

Example input:
3
2 2
3 7
5 4

Example output:
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

Editorial:
Hint #1: It can be observed that the larger $$$m$$$ is, the harder it is to satisfy the conditions. Try to find an upper bound for $$$m$$$.
The graph has a total of $$$2nm$$$ edges, and each color forms a forest. Therefore, for any given color, there are at most $$$2n + m - 1$$$ edges. Thus, the total number of edges cannot exceed $$$(2n + m - 1)n$$$. This gives the condition: $$$(2n+m-1)n\ge 2nm$$$. Simplifying, we find $$$m \leq 2n - 1$$$.
Next, we only need to construct a valid case for $$$m = 2n - 1$$$ to solve the problem.
In fact, this is easy to construct. Since each right-side vertex has a degree of $$$2n$$$, and there are $$$n$$$ total colors, let each color have exactly $$$2$$$ edges. For any given color, this is equivalent to choosing two left-side vertices to connect (ignoring the existence of the right-side vertices). After $$$2n - 1$$$ connections, the left-side vertices need to form a tree. It turns out that connecting the left-side vertices into a chain suffices. During construction, we can cycle the colors of the first right-side vertex. For example, for $$$n = 4$$$ and $$$m = 7$$$, the result looks like this:
"' 1 4 4 3 3 2 2 1 1 4 4 3 3 2 2 1 1 4 4 3 3 2 2 1 1 4 4 3 3 2 2 1 1 4 4 3 3 2 2 1 1 4 4 3 3 2 2 1 1 4 4 3 3 2 2 1 "'
Thus, a simple construction method is as follows: for left-side vertex $$$i$$$ and right-side vertex $$$j$$$, the color of the edge connecting them is given by:
$$$$$$ \left\lfloor\dfrac{(i+j)\bmod 2n}2\right\rfloor+1 $$$$$$