#include <bits/stdc++.h>
using namespace std;
const int MAXN=200000;
int where[MAXN], to[MAXN], inverse[MAXN];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
for(int i=0;i<N;i++){
where[S[i]]=i; //el item S[i] está en la posición i (permutacion actual)
}
int S_[N];
for(int i=0;i<N;i++)S_[i]=S[i];
for(int i=0;i<M;i++){
swap(S_[X[i]], S_[Y[i]]);
}
for(int i=0;i<N;i++){
to[i]=where[S_[i]]; //el item S[i] va a terminar en la posicion i
inverse[where[S_[i]]]=i;
}
for(int i=0;i<M;i++)P[i]=Q[i]=0;
int cur=0, j=0;
auto merge=[&](int a, int b){
swap(S[where[a]], S[where[b]]);
swap(to[inverse[where[a]]], to[inverse[where[b]]]);
swap(inverse[where[a]], inverse[where[b]]);
swap(where[a], where[b]);
};
for(int i=0;i<M;i++){ //a medida que avanzamos tenemos que updatear los arrays
int a=S[X[i]], b=S[Y[i]];
merge(a,b);
if(cur<N){
if(cur!=to[cur]){
P[j]=where[cur];
Q[j]=where[to[cur]];
merge(cur, to[cur]);
j++;
}
}
cur++;
}
/* for(int i=0;i<N;i++){
cout<<S[i]<<" ";
}
cout<<endl; */
return M;
}
