Easy Version

Easy Version 只需构造任意一种合法方案即可。

容易想到把两个排列分开考虑。

方案 1

对于一个排列，考虑每次让 $i+1$ 接在 $i$ 的后面：

• 若 $i$ 不在最后一个位置上，就对其后面的那个位置操作，此时 $i$ 一定在最后一个位置上；
• 对 $i+1$ 操作，此时 $i$ 被移动到 $i+1$ 前面，且 $1\sim i$ 总是有序排列。

此时我们发现对任意一个长度为 $n$ 的排列都可以在 $2n$ 次操作内做到符合题目要求。

方案 2

考虑对任意排列中两个不同的数 $x$ 和 $y$，考虑依次对 $x,\ y,\ x$ 操作，

就交换了这两个数。

而 $1\sim n$ 的排列可以通过类似冒泡排序的过程在 $n$ 次交换内完成排序，故至多用 $3n$ 次操作。

（个人认为方案 1 更容易想到，方案 2 则是 CodeForces 提供的解法。）

考虑怎么使得两个排列操作次数相同。容易想到添加一段操作序列使得排列不变。

• 先对第一个位置操作，此时第一个位置上的数移动到最后一个位置，再对最后一个位置操作，则排列恢复原状；
• 设排列长度为 $n$，就重复 $n$ 次对第一个数操作，排列也恢复原状。

所以只需在操作次数奇偶性相同时用第一种方案补齐；奇偶性不同时则先用第二种方案对长度为奇数的排列操作，使得奇偶性相同，再用第一种方案补齐。否则一定不能成功，证明见题解末。

此时至多再操作 $n$ 次。总共不超过 $3n$ 次（方案 2 则是 $4n$ 次）。

Hard Version

考虑在序列开头加一个 $0$，再把数列放到环上（即 $0$ 代表序列的开始）：

考虑对一个数进行操作，则容易发现操作在环上等价于 $0$ 与这个数交换之后再进行旋转。

于是问题转化为，在序列 $[0,\ p_1,\ p_2,\ \cdots,\ p_n]$ 上每次将 $0$ 与另一个数交换，使得序列变为 $[0,\ 1,\ 2,\ \cdots,\ n],\ [n,\ 0,\ 1,\ 2,\ \cdots,\ n-1],\ [n-1,\ n,\ 0,\ 1,\ 2,\ \cdots,\ n-2],\ \cdots$ 之一。

此时容易联想到另一个模型：在一个排列上，要用交换使得排列升序，将每个位置指向位置上数应该在的位置，形成一个图，则交换次数至少是 $n$ 减去环的个数。

我们的目标是将这个模型运用到这个问题上。容易想到对每个环，设环的大小为 $x$：

• 若环包含 $0$，则需要 $x-1$ 步即可完成；
• 若环不包含 $0$，可以先将 $0$ 与环上的数交换，再用 $x-1$ 步交换完成环上的数的还原，最后将 $0$ 与交换出去的那个数交换即可。共需要 $x+1$ 步（对环大小 $\geq 2$ 的环而言）。

枚举序列操作的 $n$ 种可能结果，计算最优解即可。

而对于两个序列同时操作，只需求最优解时分别求出奇数步操作和偶数步操作的最优解，然后取奇数偶数中更优的即可（如果不理解，可以参考代码）。

时间复杂度 $\Theta(n^2)$。

在 CodeForces 的官方题解中，提到了一个关于 Easy Version 的加强版：$n\leq 10^5$，要求操作次数 $\leq 1.5\times 10^5$。这个问题可以用 Hard Version 的做法解决。因为不要求操作最优，所以只需对任意一种结果进行求解即可，而环对操作次数的贡献最大是 $1.5$（大小为 $2$ 的环需要 $3$ 次操作），故可以构造出符合要求的操作方案。

注：文末的代码为了方便，先求出了交换的数值的序列而非位置，再进行转换。

证明

求证：长度为偶数的序列 $a_1,\ a_2,\ \cdots,\ a_n$ 在操作后的逆序对数量奇偶性总是改变。这将得出操作序列的长度的奇偶性是确定的。

设对下标 $x$ 进行操作，则：

• $1\sim x-1$ 和 $x+1\sim n$ 中的逆序对数量保持不变；
• $1\sim x-1$ 中的一个数和 $x+1\sim n$ 构成的逆序对的数量的奇偶性也保持不变，因为总数 $(x-1)\cdot(n-x)$ 一定是偶数；
• $1\sim x-1$ 或 $x+1\sim n$ 中的一个数与 $x$ 构成的逆序对数量的奇偶性会改变，因为总数 $n-1$ 一定是奇数。

综上，逆序对的数量总是改变。

代码

#include<bits/stdc++.h>
using namespace std;
const int INF=100000;

struct SolveResult{
    int minEven,minOdd;
    vector<int> even,odd;
};

vector<int> solveOperations(vector<int> v,vector<int> op){
    vector<int> res;
    for(int x :op){
        int id=0;
        while(v[id]!=x)id++;
        res.push_back(id+1);
        vector<int> newv;
        for(int i=id+1;i<v.size();i++)newv.push_back(v[i]);
        newv.push_back(v[id]);
        for(int i=0;i<id;i++)newv.push_back(v[i]);
        v=newv;
    }
    return res;
}

SolveResult solve(vector<int> v){
    SolveResult res; res.minEven=res.minOdd=INF;
    int n=v.size();
    vector<int> a;
    a.push_back(0);
    for(int i=0;i<n;i++)a.push_back(v[i]);
    for(int k=0;k<=n;k++){
        vector<int> op;
        bool vis[2501]={};
        int pos[2501]={};
        pos[0]=k;
        for(int i=1;i<=k;i++)pos[n-k+i]=i-1;
        for(int i=k+1;i<=n;i++)pos[i-k]=i;
        for(int i=0;i<=n;i++){
            if(vis[i])continue;
            vector<int> t;
            vis[i]=true,t.push_back(i);
            int p=pos[a[i]];
            while(p!=i)t.push_back(p),vis[p]=true,p=pos[a[p]];
            if(i==0){
                for(int j=t.size()-1;j>0;j--)
                    op.push_back(a[t[j]]);
            }
            else{
                if(t.size()==1)continue;
                for(int j=t.size()-1;j>=0;j--)
                    op.push_back(a[t[j]]);
                op.push_back(a[*(t.rbegin())]);
            }
        }
        if(op.size()%2==0&&op.size()<res.minEven){
            res.minEven=op.size();
            res.even=op;
        }
        if(op.size()%2==1&&op.size()<res.minOdd){
            res.minOdd=op.size();
            res.odd=op;
        }
    }
    if(res.minOdd<INF)res.odd=solveOperations(v,res.odd);
    if(res.minEven<INF)res.even=solveOperations(v,res.even);
    return res;
}

int main(){
    int n,m;
    vector<int> a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x; scanf("%d",&x);
        a.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int x; scanf("%d",&x);
        b.push_back(x);
    }
    SolveResult A=solve(a),B=solve(b);
    vector<int> opA,opB; int step=INF;
    if(A.minEven<=INF&&B.minEven<=INF
        &&(step==INF||step>max(A.minEven,B.minEven)))
        step=max(A.minEven,B.minEven),opA=A.even,opB=B.even;
    if(A.minOdd<=INF&&B.minOdd<=INF
        &&(step==INF||step>max(A.minOdd,B.minOdd)))
        step=max(A.minOdd,B.minOdd),opA=A.odd,opB=B.odd;
    if(step==INF)return printf("-1\n"),0;
    while(opA.size()<opB.size())
        opA.push_back(1),opA.push_back(n);
    while(opA.size()>opB.size())
        opB.push_back(1),opB.push_back(m);
    printf("%d\n",step);
    for(int i=0;i<step;i++)
        printf("%d %d\n",opA[i],opB[i]);
    return 0;
}