3916.T2-[NOIP2020] 移球游戏(ball)

# T2-[NOIP2020] 移球游戏（ball）

## 题目描述

小 C 正在玩一个移球游戏。他面前有 $n+1$ 根柱子，编号为 $1$ 至 $n+1$。初始时，前 $n$ 根柱子上各有 $m$ 个球，球自底向上放置在柱子上，第 $n+1$ 根柱子为空。

这 $n\times m$ 个球共有 $n$ 种颜色，每种颜色恰有 $m$ 个球。每根柱子最多容纳 $m$ 个球。

初始时，一根柱子上的球可能有多种颜色。小 C 的目标是将所有同种颜色的球移到同一根柱子上。**每种颜色的球最终放在哪根柱子上没有限制。**

一次操作可以将 $x$ 号柱子最上方的球移动到 $y$ 号柱子的最上方，但必须满足以下条件：

1. $1\le x,y\le n+1$，且 $x\ne y$；
2. $x$ 号柱子上至少有一个球；
3. $y$ 号柱子上至多有 $m-1$ 个球。

请给出一个操作次数不超过 $820000$ 的方案，使所有同种颜色的球都位于同一根柱子上。

题目保证存在满足要求的方案。合法方案可能有多种，你只需要输出任意一种，**不需要最小化操作次数**。

## 输入格式

第一行包含两个整数 $n,m$，分别表示球的颜色数和每种颜色的球数。

接下来 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行按自底向上的顺序给出 $i$ 号柱子上各个球的颜色。

## 输出格式

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

第一行输出一个整数 $k$，表示操作次数，要求 $0\le k\le 820000$。

接下来 $k$ 行，每行输出两个整数 $x,y$，表示将 $x$ 号柱子最上方的球移动到 $y$ 号柱子的最上方。

每次操作必须满足题目描述中的全部条件。完成所有操作后，所有同种颜色的球必须位于同一根柱子上。

**输出任意满足要求的方案即可。操作次数、操作序列及最终各颜色对应的柱子均不需要与样例输出一致。**

## 数据范围

对于所有测试点，保证：

- $2\le n\le 50$；
- $2\le m\le 400$；
- 共有 $n$ 种颜色，每种颜色恰有 $m$ 个球；
- 存在操作次数不超过 $820000$ 的合法方案。

各测试点的范围如下：

| 测试点编号 | $n$ 的上限 | $m$ 的上限 |
| --- | --- | --- |
| $1\sim 2$ | $2$ | $20$ |
| $3\sim 5$ | $10$ | $20$ |
| $6\sim 8$ | $50$ | $85$ |
| $9\sim 14$ | $50$ | $300$ |
| $15\sim 20$ | $50$ | $400$ |

## 样例输入

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

## 样例输出

```
6
1 3
2 3
2 3
3 1
3 2
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 | |

经过这 $6$ 次操作，颜色为 $1$ 的球全部位于 $1$ 号柱子上，颜色为 $2$ 的球全部位于 $2$ 号柱子上，满足要求。