#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 = 0, r = M, bes = M;
while(l <= r){
vector<int> seq(N);
for(int i = 0; i < N; ++i)seq[i] = S[i];
int m = (l+r)>>1;
for(int i = 0; i < m; ++i)swap(seq[X[i]],seq[Y[i]]);
int cn = 0;
for(int i = 0; i < N; ++i){
while(seq[i] != i){
cn++;
swap(seq[i],seq[seq[i]]);
}
}
if(cn > m)l = m+1;
else bes = m, r = m-1;
}
map<int,int> Ma;
for(int i = 0; i < N; ++i)Ma[S[i]] = i;
vector<int> seq(N);
for(int i = 0; i < N; ++i)seq[i] = S[i];
for(int i = 0; i < bes; ++i)swap(seq[X[i]],seq[Y[i]]);
int cn = 0;
for(int i = 0; i < N; ++i){
while(seq[i] != i){
P[cn] = seq[i];
Q[cn] = seq[seq[i]];
cn++;
swap(seq[i],seq[seq[i]]);
}
}
for(int i = 0; i < bes; ++i){
swap(S[X[i]],S[Y[i]]);
swap(Ma[S[X[i]]],Ma[S[Y[i]]]);
P[i] = Ma[P[i]];
Q[i] = Ma[Q[i]];
swap(S[P[i]],S[Q[i]]);
swap(Ma[S[P[i]]],Ma[S[Q[i]]]);
}
return bes;
}
