题目描述

一家公司经营着 $N$ 个店铺，每个店铺都销售 $M$ 种不同的产品。该公司有一个大型仓库，产品在运送到商店之前在都会那里进行包装。每家商店将会收到相同数量的每种产品。因此，该公司将一定数量的相应产品分别包装到一个集装箱中，并用产品标识符标记该集装箱。产品由 $1$ 到 $M$ 的数字标识。因此，在包装结束后，仓库中将会有 $N×M$ 个集装箱，并且正好 $N$ 个集装箱贴有每个产品的对应标签。由于该仓库位于一个狭窄的建筑物内，所以集装箱排成了一排。但为了加快配送速度，仓库经理想要重新排列集装箱。由于将产品配送到商店是通过向每个商店发出一辆卡车来实现的，并且每辆卡车运载每种产品的一个集装箱，其合适的安排如下。该行最前部分 $M$ 个集装箱必须贴有不同的产品标签，该行的第二部分 $M$ 个集装箱必须贴有不同的产品标签，依此类推。不幸的是，在这一行的尽头只有一个空闲的地方可以放置一个集装箱。因此，必须通过依次拿起集装箱并将其移动到空闲位置来进行重新排列。重新排列后，空闲位置也必须在行的末尾。
目标是通过最少的移动以实现所需的重新排列。
现请您编写一个程序来计算需要最少移动多少次使得达成目标重排。

输入格式

第一行包含两个整数 $N$ 和 $M$。$N$ 是商店的数量，$M$ 是产品的数量。第二行包含 $N×M$ 个整数，即按初始顺序排列的集装箱标签。每个产品标识符 $x$ 在行中恰好出现 $N$ 次。

输出格式

第一行包含一个整数 $S$，这是达成集装箱所需排列所需的最小移动次数。以下 $S$ 行描述了重新排列。每行包含一对整数 $x$，$y$。一对 $x$，$y$ 描述了一个移动：位于 $x$ 位置的集装箱将移动到位置 $y$。位置由从 $1$ 到 $N×M+1$ 的数字标识；最初位置 $N×M+1$ 是空闲的（没有集装箱）。只有在移动之前位置 $y$ 是空闲的，从 $x$ 到 $y$ 的移动才是合法的。从 $x$ 移动到 $y$ 后，位置 $x$ 将是空闲的。

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

提示

数据规模与约定

对于 $100 \%$ 的数据，$1 \leq N \leq 400$，$1 \leq M \leq 400$，$1 \leq x \leq M$。

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Depot Rearrangement。
由