给定 \(n+1\) 个柱子，其中有一个空柱，其余 \(n\) 个上分别有 \(m\) 个球，球分为 \(n\) 种颜色，每种颜色各 \(m\) 个。
可以在柱子间不断移动球，一个柱子最多同时存在 \(m\) 个球。
要求构造一种移球方案，使得同种颜色球移动到同一根柱子，步数 \(\leq 820000\)。
先想简单情况，这是所有构造题的基本思路来源。
假设有 \(2\) 个柱子，球的颜色为 \(0/1\)，结合一个空柱，如何将柱子变为上面一段是 \(0\) 下面一段是 \(1\) 的状态。
首先显然排序一个柱子需要结合另一个非空柱，因为仅仅一个空柱只能将整个颜色串倒序而已。
假设需要排序的柱子中有 \(a\) 个 \(0\) 号球。
那么只需要将那个非空柱的 \(a\) 个球移动到空柱，然后将 \(a\) 中的 \(0\) 移动到它，\(1\) 移动到空柱。
最后在先将 \(1\) 放回来，后将 \(0\) 放回来即可，最后将非空柱还原。
那么总操作数最大为 \(4m\)，可以卡个小常数，每次将 \(0/1\) 中较少个的作为 \(a\)，总数变为 \(3m\)。
针对两种颜色，都排序之后简单讨论一下就能得到答案。
考虑扩展到多种颜色，一个关键思想是利用分治，每次将 \(\leq mid\) 的颜色当做 \(0\)，\(>mid\) 的当做 \(1\)。
这样每次将 \(0/1\) 分离后，分治下去即可得到答案。
分离的方法是，先将所有 \(n\) 个柱子排序，然后每次找到两个柱子，使它们的 \(0/1\) 加起来 \(\geq m\)。
简单讨论一下，自然可以在 \(3m\) 的步数内，得到一个全 \(0/1\) 柱，这个操作只需要做 \(n/2\) 次。
那么总次数就是 \(4.5nm\log n<5nm\log n\) 的步数内得到答案，计算发现远小于 \(820000\)。
实现思路清晰其实也不难写（
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
const int N = 55, M = 410;
int n, m, tot[N], a[N][M], b[N][2];
vector<PII> ans;
int read(){
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
void Add(int u, int v){
a[v][++ tot[v]] = a[u][tot[u] --];
ans.PB(MP(u, v));
}
void Move(int u, int v, int x) {while(x --) Add(u, v);}
void Get(int l, int r, vector<int> S){
if(l == r) return;
int mid = (l + r) >> 1;
for(int i = 0; i < (int) S.size(); i ++){
int u = S[i]; b[u][0] = b[u][1] = 0;
for(int j = 1; j <= m; j ++) b[u][a[u][j] > mid] ++;
int v = (u == 1) ? 2 : 1;
int w = (b[u][0] < b[u][1]) ? 0 : 1;
Move(v, n + 1, b[u][w]);
for(int j = m; j >= 1; j --)
if((a[u][j] > mid) == w) Add(u, v);
else Add(u, n + 1);
if(w == 0){
Move(n + 1, u, b[u][!w]);
Move( v, u, b[u][ w]);
}
else{
Move( v, u, b[u][ w]);
Move(n + 1, u, b[u][!w]);
}
Move(n + 1, v, b[u][w]);
}
while(true){
for(int i = 0; i < (int) S.size(); i ++){
int u = S[i]; b[u][0] = b[u][1] = 0;
for(int j = 1; j <= m; j ++) b[u][a[u][j] > mid] ++;
}
int Mx = 0, u = 0, _Mx = 0, v = 0;
for(int i = 0, w; i < (int) S.size(); i ++)
if(b[w = S[i]][0] && b[w][1]){
if(b[w][0] >= Mx)
_Mx = Mx, v = u, Mx = b[w][0], u = w;
else if(b[w][0] > _Mx)
_Mx = b[w][0], v = w;
}
if(Mx + _Mx >= m){
Move( v, n + 1, m);
Move( u, v, b[u][0]);
Move(n + 1, u, b[v][1]);
Move(n + 1, v, m - b[u][0]);
Move(n + 1, u, b[u][0] - b[v][1]);
continue;
}
Mx = 0, u = 0, _Mx = 0, v = 0;
for(int i = 0, w; i < (int) S.size(); i ++)
if(b[w = S[i]][0] && b[w][1]){
if(b[w][1] >= Mx)
_Mx = Mx, v = u, Mx = b[w][1], u = w;
else if(b[w][1] > _Mx)
_Mx = b[w][1], v = w;
}
if(Mx + _Mx >= m){
Move(u, n + 1, b[u][0]);
Move(v, n + 1, b[v][0]);
Move(v, u, m - b[u][1]);
Move(n + 1, v, b[u][0] + b[v][0]);
continue;
}
break;
}
vector<int> LS, RS;
for(int i = 0; i < (int) S.size(); i ++){
int u = S[i];
if(a[u][m] <= mid) LS.PB(u);
else RS.PB(u);
}
Get( l, mid, LS);
Get(mid + 1, r, RS);
}
int main(){
n = read(), m = read();
vector<int> S;
for(int i = 1; i <= n; i ++){
tot[i] = m; S.PB(i);
for(int j = 1; j <= m; j ++) a[i][j] = read();
}
Get(1, n, S);
printf("%d\n", ans.size());
for(int i = 0; i < (int) ans.size(); i ++)
printf("%d %d\n", ans[i].X, ans[i].Y);
return 0;
}