#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
const int MN=2e5+100;
int n,a[MN],m,x[MN],y[MN],b[MN],rb[MN];
bool mark[MN];
bool check(int x1){
for(int i=0;i<n;i++){
b[i]=a[i];
mark[i]=0;
}
for(int i=0;i<x1;i++){
swap(b[x[i]],b[y[i]]);
}
int cmp=0;
for(int i=0;i<n;i++){
if(!mark[i]){
int x2=i;
do{
mark[x2]=1;
x2=b[x2];
}while(x2!=i);
cmp++;
}
}
return (n-cmp)<=x1;
}
int bs(){
int lo=-1,hi=m;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(check(mid)){
hi=mid;
}
else{
lo=mid;
}
}
return hi;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int p[], int q[]) {
n=N;
for(int i=0;i<n;i++){
a[i]=S[i];
}
m=M;
for(int i=0;i<m;i++){
x[i]=X[i],y[i]=Y[i];
}
int r=bs();
for(int i=0;i<n;i++){
b[i]=a[i];
}
for(int i=0;i<r;i++){
swap(b[x[i]],b[y[i]]);
}
int cnt=0;
for(int i=0;i<n;i++){
while(b[i]!=i){
p[cnt]=i;
q[cnt]=b[i];
swap(b[i],b[b[i]]);
cnt++;
}
}
while(cnt<r){
p[cnt]=0;
q[cnt]=0;
cnt++;
}
iota(b,b+n,0);
iota(rb,rb+n,0);
for(int i=r-1;i>=0;i--){
p[i]=rb[p[i]];
q[i]=rb[q[i]];
swap(rb[b[x[i]]],rb[b[y[i]]]);
swap(b[x[i]],b[y[i]]);
}
return r;
}
