#include "sorting.h"
int S2[200001], vis[200001];
int perm[200001], inv[200001];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
//int findSwapPairs(){
int ss = 0, ee = M, R = 0, now = 0;
while(ss <= ee){
int mid = (ss+ee) / 2;
for(int i=0;i<N;i++){
S2[i] = S[i];
vis[i] = 0;
}
for(int i=now;i<mid;i++){
int tmp = S2[X[i]]; S2[X[i]] = S2[Y[i]]; S2[Y[i]] = tmp;
}
int cnt = 0;
for(int i=0;i<N;i++){
if(vis[i]) continue;
int ii = S2[i];
while(ii != i){
vis[ii] = 1;
cnt++;
ii = S2[ii];
}
}
if(cnt <= mid){
R = mid;
ee = mid - 1;
}else{
now = mid;
for(int i=0;i<N;i++) S[i] = S2[i];
ss = mid + 1;
}
}
for(int i=now;i<R;i++){
int tmp = S[X[i]]; S[X[i]] = S[Y[i]]; S[Y[i]] = tmp;
}
for(int i=0;i<N;i++){
vis[i] = 0;
perm[i] = i;
inv[i] = i;
}
int cnt = 0;
for(int i=0;i<N;i++){
if(vis[i]) continue;
while(S[i] != i){
vis[S[i]] = 1;
P[cnt] = i; Q[cnt] = S[i];
int nxt = S[i];
S[i] = S[nxt];
S[nxt] = nxt;
cnt++;
}
}
for(int i=R-2;i>=0;i--){
int tmp;
int p1 = X[i+1], q1 = Y[i+1];
tmp = perm[p1]; perm[p1] = perm[q1]; perm[q1] = tmp;
int p2 = perm[p1], q2 = perm[q1];
tmp = inv[p2]; inv[p2] = inv[q2]; inv[q2] = tmp;
P[i] = inv[P[i]]; Q[i] = inv[Q[i]];
}
return R;
}
