#include "sorting.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 2e5 + 5;
int sz, cnt, res, u[N], a[N], pos[N], asd[N];
void dfs (int v) {
cnt++;
u[v] = 1;
if (u[ a[v] ] == 0)
dfs(a[v]);
}
int findSwapPairs(int n, int b[], int m, int x[], int y[], int p[], int q[]) {
bool fl = 1;
for (int i = 0; i < n; i++) {
a[i] = b[i];
if (a[i] != i)
fl = 0;
}
if (fl)
return 0;
int l = 0, r = m;
while (r - l > 1) {
int md = (l + r) >> 1;
for (int i = 0; i < n; i++)
a[i] = b[i];
for (int i = 0; i < md; i++) {
swap( a[ x[i] ], a[ y[i] ] );
}
res = 0;
memset(u, 0, sizeof(u));
for (int j = 0; j < n; j++) {
if (u[j]) continue;
cnt = 0; dfs(j);
res += cnt - 1;
}
if (res <= md)
r = md;
else
l = md;
}
for (int i = 0; i < n; i++)
a[i] = b[i];
for (int i = 0; i < r; i++) {
swap( a[ x[i] ], a[ y[i] ] );
}
for (int j = 0; j < n; j++)
pos[b[j]] = j, asd[a[j]] = j;
int k = 0;
for (int j = 0; j < n; j++) {
if (a[j] == j) continue;
pos[ b[x[k]] ] = y[k];
pos[ b[y[k]] ] = x[k];
swap( b[x[k]], b[y[k]] );
p[k] = pos[a[j]], q[k] = pos[j];
swap( b[pos[ a[j] ]], b[pos[j]] );
swap( pos[ a[j] ], pos[j] );
swap(a[j], a[asd[j]]);
asd[a[asd[j]]] = asd[j];
k++;
}
return r;
}
