#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;
}
void OP(int id){
auto [a,b] = arr[id];
act(a,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]);
for(int i = 0;i+1<N;i++){
P[i] = pos[i],Q[i] = i;
if(check())return i+1;
act(i,pos[i]);
assert(perm[i] == i);
if(check())return i+1;
}
assert(false);
return -1;
/*
for(int i = 0;i+2<N;i++){
OP(i);
if(check())return i;
P[i] = pos[i+2],Q[i] = i+2;
act(i+2,pos[i+2]);
assert(perm[i+2] == i+2);
if(check())return i;
}
OP(N-2);
P[N-2] = Q[N-2] = 0;
if(check())return N-1;
else{
P[N-2] = 0;
Q[N-2] = 1;
return N-1;
}
*/
return -1;
}
