#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int l=-1,r=M;
for(int i=0;i<M;i++)P[i]=Q[i]=0;
while(l<r-1){
int mid=(l+r)/2;
vector<bool> vis(N, 0);
vector<int> cur(N);
for(int i=0;i<N;i++)cur[i]=S[i];
for(int i=0;i<mid;i++){
swap(cur[X[i]], cur[Y[i]]);
}
int cycles=0;
for(int i=0;i<N;i++){
if(!vis[i]){
cycles++;
int c=i;
vis[i]=true;
while(cur[c]!=i){
c=cur[c];
vis[c]=true;
}
}
}
if(N-cycles <= mid){
r=mid;
}
else l=mid;
}
vector<bool> vis(N, 0);
vector<int> cur(N);
for(int i=0;i<N;i++)cur[i]=S[i];
for(int i=0;i<r;i++){
swap(cur[X[i]], cur[Y[i]]);
}
int cnt=0;
for(int i=0;i<N;i++){
if(!vis[i]){
int c=i;
vis[i]=true;
while(cur[c]!=i){
vis[c]=true;
P[cnt]=c;
Q[cnt]=cur[c];
cnt++;
c=cur[c];
}
}
}
return r;
}
