#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
bool isOrd(vector<ll>&v)
{
ll i;
for(i=0; i<sz(v); i++)
if(i!=v[i])
return 0;
return 1;
}
vector<ll>x,y,s;
vector<ll>in, m, v, mal;
void can(ll M, vector<ll>&P, vector<ll>&Q)
{
ll N=sz(s);
iota(all(in),0);
ll i, j, k, l, end=N-1;
for(i=M-1; i>=0; i--)
swap(in[x[i]],in[y[i]]);
v=s;
for(i=0; i<N; i++)
{
if(v[i]!=in[i])
mal[v[i]]=i;
else
mal[v[i]]=-1;
m[in[i]]=i;
}
for(i=0; i<M; i++)
{
if(v[x[i]]!=in[x[i]])
mal[v[x[i]]]=-1;
if(v[y[i]]!=in[y[i]])
mal[v[y[i]]]=-1;
swap(v[x[i]],v[y[i]]);
swap(m[in[x[i]]],m[in[y[i]]]);
swap(in[x[i]],in[y[i]]);
if(v[x[i]]!=in[x[i]])
mal[v[x[i]]]=x[i];
if(v[y[i]]!=in[y[i]])
mal[v[y[i]]]=y[i];
while(end>=0&&mal[end]==-1)
end--;
if(end>=0)
{
k=mal[end];
l=m[v[k]];
mal[end]=-1;
mal[v[l]]=-1;
if(v[l]!=in[k])
mal[v[l]]=k;
swap(v[k],v[l]);
P[i]=k;
Q[i]=l;
}
else
{
P[i]=0;
Q[i]=0;
}
}
while(end>=0&&mal[end]==-1)
end--;
if(end<0)
return;
P[0]=-1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
ll l=1, r=(N)-1, piv, pos=(N), i;
in.resize(N);
m.resize(N);
x.resize(M);
y.resize(M);
mal.resize(N);
for(i=0; i<M; i++)
{
x[i]=X[i];
y[i]=Y[i];
}
s.resize(N);
for(i=0; i<N; i++)
s[i]=S[i];
if(isOrd(s))
return 0;
vector<ll>a(M),b(M);
while(l<=r)
{
piv=(l+r)/2;
can(piv,a,b);
if(a[0]!=-1)
{
pos=piv;
r=piv-1;
}
else
l=piv+1;
}
vector<ll>p(pos),q(pos);
can(pos,p,q);
for(i=0; i<sz(p); i++)
{
P[i]=p[i];
Q[i]=q[i];
}
return pos;
}
