#include "sorting.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, lb, ub, mid, cs;
ll a[200005], cv, b[200005];
bool vis[200005];
vector<pll> res;
vector<ll> tmb;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N, m = M;
lb = 0, ub = m;
while (lb < ub) {
mid = (lb + ub)>>1;
iloop(0, n) a[i] = S[i], vis[i] = 0;
iloop(0, mid) swap(a[X[i]], a[Y[i]]);
cs = 0;
iloop(0, n) if (!vis[i]) {
vis[i] = 1;
cv = i;
while (!vis[a[cv]]) {
cv = a[cv];
vis[cv] = 1;
cs++;
}
}
if (cv <= mid) ub = mid;
else lb = mid + 1;
}
iloop(0, n) a[i] = S[i], vis[i] = 0;
iloop(0, lb) swap(a[X[i]], a[Y[i]]);
iloop(0, n) if (!vis[i]) {
vis[i] = 1;
cv = i;
while (!vis[a[cv]]) {
tmb.push_back(cv);
cv = a[cv];
vis[cv] = 1;
}
while (tmb.size()) {res.push_back({cv, tmb.back()}); tmb.pop_back();}
}
while ((ll)res.size() < lb) res.push_back({0, 0});
iloop(0, n) a[i] = S[i], b[S[i]] = i;
iloop(0, lb) {
swap(b[a[X[i]]], b[a[Y[i]]]);
swap(a[X[i]], a[Y[i]]);
P[i] = b[res[i].first];
Q[i] = b[res[i].second];
swap(b[a[P[i]]], b[a[Q[i]]]);
swap(a[P[i]], a[Q[i]]);
}
return lb;
}
