#include "sorting.h"
#include <algorithm>
#include <stdio.h>
#include <vector>

namespace
{

typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}

std::vector<std::pair<uint,uint> >solve(std::vector<uint>A,std::vector<std::pair<uint,uint> >B)
{
    uint n=A.size();
    std::vector<uint>Now=A;uint p=0;
    auto roll=[&](uint t)
    {
        while(p<t)std::swap(Now[B[p].first],Now[B[p].second]),p++;
        while(p>t)p--,std::swap(Now[B[p].first],Now[B[p].second]);
    };
    auto get=[&]()
    {
        static bol B[200005];
        for(uint i=0;i<n;i++)B[i]=false;
        std::vector<std::vector<uint> >V;
        for(uint i=0;i<n;i++)if(!B[i])
        {
            V.push_back({i}),B[i]=true;
            while(!B[Now[V.back().back()]])V.back().push_back(Now[V.back().back()]),B[V.back().back()]=true;
        }
        return V;
    };
    uint l=0,r=n;
    while(l<r)
    {
        uint mid=(l+r)>>1,s=0;roll(mid);auto t=get();for(auto v:t)s+=v.size()-1;
        if(s>mid)l=mid+1;else r=mid;
    }
    roll(l);
    std::vector<std::pair<uint,uint> >Ans;
    auto t=get();
    for(auto s:t)for(uint j=1;j<s.size();j++)Ans.push_back({s[0],s[j]});
    while(Ans.size()<l)Ans.push_back({0,0});
    std::vector<uint>Back(n);
    for(uint i=0;i<n;i++)Now[i]=Back[i]=i;
    for(uint i=l-1;~i;i--)
        std::swap(Now[B[i].first],Now[B[i].second]),std::swap(Back[Now[B[i].first]],Back[Now[B[i].second]]);
    for(uint i=0;i<l;i++)
        std::swap(Now[B[i].first],Now[B[i].second]),std::swap(Back[Now[B[i].first]],Back[Now[B[i].second]]),
        Ans[i]={Back[Ans[i].first],Back[Ans[i].second]};
    return Ans;
}

}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    std::vector<uint>A(N);
    std::vector<std::pair<uint,uint> >B(N);
    for(int i=0;i<N;i++)A[i]=S[i],B[i]={X[i],Y[i]};
    B=solve(A,B);
    for(int i=0;i<(int)B.size();i++)P[i]=B[i].first,Q[i]=B[i].second;
    return B.size();
}

/*

g++ 233.cpp grader.cpp -o code -std=c++11

*/