3916.移球游戏(NOIP2020)

## 题目描述

小 $ C $ 正在玩一个移球游戏，他面前有 $ n+1 $ 根柱子，柱子从 $ 1∼n+1 $ 编号，其中 $ 1 $ 号柱子、 $ 2 $ 号柱子、⋯⋯、 $ n $ 号柱子上各有 $ m $ 个球，它们自底向上放置在柱子上， $ n+1 $ 号柱子上初始时没有球。

这 $ n\timesm $ 个球共有 $ n $ 种颜色，每种颜色的球各 $ m $ 个。

初始时一根柱子上的球可能是五颜六色的，而小 $ C $ 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，**而每种颜色的球最后放置在哪根柱子则没有限制**。

小 $ C $ 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。

更具体地，将 $ x $ 号柱子上的球移动到 $ y $ 号柱子上的要求为：

1. $ x $ 号柱子上至少有一个球；
2. $ y $ 号柱子上至多有 $ m-1 $ 个球；
3. 只能将 $ x $ 号柱子最上方的球移到 $ y $ 号柱子的最上方。

小 $ C $ 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的**操作次数不能超过** $ 820000 $ 。

**换句话说，小 $ C $ 需要使用至多 $ 820000 $ 次操作完成目标。**

小 $ C $ 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 $ C $ 的目标。

合法的方案可能有多种，**你只需要给出任意一种，题目保证一定存在一个合法方案。**

## 输入格式

第一行两个用空格分隔的整数 $ n,m $ 。分别表示球的颜色数、每种颜色球的个数。

接下来 $ n $ 行每行 $ m $ 个用单个空格分隔的整数，第 $ i $ 行的整数按自底向上的顺序依次给出了 $ i $ 号柱子上的球的颜色。

## 输出格式

**本题采用自定义校验器（special judge）评测。**

你的输出的第一行应该仅包含单个整数 $k$，表示你的方案的操作次数。你应保证 $ 0\lek\le820000 $ 。

接下来 $ k $ 行每行你应输出两个用单个空格分隔的正整数 $ x,y $ ，表示这次操作将 $ x $ 号柱子最上方的球移动到 $ y $ 号柱子最上方。你应保证 $ 1\lex,y\len+1 $ 且 $ x\ney $ 。

## 数据范围

| 测试点编号 | n\le | m\le |
| --- | --- | --- |
| 1∼2 | 2 | 20 |
| 3∼5 | 10 | 20 |
| 6∼8 | 50 | 85 |
| 9∼14 | 50 | 300 |
| 15∼20 | 50 | 400 |

对于所有测试点，保证 $ 2\len\le50 $ ， $ 2\lem\le400 $ 。

```in4
2 3
1 1 2
2 1 2
```

```out4
6
1 3
2 3
3 1
3 2
```

## 说明

柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。

| 操作 | 1 号柱子 | 2 号柱子 | 3 号柱子 |
| --- | --- | --- | --- |
| 初始 | 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 |  |