#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+3;
int ori[MAXN], quero[MAXN], queroi[MAXN];
int v[MAXN], vi[MAXN];
int x[MAXN], y[MAXN];
int r1[MAXN], r2[MAXN];
unordered_set<int> s;
int n, m;
bool testa(int k) {
if(k<=0) return 0;
for(int i=0; i<n; i++) {
quero[i]=i; queroi[i]=i;
v[i]=ori[i]; vi[v[i]]=i;
}
for(int i=k-1; i>=0; i--) {
int a=x[i]; int b=y[i];
swap(quero[a], quero[b]);
queroi[quero[a]]=a; queroi[quero[b]]=b;
}
s.clear();
for(int i=0; i<n; i++) if(v[i]!=quero[i]) s.insert(v[i]);
// for(int i=0; i<n; i++) printf("%d ", quero[i]);
for(int i=1; i<=k; i++) {
int a=x[i]; int b=y[i];
if(v[a]==quero[a]&&v[b]==quero[b]) {
if(s.empty()) r1[i]=r2[i]=0;
else {
int cara=(*s.begin());
r1[i]=vi[cara]; r2[i]=queroi[cara];
}
} else if(v[a]==quero[a]) {
int cara=quero[b];
r1[i]=vi[cara]; r2[i]=b;
} else {
int cara=quero[a];
r1[i]=vi[cara]; r2[i]=a;
}
swap(v[r1[i]], v[r2[i]]);
vi[v[r1[i]]]=r1[i]; vi[v[r2[i]]]=r2[i];
if(v[r1[i]]==quero[r1[i]]) s.erase(v[r1[i]]);
if(v[r2[i]]==quero[r2[i]]) s.erase(v[r2[i]]);
// printf("%d %d\n", r1[i], r2[i]);
// for(auto cur : s) printf("%d ", cur); printf("\n");
swap(quero[a], quero[b]);
queroi[quero[a]]=a; queroi[quero[b]]=b;
if(i==k) break;
swap(v[a], v[b]);
vi[v[a]]=a; vi[v[b]]=b;
}
int ok=1;
for(int i=0; i<n; i++) if(v[i]!=i) ok=0;
return ok;
}
int findSwapPairs(int N, int V[], int M, int X[], int Y[], int R1[], int R2[]) {
n=N; m=M;
for(int i=0; i<n; i++) ori[i]=V[i];
for(int i=0; i<m; i++) x[i]=X[i];
for(int i=0; i<m; i++) y[i]=Y[i];
int ok=1;
for(int i=0; i<n; i++) if(ori[i]!=i) ok=0;
if(ok) return 0;
swap(ori[x[0]], ori[y[0]]);
x[0]=0; y[0]=0;
x[m]=0; y[m]=0;
int respf=0;
for(int i=m; i>0; i/=2) while(respf+i<=m&&testa(respf+i)==0) respf+=i;
while(respf<=m&&!testa(respf)) respf++;
if(!testa(respf)) assert(testa(m));
for(int i=1; i<=respf; i++) R1[i-1]=r1[i], R2[i-1]=r2[i];
return respf;
}
