#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define pb push_back
const int lim=2e5+100;
int n,m,*s,*x,*y,*p,*q;
struct rollbackdsu{
int par[lim],sz[lim];
int compcnt,opcnt;
struct opr{
int id,i,j;
};
stack<opr>ops;
void init(){
for(int i=0;i<n;i++){
par[i]=i;
sz[i]=1;
}
compcnt=n,opcnt=0;
}
int find(int i){
while(i!=par[i]){
i=par[i];
}
return i;
}
void unite(int i,int j){
i=find(i),j=find(j);
if(i^j){
if(sz[i]<sz[j])swap(i,j);
ops.push({opcnt,i,j});
par[j]=i;
sz[i]+=sz[j];
compcnt--;
}
opcnt++;
}
void rollback(){
opcnt--;
if(ops.size()&&ops.top().id==opcnt){
auto[id,i,j]=ops.top();
sz[i]-=sz[j];
par[j]=j;
ops.pop();
compcnt++;
}
}
};
struct{
rollbackdsu dsu;
vector<pii>tree[5*lim];
map<pii,int>edgetrack;
int tm=0;
void init(){
dsu.init();
}
int L,R;
pii VAL;
void update(int l,int r,int node){
if(L<=l&&r<=R){
tree[node].pb(VAL);
return;
}
if(r<L||R<l)return;
int mid=(l+r)>>1,child=node<<1;
update(l,mid,child),update(mid+1,r,child|1);
}
void update(int l,int r,pii val){
L=l,R=r,VAL=val;
update(0,m,1);
}
void addedge(pii val){
edgetrack[val]=tm;
}
void removeedge(pii val){
int past=edgetrack[val];
edgetrack.erase(val);
update(past,tm-1,val);
}
void passtime(){tm++;}
void roll(int node){
for(auto[x,y]:tree[node]){
dsu.rollback();
}
}
int walk(int l,int r,int node){
for(auto[x,y]:tree[node]){
dsu.unite(x,y);
}
if(l==r){
if(n-dsu.compcnt<=l){
roll(node);
return l;
}
roll(node);
return -1;
}
int mid=(l+r)>>1,child=node<<1;
int leftval=walk(l,mid,child),rightval=walk(mid+1,r,child|1);
roll(node);
if(leftval!=-1)return leftval;
return rightval;
}
int walk(){
assert(tm==m+1);
for(auto[x,y]:edgetrack){
update(y,tm,x);
}
return walk(0,m,1);
}
}dsu;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N,m=M,s=S,x=X,y=Y,p=P,q=Q;
dsu.init();
for(int i=0;i<n;i++){
dsu.addedge({i,s[i]});
}
dsu.passtime();
int a[n];
for(int i=0;i<n;i++){
a[i]=s[i];
}
for(int i=0;i<m;i++){
dsu.removeedge({x[i],a[x[i]]});
dsu.removeedge({y[i],a[y[i]]});
swap(a[x[i]],a[y[i]]);
dsu.addedge({x[i],a[x[i]]});
dsu.addedge({y[i],a[y[i]]});
dsu.passtime();
}
int res=dsu.walk();
for(int i=0;i<n;i++){
a[i]=s[i];
}
for(int i=0;i<res;i++){
swap(a[x[i]],a[y[i]]);
}
int pos[n];
for(int i=0;i<n;i++){
pos[s[i]]=i;
}
int j=0;
for(int i=0;i<res;i++){
swap(s[x[i]],s[y[i]]);
pos[s[x[i]]]=x[i];
pos[s[y[i]]]=y[i];
while(j<n&&a[j]==j)j++;
if(j==n)p[j]=q[j]=0;
else{
p[i]=pos[a[j]];
q[i]=pos[a[a[j]]];
swap(s[p[i]],s[q[i]]);
pos[s[p[i]]]=p[i];
pos[s[q[i]]]=q[i];
swap(a[j],a[a[j]]);
}
}
return res;
}
