#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 600050
#define mod 1000000007
#define ll long long
#define f first
#define s second
#define ii pair<ll,ll>
#define db(x) cerr << #x << ": " << (x) << '\n';
int a[maxn], b[maxn], n, m, id[maxn];
ii bc[maxn], gc[maxn];
bool can(int limit){
for(int i=0; i<n; i++)
b[i] = a[i];
for(int i=0; i<limit; i++)
swap(b[bc[i].f],b[bc[i].s]);
for(int i=0; i<n; i++){
id[b[i]] = i;
}
int cnt = 0;
for(int i=0; i<n; i++){
if( b[i] != i ){
cnt++;
int x = id[i];
int y = i;
swap( b[x] , b[y] );
id[ b[x] ] = x;
id[ b[y] ] = y;
}
}
return ( cnt <= limit );
}
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++){
bc[i] = { X[i] , Y[i] };
}
int l = 1, r = M - 1;
while( l < r ){
int mi = ( l + r ) >> 1;
if( can(mi) ) r = mi;
else l = mi + 1;
}
if( can(l-1) ) l --;
if( ! can(l) ) l ++;
for(int i=0; i<n; i++)
b[i] = a[i];
for(int i=0; i<l; i++)
swap(b[bc[i].f],b[bc[i].s]);
for(int i=0; i<n; i++){
id[b[i]] = i;
}
int cnt = 0;
for(int i=0; i<n; i++){
if( b[i] != i ){
int x = id[i];
int y = i;
P[cnt] = x;
Q[cnt] = y;
swap( b[x] , b[y] );
id[ b[x] ] = x;
id[ b[y] ] = y;
cnt++;
}
}
return l;
}
