P15747 [JAG 2024 Summer Camp #3] Ball Passing

There are $M$ balls of each color $1, 2, \ldots, N$, and $N$ students are sitting in a circle playing with these balls. The students are numbered from $1$ to $N$ in the order in which they are seated. Initially, each student has exactly $M$ balls. Specifically, the color of the $j$-th ball that $i$-th student has is color $a_{i,j}$. They will perform the following operation to achieve a state where each student holds balls of only one color: **Operation**: Each of the $N$ students simultaneously passes one ball they currently possess to their neighbor (the $i$-th student passes a ball to the $(i + 1)$-th student, and the $N$-th student passes a ball to the $1$st student, as the $(N + 1)$-th student is considered to be the $1$st student). Your task is to determine whether, by repeating this operation at most $NM$ times, it is possible to achieve the goal. If possible, output a sequence of operations.

The input consists of a single test case of the following format. $$\begin{aligned} & N \ M \\ & a_{1,1} \ a_{1,2} \ \ldots \ a_{1,M} \\ & a_{2,1} \ a_{2,2} \ \ldots \ a_{2,M} \\ & \vdots \\ & a_{N,1} \ a_{N,2} \ \ldots \ a_{N,M} \end{aligned}$$ The first line contains two integers $N$ and $M$, where $N$ represents the number of students and $M$ represents the number of balls of each color. Both $N$ and $M$ are between $2$ and $100$ (for $N$) and $2$ and $100$ (for $M$), inclusive. Each of the following $N$ lines consists of $M$ positive integers $a_{i,1}, a_{i,2}, \ldots, a_{i,M}$. The integer $a_{i,j}$ represents the color of the $j$-th ball that the $i$-th student initially has. It is guaranteed that $1 \leq a_{i,j} \leq N$ and that each integer $1, 2, \ldots, N$ occurs $M$ times among $a_{i,j} \ (1 \leq i \leq N, 1 \leq j \leq M)$. It is also guaranteed that the initial state does not satisfy the goal condition.

Print $-1$ if it is impossible to achieve the goal state by at most $NM$ operations. Otherwise, print $K$ — the number of operations. In the following $K$ lines, print $N$ integers $c_{i,1}, c_{i,2}, \ldots, c_{i,N}$. Here, $c_{i,j}$ represents the color of the ball passed from the $j$-th student to the $(j+1)$-th student at the $i$-th operation.