It's him and I, Aquemini.
You, the aquamist, are initially given $$$n$$$ stacks that can each hold up to $$$m$$$ blocks. Initially, each stack $$$i$$$ except the $$$n$$$-th stack is full with $$$m$$$ blocks that are all labeled $$$i$$$ (blocks with the same label are indistinguishable from each other). The $$$n$$$-th stack is initially empty, having no blocks on it.
In a single move, you can do the following:
- Take a block off the top of a stack and place it on top of another stack, without causing a stack to have more than $$$m$$$ blocks on it.
You are also given the final arrangement of labeled blocks in each stack, ordered from the bottom to the top of the stack, and your goal is to determine a sequence of moves to get from the initial arrangement to this final arrangement.
The first line contains two integers, $$$n$$$ and $$$m$$$ $$$(3 \le n \le 50, 1 \le m \le 100)$$$.
Next, $$$n$$$ lines follow. On the $$$i$$$-th of these lines, there is first a single integer $$$s_i$$$ and then there are $$$s_i$$$ integers that follow $$$(0 \le s_i \le m)$$$. The $$$j$$$-th of these integers on the $$$i$$$-th line, $$$a_{i,j}$$$, denotes that the $$$j$$$-th-from-the-bottom block on the $$$i$$$-th stack has the label $$$a_{i,j}$$$ in the final arrangement.
It is guaranteed that the number of blocks with a label $$$i$$$ is the same between the initial arrangement and final arrangement for all values of $$$i$$$.
First print a single number $$$k$$$, the number of moves in your sequence $$$(0 \le k \lt 2 \cdot 10^6)$$$. You do NOT have to minimize the number of moves in the sequence. It is provable that there always exists a solution in less than $$$2 \cdot 10^6$$$ moves given the specified input conditions.
Next, print $$$k$$$ lines. On the $$$i$$$-th line, print two numbers $$$x_i$$$ and $$$y_i$$$, denoting that on the $$$i$$$-th move, you will take a block from the top of stack $$$x_i$$$ and move it to the top of stack $$$y_i$$$. It must be the case that there exists at least one block on stack $$$x_i$$$ and less than $$$m$$$ blocks on stack $$$y_i$$$ before this move is made.
4 3 3 2 1 1 3 2 3 2 2 3 3 1 1
9 1 4 1 4 1 4 2 1 2 1 3 2 1 2 4 1 4 1
The following diagram shows the final arrangement of all the stacks from left to right.
Problem Credits: Eric Yachbes
