//100 points
#include "sorting.h"
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int inf = 6e5+9;
int n,m,x[inf],y[inf],a[inf],pos[inf],from[inf],origin[inf],posfrom[inf];
bool check(int i,int p[],int q[]){
int l = 0,notvalid = 0;
for(int j=0;j<n;j++){
from[j] = j;
a[j] = origin[j];
p[j] = q[j] = 0;
pos[ a[j] ] = j;
posfrom[ from[j] ] = j;
notvalid += (a[j] != j);
}
//cout<<i<<" "<<notvalid<<endl;
for(int j=i;j>=0;j--){
swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
swap( from[ x[j] ] , from[ y[j] ] );
}
for(int j=0;j<=i;j++){
swap(pos[ a[ x[j] ] ] , pos[ a[ y[j] ] ]);
swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
notvalid -= (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
swap(a[ x[j] ] , a[ y[j] ] );
notvalid += (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
swap(from[ x[j] ] , from[ y[j] ]);
//cout<<notvalid<<" ";
int idx,idfrom;
while(l<n){
idx = pos[l];
idfrom = posfrom[l];
if(idx != idfrom)
break;
l++;
}
swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
notvalid -= (a[idx] != idx) + (a[idfrom] != idfrom);
swap(a[idx],a[idfrom]);
notvalid += (a[idx] != idx) + (a[idfrom] != idfrom);
//cout<<notvalid<<" ";
//cout<<l<<" "<<idx<<" "<<idfrom<<endl;
//cout<<"swap "<<idx<<" "<<idfrom<<endl;
p[j] = idx,q[j] = idfrom;
if(notvalid == 0)
return 1;
}
//for(int i=0;i<n;i++)
// cout<<a[i]<<" ";
return 0;
}
int findSwapPairs(int N, int A[], int M, int X[], int Y[], int p[], int q[]){
n = N;
m = M;
bool tr = 1;
for(int i=0;i<n;i++){
a[i] = A[i];
pos[ a[i] ] = i;
origin[i] = a[i];
if(a[i] != i)
tr = 0;
}
if(tr)
return 0;
for(int i=0;i<m;i++)
x[i] = X[i],y[i] = Y[i];
int l = 0 , r = m-1;
while(r-l>1){
if(check(mid,p,q))
r = mid;
else
l = mid;
}
if(check(0,p,q))
r = 0;
check(r,p,q);
return r+1;
}
