#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int F[LIM];
int fnd(int x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
if(fnd(a)==fnd(b)) return false;
F[fnd(b)]=fnd(a);
return true;
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
int po=0, ko=m;
while(po<ko) {
int sr=(po+ko)/2;
vector<int>T(n);
rep(i, n) T[i]=S[i];
rep(i, sr) swap(T[X[i]], T[Y[i]]);
rep(i, n) F[i]=i;
int p=0;
rep(i, n) if(uni(i, T[i])) ++p;
if(p<=sr) ko=sr; else po=sr+1;
}
m=po;
vector<int>T(n);
rep(i, n) T[i]=S[i];
vector<int>C=T;
rep(i, m) swap(T[X[i]], T[Y[i]]);
int l=0;
rep(i, m) {
swap(C[X[i]], C[Y[i]]);
while(l<n && T[l]==l) ++l;
if(l==n) {
P[i]=Q[i]=0;
continue;
}
int a=-1, b=-1;
rep(j, n) if(C[j]==T[l]) a=j;
rep(j, n) if(C[j]==T[T[l]]) b=j;
P[i]=a;
Q[i]=b;
swap(C[a], C[b]);
swap(T[l], T[T[l]]);
}
return m;
}
