Fill in the Matrix (Codeforces 1868A)
Tags: Implement, constructive algorithms

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: 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: 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.

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$$$. 

Sample Inputs:
4
4 3
1 16
6 6
2 1

Sample Outputs:
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

Solution (Python):
from itertools import permutations

def allPermutations(str):
    permList = permutations(str)
    return permList

def factors(x):
    result = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            result.append(i)
            if x // i != i:
                result.append(x // i)
        i += 1
    return result

def fast_expo(val, power):
    result = pow(val, power // 2)
    result = result * result
    if power % 2 != 0:
        result = result * val
    return result

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True
t = int(input())
for i in range(t):
    s = ''
    (n, m) = map(int, input().split())
    l = [str(j) for j in range(m)]
    if m == 1:
        print('0\n' * (n + 1))
    else:
        if n >= m:
            print(m)
        else:
            print(n + 1)
        for j in range(n):
            s = s + ' '.join(l) + '\n'
            if j + 2 < m:
                l1 = [l[m - 1]]
                l.pop(m - 1)
                l = l1 + l
        print(s)

Solution (Python):
t = int(input())
for i in range(t):
    ch = ''
    (n, m) = input().split()
    (n, m) = (int(n), int(m))
    l = [str(j) for j in range(m)]
    if m == 1:
        print('0\n' * (n + 1))
    else:
        if n >= m:
            print(m)
        else:
            print(n + 1)
        for j in range(n):
            ch = ch + ' '.join(l) + '\n'
            if j + 2 < m:
                l1 = [l[m - 1]]
                l.pop(m - 1)
                l = l1 + l
        print(ch)

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    if n < m:
        print(n + 1)
        for i in range(n):
            l = ''
            k = i
            for j in range(m):
                l += str(k) + ' '
                if k == m - 1:
                    k = 0
                else:
                    k += 1
            print(l[:-1])
    else:
        if m == 1:
            print(0)
        else:
            print(m)
        for i in range(m - 1):
            l = ''
            k = i
            for j in range(m):
                l += str(k) + ' '
                if k == m - 1:
                    k = 0
                else:
                    k += 1
            print(l[:-1])
        print(((' '.join([str(o) for o in range(m)]) + '\n') * (n - m + 1))[:-1])