Ball Sorting Game

You are given \(n+1\) vertical rods numbered from \(1\) to \(n+1\). Initially, rods \(1, 2, \dots, n\) each contain exactly \(m\) balls placed from bottom to top, and rod \(n+1\) is empty. The total \(n \times m\) balls come in exactly \(n\) colors, and each color appears exactly \(m\) times.

The balls on a single rod may be in any order initially. Your task is to move the balls so that all balls of the same color end up on the same rod. There is no restriction on which rod a color ends up on. The only allowed move is to take the top ball from one rod and place it on top of another rod, with the following conditions:

• The source rod must contain at least one ball.
• The destination rod must contain at most \(m-1\) balls.
• You may only move the top ball from the source rod.

In addition, you must complete the task using no more than 820000 moves. It is guaranteed that under these constraints a solution exists.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space.

Then follow \(n\) lines, each containing \(m\) integers. The \(i\)-th line describes rod \(i\) and lists the colors of the balls from bottom to top. Rod \(n+1\) is initially empty.

It is guaranteed that each color from \(1\) to \(n\) appears exactly \(m\) times in total.

outputFormat

On the first line, output an integer \(k\) representing the number of moves.

Then output \(k\) lines, each containing two integers \(x\) and \(y\) (with \(1 \le x,y \le n+1\)) indicating a move from rod \(x\) to rod \(y\).

The sequence of moves must achieve the goal and use no more than 820000 moves.

sample

2 1
2
1

3
1 3
2 1
3 2