#include "sorting.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
int arr[200005];
int n;
int f(){
DSU dsu;
dsu.init(n);
for(int x=0;x<n;x++){
dsu.unite(x,arr[x]);
}
int cnt[n+5];
memset(cnt,0,sizeof(cnt));
int counter=0;
for(int x=0;x<n;x++){
int hold=dsu.get(x);
cnt[hold]++;
if(cnt[hold]==1) counter++;
}
return counter;
}
int findSwapPairs(int N, int s[], int m, int a[], int b[], int p[], int q[]){
n=N;
int pos[n];
for(int x=0;x<n;x++){
arr[x]=s[x];
pos[arr[x]]=x;
}
if(f()==n){
return 0;
}
int arr2[n];
for(int x=0;x<n;x++){
arr2[x]=arr[x];
}
int l=0;
int r=m-1;
int mid;
int best=r;
int take=0;
while(l<=r){
mid=(l+r)/2;
while(take<=mid){
swap(arr[a[take]],arr[b[take]]);
take++;
}
while(take-1>mid){
take--;
swap(arr[a[take]],arr[b[take]]);
}
if(n-f()<=mid+1){
best=mid;
r=mid-1;
}
else l=mid+1;
}
while(take<=best){
swap(arr[a[take]],arr[b[take]]);
take++;
}
while(take-1>best){
take--;
swap(arr[a[take]],arr[b[take]]);
}
//answer
bool visited[n+5];
memset(visited,0,sizeof(visited));
int ptr=0;
for(int y=0;y<n;y++){
if(visited[y]) continue;
int cur=y;
vector<int>v;
while(1){
v.push_back(cur);
visited[cur]=true;
cur=arr[cur];
if(cur==y) break;
}
for(int i=(int)v.size()-2;i>=0;i--){
int temp=v.back();
int temp2=v[i];
swap(pos[arr2[a[ptr]]],pos[arr2[b[ptr]]]);
swap(arr2[a[ptr]],arr2[b[ptr]]);
p[ptr]=pos[temp];
q[ptr]=pos[temp2];
swap(pos[arr2[p[ptr]]],pos[arr2[q[ptr]]]);
swap(arr2[p[ptr]],arr2[q[ptr]]);
ptr++;
}
}
while(ptr<best+1){
p[ptr]=q[ptr]=0;
ptr++;
}
return best+1;
}
