#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;
cnt_cycles ++;
}
}
for (int i = 0; i < n; ++ i)
{
if(used[i])continue;
cnt_cycles ++;
dfs(i);
}
return (n - cnt_cycles <= x);
}
int v[maxn], 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;
}
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)
{
v[i] = s[i];
val[i] = i;
}
for (int i = 0; i < n; ++ i)
{
if(a[i] == i)continue;
u.pb(make_pair(pos[i], i));
int val1 = a[i];
int val2 = a[pos[i]];
int index1 = i;
int index2 = pos[i];
a[index1] = val2;
pos[val2] = index1;
a[index2] = val1;
pos[val1] = index2;
}
reverse(u.begin(), u.end());
for (int i = 0; i < res; ++ i)
{
swap(val[sx[i]], val[sy[i]]);
// swap(v[sx[i]], v[sy[i]]);
if(u.size() == 0)break;
pair < int, int > curr = u.back();
u.pop_back();
P[i] = val[curr.first];
Q[i] = val[curr.second];
// swap(val[curr.first], val[curr.second]);
}
return res;
}
