#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%d",&x);return x;}
void print(int x){printf("%d\n",x);}
void file(string s)
{
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
const int mod=998244353;
int tp[600005],tq[600005];
int sr[600005];
int fa[600005];
bool vis[600005];
int to[600005],iv[600005];
bool check(int ps,int n,int m,int s[],int x[],int y[])
{
int tot=0;
rep(i,n){sr[i]=s[i];}
rep(i,ps)
{
swap(sr[x[i]],sr[y[i]]);
}
rep(i,n)
{
fa[sr[i]]=i;vis[i]=0;
}
rep(i,n)
{
if(!vis[i])
{
int now=i;
while(!vis[now])
{
vis[now]=1;
if(vis[fa[now]]){break;}
tp[tot]=now,tq[tot]=fa[now];tot++;
now=fa[now];
}
}
}
if(tot>=ps+1){return 0;}
for(int i=tot;i<m;i++){tp[i]=tq[i]=0;}
return 1;
}
int findSwapPairs(int n,int s[],int m,int x[],int y[],int p[],int q[])
{
if(is_sorted(s,s+n)){return 0;}
int l=1,r=m;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid,n,m,s,x,y)){r=mid-1;}
else{l=mid+1;}
}
check(l,n,m,s,x,y);
rep(i,n){to[i]=iv[i]=i;}
for(int i=l-1;i>=0;i--)
{
p[i]=to[tp[i]];q[i]=to[tq[i]];
swap(iv[x[i]],iv[y[i]]);
swap(to[iv[x[i]]],to[iv[y[i]]]);
}
return l;
}
