#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>s,x,y;
vector<pair<int,int>>ans;
bool ver(int r, vector<int>val){
ans.clear();
ans.assign(r,{0,0});
vector<int>valf(n),posf(n),pos(n);
for(int i=0;i<n;i++){
posf[val[i]]=i;
valf[i]=val[i];
pos[val[i]]=i;
}
//simular E
for(int i=0;i<r;i++){
swap(posf[valf[x[i]]],posf[valf[y[i]]]); ///pos[valor final]=indice final
swap(valf[x[i]],valf[y[i]]); // valf[indice final]=valorfinal
}
//armar
int p=0;
for(int i=0;i<r;i++){
swap(pos[val[x[i]]],pos[val[y[i]]]); //pos[valor]=indice actual
swap(val[x[i]],val[y[i]]); //val[indice actual]=valor
while(p<n && p==valf[p]){
p++;
}
if(p==n) break;
//cambio
//p(indice==valor) valf[p]-> el que llegara ahi
pair<int,int>c={pos[p],pos[valf[p]]}; //el que tiene que estar en p con el que esta al final
ans[i]=c;
swap(pos[p],pos[valf[p]]);
swap(val[c.first],val[c.second]);
//cambios al final
valf[posf[p]]=valf[p];
posf[valf[p]]=posf[p];
valf[p]=p;
}
while(p<n && val[p]==pos[val[p]]){
p++;
}
return p==n;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N;
s.resize(n);
x.resize(M);
y.resize(M);
for(int i=0;i<M;i++){
x[i]=X[i];
y[i]=Y[i];
}
for(int i=0;i<n;i++){
s[i]=S[i];
}
int l=0,r=M;
int cont=0;
while(l<r or cont<1000){
int mid=(r+l)/2;
if(ver(mid,s)){
r=mid;
}
else{
l=mid+1;
}
cont++;
}
if(ver(l,s)){
for(int i=0;i<l;i++){
P[i]=ans[i].first;
Q[i]=ans[i].second;
}
}
return l;
}
