#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
vector<ll> ln;
vector<pair<ll,ll>> em;
bool possi(ll m){
vector<ll> a=ln;
ll limit=m;
for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
int N=n;
vector<pair<ll,int>> temp;
for(int i=0;i<N;i++) temp.push_back({a[i],i});
sort(temp.begin(),temp.end());
vector<int> p(N);
for(int i=0;i<N;i++) p[temp[i].second]=i;
vector<bool> vis(N,false);
ll cycles=0;
for(int i=0;i<N;i++) if(!vis[i]){
int j=i;
while(!vis[j]){
vis[j]=true;
j=p[j];
}
cycles++;
}
ll min_swaps=N-cycles;
return min_swaps<=m;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
ln.resize(N);
n=N;
em.resize(M);
for(int i=0;i<N;i++){
ln[i]=S[i];
}
for(int i=0;i<M;i++){
em[i].first=X[i];
em[i].second=Y[i];
}
ll l=0,r=M,ans=M;
while(l<=r){
ll m=l+((r-l)/2);
if(possi(m)){
ans=m;
r=m-1;
}else{
l=m+1;
}
}
vector<ll> a=ln;
ll limit=ans;
for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
vector<pair<ll,int>> temp;
for(int i=0;i<N;i++) temp.push_back({a[i],i});
sort(temp.begin(),temp.end());
vector<int> p(N);
for(int i=0;i<N;i++) p[temp[i].second]=i;
vector<bool> vis(N,false);
ll R=0;
for(int i=0;i<N;i++){
if(!vis[i] && p[i]!=i){
int cur=i;
vector<int> ciclo;
while(!vis[cur]){
ciclo.push_back(cur);
vis[cur]=true;
cur=p[cur];
}
for(int j=1;j<ciclo.size();j++){
P[R]=ciclo[0];
Q[R]=ciclo[j];
R++;
}
}
}
return ans;
}
