#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
bool can(int K, int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
assert(K <= M);
int s[N], si[N]; for(int i = 0; i < N; i++) s[i] = S[i];
for(int i = 0; i < K; i++) swap(s[X[i]], s[Y[i]]);
vector<pair<int, int>> V;
bool u[N] = {};
for(int i = 0; i < N; i++){
if(!u[i] && s[i] != i){
vector<int> v {i}; int x = s[i];
while(x != i) v.push_back(x), x = s[x];
for(auto i : v) u[i] = true;
for(int j = 1; j < (int) v.size(); j++) V.push_back({v[j - 1], v[j]});
}
}
if((int) V.size() > K) return false;
for(int i = 0; i < N; i++) s[i] = S[i], si[s[i]] = i;
for(int i = 0; i < K; i++){
swap(s[X[i]], s[Y[i]]); swap(si[s[X[i]]], si[s[Y[i]]]);
if(i < (int) V.size()){
int a = V[i].first, b = V[i].second;
P[i] = si[a], Q[i] = si[b]; swap(s[si[a]], s[si[b]]); swap(si[s[si[a]]], si[s[si[b]]]);
}else{
P[i] = Q[i] = 0;
}
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int L = 0, R = M;
while(L != R){
int mid = (L + R) / 2;
if(can(mid, N, S, M, X, Y, P, Q)){
R = mid;
}else{
L = mid + 1;
}
}
can(L, N, S, M, X, Y, P, Q);
return L;
}
