#include <bits/stdc++.h>
using namespace std;
int vis[200001];
vector<int> vs;
vector<int> now;
void dfs(int i){
vis[i] = 1;
vs.push_back(i);
if(!vis[now[i]])dfs(now[i]);
}
int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){
long long l = 0 , r = M , nah = 0;
while(l<=r){
long long mid = (l+r)/2;
now.clear();
for(int i = 0;i<N;i++)now.push_back(S[i]);
for(int i = 0;i<mid;i++){
swap(now[X[i]],now[Y[i]]);
}
memset(vis,0,sizeof vis);
int ans = N;
for(int i = 0;i<N;i++){
if(!vis[i]){
vs.clear();
dfs(i);
ans--;
}
}
if(ans<=mid){
r = mid-1;
nah = mid;
}else l = mid+1;
}
now.clear();
for(int i = 0;i<N;i++)now.push_back(S[i]);
for(int i = 0;i<nah;i++){
swap(now[X[i]],now[Y[i]]);
}
memset(vis,0,sizeof vis);
vector<pair<int,int>> swps;
for(int i = 0;i<N;i++){
if(!vis[i]){
vs.clear();
dfs(i);
for(int xd = 1;xd<vs.size();xd++){
swps.push_back({vs[0],vs[xd]});
}
}
}
reverse(swps.begin(),swps.end());
int pos[N] = {0};
now.clear();
for(int i = 0;i<N;i++){
now.push_back(S[i]);pos[S[i]] = i;
}
for(int i = 0;i<nah;i++){
swap(S[X[i]],S[Y[i]]);
swap(pos[S[X[i]]],pos[S[Y[i]]]);
if(swps.empty()){
P[i] = 0;
Q[i] = 0;
}else{
P[i] = pos[swps.back().first];
Q[i] = pos[swps.back().second];
swps.pop_back();
}
//cout<<X[i]<<" "<<Y[i]<<" "<<P[i]<<" "<<Q[i]<<endl;
}
return nah;
}/*
int main(){
int S[] ={3,0,4,2,1};
int X[] = {1,4,2,1,0};
int Y[] ={1,0,3,4,4};
int P[] ={0,0,0,0,0};
int Q[] = {0,0,0,0,0};
findSwapPairs(5,S,5,X,Y,P,Q);
}
*/
