Fill in the Matrix
Contest: Codeforces Round 896 (Div. 1)
Difficulty rating: 1300
Tags: constructive algorithms, implementation

There is an empty matrix $$$M$$$ of size $$$n\times m$$$.

Zhongkao examination is over, and Daniel would like to do some puzzle games. He is going to fill in the matrix $$$M$$$ using permutations of length $$$m$$$. That is, each row of $$$M$$$ must be a permutation of length $$$m^\dagger$$$.

Define the value of the $$$i$$$-th column in $$$M$$$ as $$$v_i=\operatorname{MEX}(M_{1,i},M_{2,i},\ldots,M_{n,i})^\ddagger$$$. Since Daniel likes diversity, the beauty of $$$M$$$ is $$$s=\operatorname{MEX}(v_1,v_2,\cdots,v_m)$$$.

You have to help Daniel fill in the matrix $$$M$$$ and maximize its beauty.

$$$^\dagger$$$ A permutation of length $$$m$$$ is an array consisting of $$$m$$$ distinct integers from $$$0$$$ to $$$m-1$$$ in arbitrary order. For example, $$$[1,2,0,4,3]$$$ is a permutation, but $$$[0,1,1]$$$ is not a permutation ($$$1$$$ appears twice in the array), and $$$[0,1,3]$$$ is also not a permutation ($$$m-1=2$$$ but there is $$$3$$$ in the array).

$$$^\ddagger$$$ The $$$\operatorname{MEX}$$$ of an array is the smallest non-negative integer that does not belong to the array. For example, $$$\operatorname{MEX}(2,2,1)=0$$$ because $$$0$$$ does not belong to the array, and $$$\operatorname{MEX}(0,3,1,2)=4$$$ because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ appear in the array, but $$$4$$$ does not.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$) — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 2\cdot 10^5$$$) — the size of the matrix.

It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, in the first line output a single integer — the maximum beauty of $$$M$$$.

Then output the matrix $$$M$$$ of size $$$n\times m$$$ — the matrix you find.

If there are multiple solutions, you may output any of them.

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

Note:
In the first test case:

- $$$v_1=\operatorname{MEX}(1,0,1,0)=2$$$;
- $$$v_2=\operatorname{MEX}(0,2,0,2)=1$$$;
- $$$v_3=\operatorname{MEX}(2,1,2,1)=0$$$.

Therefore, $$$s=\operatorname{MEX}(2,1,0)=3$$$.

It can be shown that $$$3$$$ is the maximum possible beauty of $$$M$$$.

In the second test case, any permutation will make $$$s=2$$$.

In the third test case:

- $$$v_1=\operatorname{MEX}(3,5,1,4,4,2)=0$$$;
- $$$v_2=\operatorname{MEX}(0,2,3,1,2,4)=5$$$;
- $$$v_3=\operatorname{MEX}(1,1,2,3,5,0)=4$$$;
- $$$v_4=\operatorname{MEX}(4,0,4,2,3,5)=1$$$;
- $$$v_5=\operatorname{MEX}(2,4,5,5,0,1)=3$$$;
- $$$v_6=\operatorname{MEX}(5,3,0,0,1,3)=2$$$.

Therefore, $$$s=\operatorname{MEX}(0,5,4,1,3,2)=6$$$.

Example input:
4
4 3
1 16
6 6
2 1

Example output:
3
1 0 2
0 2 1
1 0 2
0 2 1
2
14 7 15 4 10 0 8 6 1 2 3 5 9 11 12 13 
6
3 0 1 4 2 5 
5 2 1 0 4 3 
1 3 2 4 5 0 
4 1 3 2 5 0 
4 2 5 3 0 1 
2 4 0 5 1 3
0
0
0

Editorial:
On one hand, the matrix $$$M$$$ has $$$n$$$ rows, so the maxmium $$$v_i$$$ does not exceed $$$\operatorname{MEX}(0,1,\cdots,n-1)=n$$$, and $$$s$$$ does not exceed $$$n+1$$$.
On the other hand, the matrix $$$M$$$ has $$$m$$$ columns, and there are only $$$m$$$ numbers in the array $$$v$$$, so $$$s$$$ must not exceed $$$m$$$.
Therefore, the upper bound of $$$s$$$ is $$$\min(n+1,m)$$$.
How can we reach the upper bound?
If $$$m=1$$$, then the only possible $$$M=\begin{pmatrix} 0\\ 0\\ \vdots\\ 0 \end{pmatrix}$$$, in this case, $$$v_1=1$$$, so $$$s$$$ must be $$$0$$$, which unfortunately cannot reach the upper bound. Sadly, many participants failed on pretest 2 because of it. I've added this test to examples:)
If $$$m>1$$$, let's construct the $$$M$$$ in two cases:
• Case 1. $$$m\ge n+1$$$.In this case, we can construct $$$M$$$ like following: $$$$$$M= \begin{pmatrix} 0&1&\cdots&m-2&m-1\\ 1&2&\cdots&m-1&0\\ 2&3&\cdots&0&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ n-1&n&\cdots &n-3 & n-2 \end{pmatrix}$$$$$$More formally, $$$M_{i,j}=(i+j-1)\bmod m$$$.Note that in this case $$$n-1< m-1$$$, so we have $$$v_1=n$$$, $$$v_2=v_{3}=\cdots=v_{m-n-1}=0$$$, $$$v_{m-n}=1,v_{m-n+1}=2,\cdots,v_m=n-1$$$. Then $$$s=n+1$$$, which reaches the upper bound.
• Case 2. $$$m<n+1$$$.In this case, we can construct $$$M$$$ like following: $$$$$$M= \begin{pmatrix} 0&1&\cdots&m-2&m-1\\ 1&2&\cdots&m-1&0\\ 2&3&\cdots&0&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ m-2&m-1&\cdots &m-4 & m-3\\ 0&1&\cdots&m-2&m-1\\ 0&1&\cdots&m-2&m-1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&1&\cdots&m-2&m-1\\ \end{pmatrix}$$$$$$More formally, for $$$1\le j\le m-1$$$, $$$M_{i,j}=(i+j-1)\bmod m$$$, for $$$m\le j\le n$$$, $$$M_{i,j}=(j-1)\bmod m$$$.Note that $$$m>1$$$, and $$$m-2\ge 0$$$. Similarly to case 1 we can get $$$s=m$$$, which also reaches the upper bound.
Time Complexity: $$$\mathcal{O}(n\cdot m)$$$ per test case.