problem

[POI 2025/2026 #1] 并非哈诺塔 / Hanoj。

考场上少写一个 case 挂到了 27.

sol

考虑什么时候能够完成要求。

如果存在一个空柱子，那么有一个显而易见的构造就是将 $1\sim n$ 依次移到这个空柱子上，此时操作次数为 $n$。

同理，如果一个柱子上的盘子编号为 $\{1,2,3,\cdots,i\}$，其等价于一个空柱子，因为任何盘子都能移动过来，所以把 $i+1\sim n$ 依次移到这根柱子上即可，此时操作次数为 $n-i$，注意这个情况次数更少，所以要比存在空柱子优先判断。

如果以上两种情况都不满足，则要改变 $1$ 所在柱子结构必然会移动 $1$，而移动 $1$ 无论如何都不合法，所以考虑能否将一个柱子变为空柱子，这个问题等价于找到两根柱子 $A,B$ 使得 $\max\{A\}<\min\{B\}$。

发现对于一个固定的柱子 $B$ 改变 $A$ 不会影响答案，所以固定 $A$ 为 $\max\{A\}$ 最小的柱子，如果存在一对柱子 $C,B(C\neq A)$ 满足条件则 $A,B$ 一定满足条件。

那么枚举 $B$ 判断，然后找到满足条件的盘子数最少的柱子即可，构造方案是简单的。

如果找不到这样一对 $A,B$ 则无解，输出 $-1$。

code

const int N=1e6+5;
int n,m,in[N],p;
vector<int>num[N];
bool f1=1,f2=0;
void Main(){
    cin>>n>>m;
    for(int i=1,k;i<=m;i++){
        cin>>k;
        if(!k)  f2=1,p=i;
        else{
            for(int j=1,x;j<=k;j++) cin>>x,in[x]=i,num[i].push_back(x);
        }
    }
    if(num[in[1]].back()==num[in[1]].size()){
        cout<<n-num[in[1]].size()<<"\n";
        for(int i=num[in[1]].back()+1;i<=n;i++)   cout<<in[i]<<" "<<in[1]<<"\n";
    }else if(f2){
        cout<<n<<"\n";
        for(int i=1;i<=n;i++)   cout<<in[i]<<" "<<p<<"\n";
    }else{
		int v=0x3f3f3f3f,p,va=0x3f3f3f3f,pa=0;
		for(int i=1;i<=m;i++){
			if(num[i].back()<v)	v=num[i].back(),p=i;
		}
		for(int i=1;i<=m;i++){
			if(i!=p&&num[i][0]>v&&num[i].size()<va)	va=num[i].size(),pa=i;
		}
		if(!pa)	cout<<"-1\n";
		else{
			cout<<n+va<<"\n";
			for(auto it:num[pa])	in[it]=p,cout<<pa<<" "<<p<<"\n";	
			for(int i=1;i<=n;i++)   cout<<in[i]<<" "<<pa<<"\n";
		}
	}
}