Jumbled Stacks

We are given a set of $n$ cards, labelled from 1 to $n$, which are distributed into $k$ stacks $S_1, S_2, \ldots, S_k$. Each stack has a limited capacity: the $i$-th stack, $S_i$, can contain at most $C_i$ cards. The only way to manipulate these cards is to take the top card of a stack and move it to the top of some other stack, as long as this does not exceed the capacity of the destination stack.

Using a sequence of such moves, we would like to rearrange the cards so that the first few stacks (0 or more) with the smallest indices are filled to capacity, the stack immediately after them is not filled to capacity (and may even be empty), and all stacks after that are completely empty. Moreover, if you stack all the stacks from $S_1$ at the bottom to $S_k$ at the top, the cards must be ordered from smallest to largest, with $1$ at the bottom and $n$ at the top.

It is guaranteed that $n \le \left(\sum_{i=1}^k C_i\right) - \max_{1 \le i \le k} C_i$.

Suppose we had $n = 6$ cards on $k = 3$ stacks, with capacities $C_1 = 4$, $C_2 = C_3 = 3$, and with the following initial state: $S_1 = [2, 3, 0, 0]$ (from bottom to top; $0$ indicates an empty slot), $S_2 = [4, 1, 6]$, $S_3 = [5, 0, 0]$. Then the desired end state is $S_1 = [1, 2, 3, 4]$, $S_2 = [5, 6, 0]$ and $S_3 = [0, 0, 0]$.

The first line contains two integers, $n$ (the number of cards) and $k$ (the number of stacks), separated by a space. The remaining $k$ lines describe the initial state of the stacks. The $i$-th of these lines describes $S_i$ and contains $C_i + 1$ integers, separated by spaces. The first of these integers is $C_i$ (the capacity of the stack $S_i$), and the rest are the labels of the cards on $S_i$, from bottom to top. If the stack $S_i$ contains fewer than $C_i$ cards (it could even be empty), the last few integers in the line are 0.

Print a sequence of moves that brings the stacks into the desired end state. For each move, output a line with two integers separated by a space: first the number of the stack the card is moved from, then the number of the stack it is moved to. The stacks are numbered from 1 to $k$, and the destination must differ from the source. The number of moves must not exceed $10^5$. After the last move, print a line containing "0 0" (without the quotation marks). If there are several possible solutions, you may output any of them.

• $1 \le n \le 100$
• $3 \le k \le 100$
• $1 \le C_i \le n$

This is the example discussed earlier in the problem statement. The sample output shows a sequence of 14 moves that brings the stacks into the desired end state.