//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include "sorting.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m;
vector<int> s,arr;
vector<ii> sw;
vector<ii> changes;
bool vis[200005];
int can(int i){
changes.clear();
memset(vis,false,sizeof(vis));
arr=s;
rep(x,0,i){
swap(arr[sw[x].fi],arr[sw[x].se]);
}
//cout<<i<<": "; rep(x,0,n) cout<<arr[x]<<" "; cout<<endl;
rep(x,0,n) if (!vis[x]){
int curr=x;
vector<int> v;
do{
vis[curr]=true;
v.pub(curr);
curr=arr[curr];
} while (curr!=x);
rep(x,0,sz(v)-1) changes.pub(ii(v[x],v[x+1]));
}
//cout<<i<<" "<<sz(changes)<<endl;
return sz(changes);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N,m=M;
rep(x,0,n) s.pub(S[x]);
rep(x,0,m) sw.pub(ii(X[x],Y[x]));
int lo=-1,hi=m,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (can(mi)<=mi) hi=mi;
else lo=mi;
}
can(hi);
//cout<<hi<<endl;
//for (auto &it:changes) cout<<it.fi<<" "<<it.se<<endl;
vector<int> idx,pos;
rep(x,0,n) idx.pub(x),pos.pub(x);
rep(x,hi,0){
swap(pos[idx[sw[x].fi]],pos[idx[sw[x].se]]);
swap(idx[sw[x].fi],idx[sw[x].se]);
}
rep(x,0,hi){
swap(pos[idx[sw[x].fi]],pos[idx[sw[x].se]]);
swap(idx[sw[x].fi],idx[sw[x].se]);
if (!changes.empty()){
P[x]=pos[changes.back().fi];
Q[x]=pos[changes.back().se];
changes.pob();
}
else{
P[x]=0;
Q[x]=0;
}
}
return hi;
}
