#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n;
vector<int> ss,x,y;
vector<pii> ans;
bool check(int m){
ans.assign(m,{0,0});
vector<int> plates_sitting_in_pos(n),inverse_of_s(n),s(n),pos_of_plate(n);
for(int i=0;i<n;i++){
s[i]=ss[i];
inverse_of_s[s[i]]=i;
plates_sitting_in_pos[i]=i;
}
for(int i=0;i<m;i++){
swap(plates_sitting_in_pos[x[i]],plates_sitting_in_pos[y[i]]);
}
for(int i=0;i<n;i++){
pos_of_plate[plates_sitting_in_pos[i]]=i;
}
int p=0;
for(int i=0;i<m;i++){
swap(s[x[i]],s[y[i]]);
swap(pos_of_plate[x[i]],pos_of_plate[y[i]]);
inverse_of_s[s[x[i]]]=x[i];
inverse_of_s[s[y[i]]]=y[i];
plates_sitting_in_pos[pos_of_plate[x[i]]]=x[i];
plates_sitting_in_pos[pos_of_plate[y[i]]]=y[i];
while(p<n&&inverse_of_s[p]==plates_sitting_in_pos[p]){
p++;
}
if(p==n){
break;
}
pii temp={inverse_of_s[p],plates_sitting_in_pos[p]};
swap(s[temp.first],s[temp.second]);
inverse_of_s[s[temp.first]]=temp.first;
inverse_of_s[s[temp.second]]=temp.second;
ans[i]=temp;
}
while(p<n&&inverse_of_s[p]==plates_sitting_in_pos[p]){
p++;
}
return p==n;
}
int findSwapPairs(int N,int S[],int m,int X[],int Y[],int p[],int q[]){
n=N;
ss.assign(n,0);
x.assign(m,0);
y.assign(m,0);
for(int i=0;i<n;i++){
ss[i]=S[i];
}
for(int i=0;i<m;i++){
x[i]=X[i];
y[i]=Y[i];
}
int l=0,r=m;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid;
}else{
l=mid+1;
}
}
check(l);
for(int i=0;i<l;i++){
p[i]=ans[i].first;
q[i]=ans[i].second;
}
return l;
}
