#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;
while(true){
vis[c]=true;
if(vis[cur[c]])break;
c=cur[c];
}
}
}
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]]);
}
vector<pair<int,int>> todo;
for(int i=0;i<N;i++){
if(!vis[i]){
int c=i;
vis[i]=true;
while(true){
vis[c]=true;
if(vis[cur[c]])break;
todo.push_back({c, cur[c]});
c=cur[c];
}
}
}
vector<int> pos(N);
for(int i=0;i<N;i++){
cur[i]=S[i];
pos[cur[i]]=i;
}
for(int i=0;i<(int)(todo.size());i++){
//~ printf("trying to swap values %d with %d\n", todo[i].first, todo[i].second);
pos[cur[X[i]]]=Y[i];
pos[cur[Y[i]]]=X[i];
swap(cur[X[i]], cur[Y[i]]);
//~ for(int j=0;j<N;j++){
//~ cout<<cur[j]<<" ";
//~ }
//~ cout<<endl;
P[i]=pos[todo[i].first];
Q[i]=pos[todo[i].second];
swap(cur[pos[todo[i].first]], cur[pos[todo[i].second]]);
swap(pos[todo[i].first], pos[todo[i].second]);
//~ for(int j=0;j<N;j++){
//~ cout<<cur[j]<<" ";
//~ }
//~ cout<<endl;
}
return r;
}
