Description

A company operates $N$ stores, and each store sells $M$ different products. The company has a large depot, where products are packed before being shipped to the stores. Each store will receive the same amount of each product. Therefore, the company packs a certain amount of the same product into one container and marks the container with the product identifier.

Products are identified by the numbers from $1$ to $M$. Thus, after packing is finished, there will be $N×M$ containers in the depot, and for each product label there are exactly $N$ containers with that label. Since the depot is located in a narrow building, the containers are placed in a single line.

To speed up deliveries, the depot manager wants to rearrange the containers. Since products are delivered by sending one truck to each store, and each truck carries one container of each product, the desired arrangement is as follows: the first $M$ containers in the line must have pairwise different product labels, the second $M$ containers must also have pairwise different product labels, and so on. Unfortunately, there is only one free space at the end of the line, which can hold one container. Therefore, the rearrangement must be done by repeatedly picking up one container and moving it into the free space. After rearrangement, the free space must also be at the end of the line.

The goal is to achieve the required rearrangement using the minimum number of moves. You are asked to write a program to compute the minimum number of moves needed to reach a valid arrangement.

Input Format

The first line contains two integers $N$ and $M$. $N$ is the number of stores, and $M$ is the number of products. The second line contains $N×M$ integers, the labels of the containers in their initial order. Each product identifier $x$ appears exactly $N$ times in the line.

Output Format

The first line contains an integer $S$, the minimum number of moves required to reach a valid arrangement. The next $S$ lines describe the rearrangement. Each line contains a pair of integers $x$, $y$. The pair $x$, $y$ describes one move: the container at position $x$ is moved to position $y$.

Positions are numbered from $1$ to $N×M+1$; initially, position $N×M+1$ is the free space (it has no container). A move from $x$ to $y$ is legal only if position $y$ is free before the move. After moving from $x$ to $y$, position $x$ becomes the free space.

5  6
4 1 3 1 6 5 2 3 2 3 5 6 2 1 4 5 6 4 1 3 2 4 5 5 1 2 3 4 6 6

8
9 31
18 9
10 18 
4 10
31 4
30 31
24 30
31 24

Hint

Constraints

For $100\%$ of the testdata, $1 \leq N \leq 400$, $1 \leq M \leq 400$, $1 \leq x \leq M$.

Notes

From CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005, Depot Rearrangement.
Translated and organized by

Translated by ChatGPT 5