Problem Description

Little C is playing a ball moving game. In front of him, there are \( n + 1 \) pillars numbered from \( 1 \) to \( n + 1 \). Pillars \( 1 \) through \( n \) each contain \( m \) balls stacked from bottom to top, while pillar \( n + 1 \) initially has no balls. These \( n \times m \) balls come in \( n \) colors, with each color having exactly \( m \) balls.

Initially, the balls on a pillar may be of various colors. Little C's task is to move all balls of the same color to the same pillar. The final placement of each color's balls on which pillar is not restricted.

Little C can achieve this goal through several operations, where each operation moves a ball from one pillar to another. Specifically, moving a ball from pillar \( x \) to pillar \( y \) requires:

1. Pillar \( x \) must have at least one ball.
2. Pillar \( y \) can have at most \( m - 1 \) balls.
3. Only the top ball of pillar \( x \) can be moved to the top of pillar \( y \).

Although the goal is not difficult to achieve, Little C decides to add a challenge: the number of operations must not exceed \( 820000 \). In other words, Little C needs to complete the task using at most \( 820000 \) operations.

Little C is stumped, but he believes you can solve it. Please provide an operation plan to achieve Little C's goal. There may be multiple valid solutions; you only need to provide any one. The problem guarantees that at least one valid solution exists.

Input Format

The first line contains two integers \( n \) and \( m \) separated by a space, representing the number of colors and the number of balls per color, respectively.
The next \( n \) lines each contain \( m \) integers separated by single spaces. The integers on the \( i \)-th line, given in bottom-up order, represent the colors of the balls on the \( i \)-th pillar.

Output Format

This problem uses a custom checker (special judge) for evaluation.
Your output should start with a single integer \( k \), indicating the number of operations in your solution. Ensure \( 0 \le k \le 820000 \).
The next \( k \) lines should each contain two positive integers \( x \) and \( y \) separated by a single space, indicating that the top ball of pillar \( x \) is moved to the top of pillar \( y \). Ensure \( 1 \le x, y \le n + 1 \) and \( x \ne y \).

Sample Input and Output

Sample Input #1

2 3
1 1 2
2 1 2

Sample Output #1

6
1 3
2 3
2 3
3 1
3 2
3 2

Sample Input #2

See the attached file ball/ball2.in

Sample Output #2

See the attached file ball/ball2.ans

Sample Input #3

See the attached file ball/ball3.in

Sample Output #3

See the attached file ball/ball3.ans

Notes

[Sample #1 Explanation]

The content of the pillars is given in bottom-up order, showing the colors of the balls on each pillar.

[Data Range]

For all test points, \( 2 \le n \le 50 \) and \( 2 \le m \le 400 \).

[Checker]

For convenience in testing, a checker.cpp file is provided in the ball directory of the attachments. You can compile and use this program to verify your output files. Note that this checker may not be identical to the one used in the final evaluation. You do not need to understand the specifics of its code.

Compile command: g++ checker.cpp -o checker -std=c++11.

Usage: checker <inputfile> <outputfile>, where the arguments represent the input file and your output file, respectively.

If your output numbers are out of the valid range, the checker will provide corresponding feedback. If your output numbers are within the correct range but the solution is incorrect, the checker will provide brief error messages:

1. A x, indicating an illegal operation at the \( x \)-th step.
2. B x, indicating an illegal state on the \( x \)-th pillar after all operations.

If your solution is correct, the checker will return OK.

见题面 Input 部分

见题面 Output 部分