#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
pii arr[mxn];
int perm[mxn],pos[mxn];
int N,M;
int done = 0;
void del(int k){
done -= (perm[k] == k);
return;
}
void add(int k){
done += (perm[k] == k);
}
bool check(){
for(int i = 0;i<N;i++){
if(perm[i] != i)return false;
}
return true;
}
void act(int a,int b){
if(a == b)return;
del(a);del(b);
swap(perm[a],perm[b]);
pos[perm[a]] = a;
pos[perm[b]] = b;
add(a);add(b);
return;
}
int findSwapPairs(int NN, int S[], int MM, int X[], int Y[], int P[], int Q[]) {
N = NN;M = MM;
for(int i = 0;i<N;i++){
perm[i] = S[i];
pos[perm[i]] = i;
add(i);
}
for(int i = 0;i<M;i++)arr[i] = pii(X[i],Y[i]);
if(check())return P[0] = Q[0] = 0;
for(int i = 0;i+2<N;i++){
act(arr[i].fs,arr[i].sc);
P[i] = pos[i+2],Q[i] = i+2;
if(check())return i+1;
act(P[i],Q[i]);
assert(perm[i+2] == i+2);
if(check())return i+1;
}
act(arr[N-2].fs,arr[N-2].sc);
P[N-2] = Q[N-2] = 0;
if(check())return N-1;
else{
P[N-2] = 0;
Q[N-2] = 1;
act(P[N-2],Q[N-2]);
assert(check());
return N-1;
}
assert(false);
}
