#include <bits/stdc++.h>
//#include "sorting.h"
using namespace std;
int vrni(vector<int>v,vector<pair<int,int>>&g,int m)
{
int n=v.size(),sum=0;
for(int i=0;i<m;i++)
{
swap(v[g[i].first],v[g[i].second]);
}
vector<bool>vis(n);
for(int i=0;i<n;i++)
{
if(vis[i])continue;
sum++;
int a=i;
vis[i]=true;
while(v[a]!=i)
{
vis[v[a]]=true;
a=v[a];
}
}
return n-sum;
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[])
{
int l=0,r=n;
vector<pair<int,int>>g,res1;
vector<int>v,v2(n);
for(int i=0;i<n;i++)
{
v2[S[i]]=i;
v.push_back(S[i]);
g.push_back({X[i],Y[i]});
}
while(l<r)
{
int m=(l+r)/2,a=vrni(v,g,m);
if(a<=m)r=m;
else l=m+1;
}
vector<int>v1=v;
for(int i=0;i<l;i++)
{
swap(v1[g[i].first],v1[g[i].second]);
}
vector<bool>vis(n);
for(int i=0;i<n;i++)
{
if(vis[i])continue;
int a=i;
vis[i]=true;
while(v1[a]!=i)
{
vis[v1[a]]=true;
res1.push_back({a,v1[a]});
a=v1[a];
}
}
for(int i=0;i<l;i++)
{
int a=g[i].first,b=g[i].second;
swap(v2[v[a]],v2[v[b]]);
swap(v[a],v[b]);
P[i]=v2[res1[i].first];
Q[i]=v2[res1[i].second];
a=P[i];b=Q[i];
swap(v2[v[a]],v2[v[b]]);
swap(v[a],v[b]);
}
return l;
}
