#include<bits/stdc++.h>
#define pb push_back
#include "sorting.h"
using namespace std;
const int maxn = 1e5 + 10;
int n, m;
int s[maxn];
int a[maxn];
int sx[maxn], sy[maxn];
vector < int > g[maxn];
int used[maxn];
void dfs(int beg)
{
used[beg] = 1;
for (auto nb: g[beg])
if(!used[nb])dfs(nb);
}
bool check(int x)
{
for (int i = 0; i < n; ++ i)
{
a[i] = s[i];
g[i].clear();
used[i] = 0;
}
for (int i = 0; i < x; ++ i)
swap(a[sx[i]],a[sy[i]]);
int cnt_cycles = 0;
for (int i = 0; i < n; ++ i)
{
if(a[i] != i)g[a[i]].pb(i);
else used[i] = 1;
}
for (int i = 0; i < n; ++ i)
{
if(used[i])continue;
cnt_cycles ++;
dfs(i);
}
return (n - cnt_cycles <= x);
}
int val[maxn], pos[maxn];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n = N;
m = M;
int is = 1;
for (int i = 0; i < n; ++ i)
{
s[i] = S[i];
if(i != s[i])is = 0;
}
if(is)return 0;
for (int i = 0; i < m; ++ i)
{
sx[i] = X[i];
sy[i] = Y[i];
}
int l = 1, r = m, mid, res = m;
while(l <= r)
{
mid = (l + r)/2;
if(check(mid))
{
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
for (int i = 0; i < n; ++ i)
val[i] = i;
check(res);
// cout << res << endl;
for (int i = 0; i < n; ++ i)
{
// cout << a[i] << " ";
pos[a[i]] = i;
}
// cout << endl;
vector < pair < int, int > > u;
for (int i = 0; i < n; ++ i)
{
if(a[i] == i)continue;
u.pb(make_pair(i, pos[i]));
// cout << "swap " << i << " " << pos[i] << endl;
int curr = a[i];
swap(a[i], a[pos[i]]);
swap(pos[curr], pos[i]);
}
for (int i = res-1; i >= 0; -- i)
{
pair < int, int > curr = u.back();
u.pop_back();
P[i] = val[curr.first];
Q[i] = val[curr.second];
swap(val[sx[i]], val[sy[i]]);
}
return res;
}
