#include<bits/stdc++.h>
#include "sorting.h"
#define MAXN 200007
using namespace std;
int n,m,q;
int pos[MAXN],s[MAXN];
int to[MAXN];
bool check(){
for(int i=0;i<n-1;i++){
if(s[i]>s[i+1])return false;
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N; m=M;
for(int i=0;i<n;i++)s[i]=i;
for(int i=0;i<n;i++){
swap(s[X[i]],s[Y[i]]);
}
for(int i=0;i<n;i++){
to[s[i]]=i;
}
for(int i=0;i<n;i++)s[i]=S[i];
for(int i=0;i<n;i++){
swap(s[X[i]],s[Y[i]]);
swap(to[X[i]],to[Y[i]]);
for(int f=0;f<n;f++){
if(to[f]!=s[f]){
for(int k=0;k<n;k++){
if(s[k]==to[f]){
P[i]=f; Q[i]=k;
swap(s[k],s[f]);
}
}
break;
}
}
}
q=n;
for(int i=0;i<n;i++)s[i]=S[i];
for(int i=0;i<n;i++){
if(check())return i;
swap(s[X[i]],s[Y[i]]);
swap(s[P[i]],s[Q[i]]);
}
return q;
}
