题目
思路
我真的佛了，连 n = 2 n=2 n=2 的分我都写不出来！而且这是后面所有分析的基础！
为什么要用 “分馏” 操作？我真的吐了！我讨厌构造！讨厌还不够，我恨构造！恨得牙痒痒！义愤填膺！不枪毙十分钟，难解心头之恨！恨之入骨！
恨到想用我的鞋子狠狠踢它的屁股！因之以北斗百裂拳！加之以大玉螺旋丸！
分馏
这是用来解决 n = 2 n=2 n=2 的情况的。
我最初尝试着一种 “尽量让同色的相邻” 的方法，发现完全行不通。或者是倒推，也完全没有任何可行方案。
只有一种方案：分馏。即，让某一个栈中的某些特殊点被提取出来。方案其实很简单，只要有两个位置可以存储元素，那就可以一直往 A A A 桶塞元素，遇到特殊点就放 B B B 桶，那就被分开了。
对于 n = 2 n=2 n=2 的情况，说具体点好了，不妨设现在要分馏 A A A 栈，有 B B B 栈为满栈、 C C C 栈为空栈。
- 统计 A A A 栈中的特殊点（也就是颜色 1 1 1 的球）数量为 s s s 。
- 将 B B B 栈的顶上 s s s 个球放入 C C C 栈。实际上是要创造一个大小为 s s s 的 “临时寄存器” 。
- 将 A A A 栈弹空。过程中，遇到颜色 1 1 1 的球就放入 B B B 栈顶，否则入 C C C 栈顶。
- 将 C C C 栈中原本属于 A A A 栈的球回收至 A A A 栈，然后将 B B B 栈顶端 s s s 个球回收至 A A A 栈，最后将 C C C 栈中 s s s 个原本属于 B B B 栈的球回收至 B B B 栈。
不难发现，此时 A A A 栈中的颜色为 1 1 1 的球都被放到了栈顶，而 B B B 栈没有发生变化。只要对 B B B 栈再进行同样的操作，然后把二者的颜色为 1 1 1 的球收归 C C C 栈，最后 A A A 栈入 B B B 栈，就做完了！
依次分馏
首先看看分馏的代价（移动步数）。每一步代价分别是 s , m , m + s s,m,m+s s,m,m+s，总代价就是 2 m + 2 s 2m+2s 2m+2s 的。
那么，如果我们要解决 n > 2 n>2 n>2 的问题，只需要把每个栈中的颜色 1 1 1 分馏出来，放到一个栈里，剩下的统一递归。
多次分馏时，可以略微优化 2 m + 2 s 2m+2s 2m+2s 的单次代价，因为创造 “临时寄存器” 之后可以重复使用。我们找准一个栈，其余的栈按照 s s s 排序，就可以把 “临时寄存器” 一直保存到最后。
同时，“临时寄存器” 大小是 s s s 和 m − s m-s m−s，二者地位相等，所以 s ⩽ ⌊ m 2 ⌋ s\leqslant\lfloor\frac{m}{2}\rfloor s⩽⌊2m⌋ 。用文字语言表达就是，将 s s s 个分离出来，等价于把 m − s m-s m−s 个留下，所以可以取较小者。
每一轮的代价是什么呢？每个栈只有 2 m 2m 2m 的代价（出入各一次），所有栈合在一起提供 2 s ⩽ m 2s\leqslant m 2s⩽m 的 “临时寄存器” 构建代价。最后，用来当 “临时寄存器” 的栈需要单独进行分馏，又是一次 2 m + 2 s 2m+2s 2m+2s 的支出。然后以 m m m 的代价将所有分馏出的球放到空栈中，以 m m m 的代价制造出一个新的空栈。
显然
min
s
⩽
⌊
m
n
⌋
\min s\leqslant\lfloor\frac{m}{n}\rfloor
mins⩽⌊nm⌋，于是总代价为
f
(
n
)
=
2
m
⋅
(
n
−
1
)
+
m
+
2
m
+
2
⌊
m
n
⌋
+
2
m
T
(
n
)
=
∑
i
=
2
n
f
(
i
)
=
m
(
n
−
1
)
(
n
+
5
)
+
2
H
m
f(n) = 2m\cdot (n-1)+m+2m+2\left\lfloor{m\over n}\right\rfloor+2m\\ T(n)=\sum_{i=2}^{n}f(i)=m(n{\rm-}1)(n{\rm+}5)+2\mathcal H_m
f(n)=2m⋅(n−1)+m+2m+2⌊nm⌋+2mT(n)=i=2∑nf(i)=m(n−1)(n+5)+2Hm
其中
H
m
=
∑
i
=
2
n
⌊
m
i
⌋
\mathcal H_m=\sum_{i=2}^{n}\lfloor{m\over i}\rfloor
Hm=∑i=2n⌊im⌋，不好估算。代入
70
%
70\%
70% 的数据范围，显然是可以通过的。
然而想通过 100 % 100\% 100% 的数据就有点吃力了，因为此时 n 2 m n^2m n2m 都已经无法接受了，而每一轮中每个球有出有入基本是下界， f ( n ) = 2 n m f(n)=2nm f(n)=2nm 就超过了限制！
虽然题解区有一位说自己的暴力已经通过了。
二分分馏
所以又为什么要二分啊……反正就要坚持分馏战略，于是只能考虑不同的特殊点划分了……不能考虑改良分馏法吗。
又回到开头的那个想法：让异色的小球尽量不在同一个柱子上。于是把颜色 ⩽ m i d \leqslant mid ⩽mid 的球视为白色，其余视为黑色，目标是每个柱子上要么只有黑色，要么只有白色。
不过这个时候不能简单分馏了，因为并不存在一个空栈来放下所有的黑球。怎么办？放弃该做法。
从小处着眼。对于两个柱子上面的球，总有一种颜色有至少 m m m 个。不妨设是白色。那么我们先将 B B B 栈的白色球分馏到栈顶，然后让 A A A 栈的黑色球被分馏掉（可以暂时不将这 s s s 个黑色球从 “临时寄存器” 中取出）；将 B B B 栈顶的 s s s 个白色球塞入 A A A 栈，此时 A A A 是纯白的栈；将原本属于 A A A 的那 s s s 个黑色球放回 B B B 栈。
这样一次是 2 m + 2 s b + 2 m + 3 s a 2m+2s_b+2m+3s_a 2m+2sb+2m+3sa 的。显然 A , B A,B A,B 其中之一白球数量达到 ⌈ m 2 ⌉ \lceil{m\over 2}\rceil ⌈2m⌉，令其为 A A A 栈，显然 max ( s a , s b ) ⩽ ⌊ m 2 ⌋ \max(s_a,s_b)\leqslant\lfloor\frac{m}{2}\rfloor max(sa,sb)⩽⌊2m⌋，于是一次的支出不超过 5 ⌊ m 2 ⌋ + 4 m ⩽ 13 2 m 5\lfloor{m\over 2}\rfloor+4m\leqslant\frac{13}{2}m 5⌊2m⌋+4m⩽213m 。
每一轮有 n − 1 n-1 n−1 根柱子需要执行该操作，所以是 13 2 ( n − 1 ) m \frac{13}{2}(n-1)m 213(n−1)m 的。加上外层的分治，总支出是 13 2 n ⋅ ⌈ log 2 n ⌉ ⋅ m {13\over 2}n\cdot \lceil\log_2 n\rceil\cdot m 213n⋅⌈log2n⌉⋅m 的，而且根本跑不满。
注意 n = 2 n=2 n=2 时必须特判。因为上面的做法需要一个 A , B A,B A,B 栈以外的 “临时寄存器”，在 n = 2 n=2 n=2 时是做不到的。
代码
最后事实证明：对常数的要求并不高！比如创造 “临时寄存器” 的时候，就大大方方地创造 s s s 个（而不判断 s s s 与 ⌊ m 2 ⌋ \lfloor{m\over 2}\rfloor ⌊2m⌋ 的大小关系），也只用了 5 × 1 0 5 5\times 10^5 5×105 多一些的代价！加上这个判断，更是让操作次数降至 5 × 1 0 5 5\times 10^5 5×105 以内！甚至还有 “临时寄存器” 用完不立刻销毁的优化没有拿出手呢！
代码实现还是有一点点难度的。一定要用好函数！
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void writeint(int x){
if(x > 9) writeint(x/10);
putchar((x-x/10*10)^48);
}
inline int ABS(const int &x){
return x < 0 ? -x : x;
}
const int MaxN = 55;
const int MaxM = 405;
int a[MaxN][MaxM], n, m;
int count(int x,int mid){
int s = 0; rep(i,1,m) s += (a[x][i] <= mid); return s;
}
# define TOP(x) a[x][a[x][0]]
vector< pair<int,int> > ans;
# define CMD(x,y) do{ ans.push_back(make_pair(x,y));\
a[y][++ a[y][0]] = a[x][a[x][0] --]; } while(false)
int pos[MaxN]; // pos[0] is empty
inline void create(int x,int s){
rep(i,1,s) CMD(x,pos[0]);
}
inline void pourOut(int x,int y,int k){
for(; k; --k) CMD(x,y);
}
inline void moveUp(int x,int want,int helper,bool sgn=1,bool f=1){
int s = count(x,want), lost = 0;
if(!sgn) s = m-s; // > want
bool wxk = false; // if it's swapped
if((m>>1) < s && f){
wxk = 1; create(helper,m-s);
swap(helper,pos[0]); // temporary
} else create(helper,s);
for(int work=s; work; )
if((TOP(x) <= want) == sgn){
CMD(x,helper); -- work;
} else { CMD(x,pos[0]); ++ lost; }
pourOut(pos[0],x,lost); // normal balls
if(!f) return ; // keep %want% in register
pourOut(helper,x,s); // put %want% on the top
if(wxk){ // restore
swap(helper,pos[0]);
pourOut(pos[0],helper,m-s);
} else pourOut(pos[0],helper,s);
}
void solve(int l,int r){
if(l == r) return ; // already done
if(l+1 == r){ // n = 2
moveUp(pos[l],l,pos[r]);
moveUp(pos[r],l,pos[l]);
pourOut(pos[l],pos[0],count(pos[l],l));
pourOut(pos[r],pos[0],count(pos[r],l));
pourOut(pos[l],pos[r],a[pos[l]][0]);
swap(pos[0],pos[l]); return ;
}
int mid = (l+r)>>1;
for(int i=l+1; i<=r; ++i){
int s1 = count(pos[i-1],mid);
int s2 = count(pos[i],mid);
bool sgn = (s1+s2 >= m); // want
if((sgn && (m>>1) < m-s1)
|| (!sgn && (m>>1) < s1)) // fill pos[i-1]
swap(pos[i],pos[i-1]), s1 = s2;
if(!s1 || s1 == m) continue; // well...
int aid = (i == r) ? pos[l] : pos[i+1];
moveUp(pos[i],mid,aid,sgn); // extract i
moveUp(pos[i-1],mid,aid,sgn^1,false);
pourOut(pos[i],pos[i-1],m-a[pos[i-1]][0]);
pourOut(aid,pos[i],m-a[pos[i]][0]);
pourOut(pos[0],aid,a[pos[0]][0]);
}
for(int i=l,j=r; i<j; ++i,--j){
for(; i<j&&TOP(pos[i])<=mid; ++i);
for(; i<j&&TOP(pos[j])>mid; --j);
swap(pos[i],pos[j]);
}
solve(l,mid), solve(mid+1,r);
}
int main(){
n = readint(), m = readint();
rep(i,1,n) rep(j,1,m)
a[i][j] = readint();
rep(i,1,n) // init
pos[i] = i, a[i][0] = m;
pos[0] = n+1; solve(1,n);
writeint(ans.size());
putchar('\n');
for(auto it : ans){
writeint(it.first);
putchar(' ');
writeint(it.second);
putchar('\n');
}
return 0;
}