P7115 [NOIP2020] Ball Moving Game

Xiao C is playing a ball moving game. There are $n + 1$ poles in front of him, numbered from $1$ to $n + 1$. Poles $1$, $2$, $\ldots$, $n$ each initially have $m$ balls stacked from bottom to top, while pole $n + 1$ initially has no balls. There are $n \times m$ balls in total, with $n$ colors, and each color has exactly $m$ balls. Initially, the balls on a single pole may have many different colors. Xiao C’s task is to move all balls of the same color onto the same pole. This is the only goal, and there is no restriction on which pole each color finally ends up on. Xiao C can achieve this goal using a sequence of operations. In one operation, he moves one ball from one pole to another. More specifically, moving a ball from pole $x$ to pole $y$ must satisfy: 1. Pole $x$ has at least one ball. 2. Pole $y$ has at most $m - 1$ balls. 3. Only the top ball of pole $x$ can be moved to the top of pole $y$. Since the goal is not hard to achieve, Xiao C decided to make it more challenging: while achieving the goal, the total number of operations must not exceed $820000$. In other words, Xiao C must complete the goal in at most $820000$ operations. Xiao C is stuck, but he believes you can solve it. Please output an operation plan to achieve Xiao C’s goal. There may be many valid plans; you only need to output any one of them. It is guaranteed that at least one valid plan exists.

The first line contains two integers $n, m$ separated by spaces, representing the number of colors of balls and the number of balls of each color. The next $n$ lines each contain $m$ integers separated by single spaces. For line $i$, the integers give the colors of the balls on pole $i$ in order from bottom to top.

This problem is judged with a special judge. The first line of your output should contain only a single integer $k$, indicating the number of operations in your plan. You must ensure that $0 \le k \le 820000$. The next $k$ lines should each contain two positive integers $x, y$ separated by a single space, meaning that this operation moves the top ball of pole $x$ to the top of pole $y$. You must ensure that $1 \le x, y \le n + 1$ and $x \ne y$.

**[Sample #1 Explanation]** The contents in the poles are given as: for each pole, the colors of its balls are listed from bottom to top. | Operation | Pole $1$ | Pole $2$ | Pole $3$ | |:-:|:-:|:-:|:-:| | Initial | $1\ 1\ 2$ | $2\ 1\ 2$ | | | $1\ 3$ | $1\ 1$ | $2\ 1\ 2$ | $2$ | | $2\ 3$ | $1\ 1$ | $2\ 1$ | $2\ 2$ | | $2\ 3$ | $1\ 1$ | $2$ | $2\ 2\ 1$ | | $3\ 1$ | $1\ 1\ 1$ | $2$ | $2\ 2$ | | $3\ 2$ | $1\ 1\ 1$ | $2\ 2$ | $2$ | | $3\ 2$ | $1\ 1\ 1$ | $2\ 2\ 2$ | | **[Constraints]** | Test Point ID | $n \le$ | $m \le$ | |:-:|:-:|:-:| | $1 \sim 2$ | $2$ | $20$ | | $3 \sim 5$ | $10$ | $20$ | | $6 \sim 8$ | $50$ | $85$ | | $9 \sim 14$ | $50$ | $300$ | | $15 \sim 20$ | $50$ | $400$ | For all test points, it is guaranteed that $2 \le n \le 50$ and $2 \le m \le 400$. **[Checker]** To make it easier for contestants to test, we provide a `checker.cpp` file in the `ball` directory in the attachments. You can compile this program and use it to check your output file. However, note that it is not exactly the same as the checker used in the final judging. You also do not need to care about the exact details of its code. The compile command is: `g++ checker.cpp −o checker -std=c++11`. Usage of `checker` is: `checker `, where the parameters are the input file and your output file, respectively. If the range of numbers in your output is invalid, the checker will print corresponding messages. If the range is correct but the plan is wrong, it will print brief error information: 1. `A x`, meaning the operation is invalid at the $x$-th operation. 2. `B x`, meaning after all operations are executed, the balls on pole $x$ are invalid. If your plan is correct, the checker will print `OK`. Translated by ChatGPT 5