#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
bool trySwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
vector<int> targetArr(n);
vector<int> revInd(n);
int countMatches = 0;
for(int i = 0; i < n; i++) {
targetArr[i] = i;
if(S[i] == i) countMatches++;
}
for(int i = m-1; i >= 0; i--) {
swap(targetArr[X[i]], targetArr[Y[i]]);
}
for(int i = 0; i < n; i++) {
revInd[targetArr[i]] = i;
}
set<int> notGood; // Indices of places where no match
for(int i = 0; i < n; i++) {
if(S[i] != targetArr[i]) notGood.insert(i);
}
auto swapTwo = [&](int i, int a, int b) {
if(a == S[a]) countMatches--;
if(b == S[b]) countMatches--;
swap(S[a], S[b]);
P[i] = a; Q[i] = b;
if(a == S[a]) countMatches++;
if(b == S[b]) countMatches++;
};
for(int i = 0; i < m; i++) {
if(countMatches == n) {
m = i;
break;
}
if(X[i] != Y[i]) {
int x = (int)notGood.count(X[i]);
int y = (int)notGood.count(Y[i]);
if(X[i] == S[X[i]]) countMatches--;
if(Y[i] == S[Y[i]]) countMatches--;
swap(revInd[targetArr[X[i]]], revInd[targetArr[Y[i]]]);
swap(targetArr[X[i]], targetArr[Y[i]]);
swap(S[X[i]], S[Y[i]]);
notGood.erase(X[i]);
notGood.erase(Y[i]);
if(x) notGood.insert(Y[i]);
if(y) notGood.insert(X[i]);
if(X[i] == S[X[i]]) countMatches++;
if(Y[i] == S[Y[i]]) countMatches++;
}
if(notGood.size() == 0) {
swapTwo(i, 0, 0);
continue;
}
int a = *(notGood.begin());
int b = revInd[S[a]];
swapTwo(i, a, b);
assert(S[b] == targetArr[b]);
if(S[a] == targetArr[a]) notGood.erase(a);
if(S[b] == targetArr[b]) notGood.erase(b);
}
return (countMatches == n);
}
int findSwapPairs(int n, int R[], int m, int X[], int Y[], int P[], int Q[]) {
int V[200001];
int l = -1, r = m;
while(l != r - 1) {
for(int i = 0; i < n; i++) {
V[i] = R[i];
}
int mid = (l + r + 1) / 2;
if(trySwapPairs(n, V, mid, X, Y, P, Q)) r = mid;
else l = mid;
}
trySwapPairs(n, R, r, X, Y, P, Q);
return r;
}
