/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
typedef long long ll;
const int N_MAX = 200000;
const int M_MAX = 600000;
int findSwapPairs (int n, int p[], int m, int x[], int y[], int a[], int b[])
{
function <int ()> minSwaps = [&] ()
{
int aux[n];
int pos[n];
for(int i = 0; i < n; i++)
{
aux[i] = p[i];
pos[aux[i]] = i;
}
int swaps = 0;
for(int i = 0; i < n; i++)
{
if(aux[i] != i)
{
int u = i, v = pos[i];
swap(aux[u], aux[v]);
swap(pos[aux[u]], pos[aux[v]]);
swaps++;
}
}
return swaps;
};
function <bool (int)> check = [&] (int swaps)
{
for(int i = 0; i < swaps; i++)
swap(p[x[i]], p[y[i]]);
bool answer = (minSwaps() <= swaps);
for(int i = swaps - 1; i >= 0; i--)
swap(p[x[i]], p[y[i]]);
return answer;
};
int swaps;
{
int l = 0, r = m;
while(l < r)
{
int mid = (l + r) / 2;
if(check(mid) == true)
r = mid;
else
l = mid + 1;
}
swaps = l;
}
{
int aux[n];
for(int i = 0; i < n; i++)
aux[i] = p[i];
for(int i = 0; i < swaps; i++)
swap(aux[x[i]], aux[y[i]]);
int pos[n];
for(int i = 0; i < n; i++)
pos[aux[i]] = i;
int root[n];
for(int i = 0; i < n; i++)
root[p[i]] = i;
int curr = 0;
for(int i = 0; i < n; i++)
{
if(aux[i] != i)
{
swap(p[x[curr]], p[y[curr]]);
swap(root[p[x[curr]]], root[p[y[curr]]]);
int u = i, v = pos[i];
swap(aux[u], aux[v]);
swap(pos[aux[u]], pos[aux[v]]);
a[curr] = root[aux[u]];
b[curr] = root[aux[v]];
swap(p[a[curr]], p[b[curr]]);
swap(root[p[a[curr]]], root[p[b[curr]]]);
curr++;
}
}
while(curr < swaps)
{
a[curr] = 0;
b[curr] = 0;
curr++;
}
}
return swaps;
}
