#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
vector<pair<int,int>> swappy(int n, vector<int> arr) {
vector<int> rev(n);
for (int i = 0 ; i < n; i++ )rev[arr[i]]=i;
vector<pii> answer;
for (int i = 0 ; i<n; i++) {
if (rev[i]==i) continue;
int pos1 = rev[i];
int pos2 = i;
int ele1 = arr[pos1];
int ele2 = arr[pos2];
answer.emplace_back(ele1,ele2);
swap(arr[pos1],arr[pos2]);
swap(rev[ele1],rev[ele2]);
}
return answer;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> og(N);
for (int i = 0 ; i < N; i++ )og[i]=S[i];
int l = M-1;
int r = M-1;
vector<pii> swappies(M);
for (int i = 0 ; i< M; i++) swappies[i]={P[i],Q[i]};
while (l<r) {
int mid=(l+r)/2;
vector<int> testy = og;
for (int i = 0; i < mid; i++) {
swap(testy[X[i]],testy[Y[i]]);
}
auto important = swappy(N,testy);
if (important.size() <= mid) r = mid;
else l = mid+1;
}
vector<int> tog = og;
for (int i = 0; i < l; i++) {
swap(tog[X[i]],tog[Y[i]]);
}
auto very = swappy(N,tog);
vector<int> rev(N);
for (int i = 0 ; i < N; i++) rev[og[i]]=i;
int ind = -1;
for (auto ele: very) {
ind++;
int p1 = X[ind];
int p2 = Y[ind];
int e1 = og[p1];
int e2 = og[p2];
swap(og[p1], og[p2]);
swap(rev[e1],rev[e2]);
int pos1 = rev[ele.F];
int pos2 = rev[ele.S];
swap(og[pos1],og[pos2]);
swap(rev[ele.F],rev[ele.S]);
P[ind]=pos1;
Q[ind]=pos2;
}
for (int i = 0; i < l-very.size(); i++) {
ind++;
P[ind]=0;
Q[ind]=0;
}
return l;
}
