题意

给定一组数（1-n这n个数全排列中的一种），通过最少轮交换使序列变为升序。
每一轮可以选择任意组数对，两组数对之间不允许有相同的，在这轮中会将这些位置上的数两两交换。

题解

每个数应该在的位置是确定的，因此考虑每个位置上目前的数可能有三种情况：

1. 已经在应该的位置上，无需交换
2. 不在应该的位置上，但与另一个数交换位置后，两数都到了应该的位置上，即下图的一个小有向环，这样的两个数在第一轮交换就可以全部归位
   
3. 不在应该的位置上，但可以与其他的数构成一个有向的环
   
   这样的大环如果是点数为n的偶环，可以在第一轮通过交换拆成n/2个第二种情况那种形式的小环，因此共需两轮即可全部归位
   如果是n点奇环，则可以在第一轮中通过交换拆成n/2个小环和一个已被归位的点（下图中左下角的点），因此也共需两轮交换即可归位
   

本题的序列在化简之后可以证明只有三种情况:

1. 序列本身就为升序，不需要交换
2. 序列中不存在大环，只有小环，一轮交换搞定
3. 序列中存在大环，第一轮拆解大环并归位可能存在的小环，第二轮将产生的小环全部归位

所以最多只需要两轮就可以。

代码

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int a[N],v[N],t[N],n,f=0;
class b{
public:
    int x,y;
};
b ans[N];
bool ck(int n){//检查是否有序
    for(int i=1;i<=n;i++)if(a[i]!=i)return 0;
    return 1;
}
void pr(){//归位小环
    for(int i=1;i<=n;i++)if(a[i]!=i&&a[a[i]]==i)ans[++f].x=i,ans[f].y=a[i],a[a[i]]=a[i],a[i]=i;
}
void out(){
    printf("%d",f);
    for(int i=1;i<=f;i++)printf(" %d %d",ans[i].x,ans[i].y);
    printf("\n");
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    if(ck(n)==1){//本身有序
        printf("0\n");return 0;
    }
    pr();//归位小环
    if(ck(n)==1){
        printf("1\n");//只有小环，一轮交换即可
        out();
        return 0;
    }
    printf("2\n");//存在大环，需两轮交换
    for(int i=1;i<=n;i++){//拆解大环
        if(a[i]==i||a[a[i]]==i||v[i]==1);
        else{
            memset(t,0,sizeof(t));
            int j=a[i],l=0;v[i]=1;
            while(a[j]!=a[i]){
                t[++l]=j;
                j=a[j];
            }
            for(int k=1;k<=l/2;k++){
                ans[++f].x=t[k];ans[f].y=t[l+1-k];
                swap(a[ans[f].x],a[ans[f].y]);
                v[ans[f].x]=1;v[ans[f].y]=1;
            }
        }
    }
    out();//第一轮的操作输出
    f=0;
    pr();//将第一轮产生的小环归位
    out();//将第二***作输出
    return 0;
}