#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int target[200005];
int cur[200005];
int bck[200005];
vector<pair<int,int> > computeShortestSwaps(int N, int t[]){
vector<pair<int,int> > ret;
for(int i = 0; i < N; i++){
bck[i] = i;
cur[i] = i;
}
for(int i = 0; i < N; i++){
if(cur[i] != t[i]){
int idx1 = i;
int idx2 = bck[t[i]];
ret.emplace_back(idx1, idx2);
bck[cur[idx1]] = idx2;
bck[cur[idx2]] = idx1;
swap(cur[idx1], cur[idx2]);
}
}
return ret;
}
int aux[200005];
bool solve(int N, int mid, int S[], int X[], int Y[], int P[], int Q[]){
for(int i = 0; i < N; i++) cur[i] = i;
for(int i = 0; i < mid; i++){
swap(cur[X[i]], cur[Y[i]]);
}
for(int i = 0; i < N; i++) bck[cur[i]] = i;
for(int i = 0; i < N; i++) target[i] = cur[S[i]];
vector<pair<int,int> > cmds = computeShortestSwaps(N, target);
if(cmds.size() > mid) return false;
for(int i = 0; i < N; i++){
cur[i] = i;
bck[i] = i;
aux[i] = i;
target[i] = i;
}
for(int i = 0; i < mid; i++){
int idx1 = X[i];
int idx2 = Y[i];
bck[cur[idx1]] = idx2;
bck[cur[idx2]] = idx1;
swap(cur[idx1], cur[idx2]);
if(i < cmds.size()){
idx1 = target[cmds[i].first];
idx2 = target[cmds[i].second];
target[aux[idx1]] = idx2;
target[aux[idx2]] = idx1;
swap(aux[idx1], aux[idx2]);
idx1 = bck[idx1];
idx2 = bck[idx2];
P[i] = idx1;
Q[i] = idx2;
}else{
P[i] = 0;
Q[i] = 0;
}
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int lo = 0;
int hi = M;
int mid;
while(lo < hi){
mid = (lo + hi)/2;
if(solve(N, mid, S, X, Y, P, Q)){
hi = mid;
}else{
lo = mid+1;
}
}
solve(N, lo, S, X, Y, P, Q);
return lo;
}
