#include <bits/stdc++.h>
// #include "sorting.h"
#define vc vector
using namespace std;
int findSwapPairs(int n, int s[], int m, int x[], int y[], int a[], int b[])
{
int is[n];
for (int i = 0; i < n; ++i)
is[s[i]] = i;
function<bool(int)> solve = [&](int meja)
{
int p[n], ip[n], z[n], iz[n];
for (int i = 0; i < n; ++i)
p[i] = i, z[i] = iz[i] = i;
for (int i = meja - 1; i >= 0; --i)
swap(p[x[i]], p[y[i]]);
for (int i = 0; i < n; ++i)
ip[p[i]] = i;
int j = 0;
for (int i = meja - 1; i >= 0; --i)
{
/*for (int t = 0; t < n; ++t)
cout << z[t] << " ";
cout << endl;*/
while (j < n && j == s[ip[iz[j]]])
++j;
if (j < n)
a[i] = iz[j], b[i] = p[is[j]];
else
a[i] = b[i] = 0;
swap(iz[z[a[i]]], iz[z[b[i]]]);
swap(z[a[i]], z[b[i]]);
/*cout << "prej" << endl;
for (int t = 0; t < n; ++t)
cout << s[ip[iz[t]]] << " ";
cout << endl;*/
swap(iz[z[x[i]]], iz[z[y[i]]]);
swap(z[x[i]], z[y[i]]);
swap(p[ip[x[i]]], p[ip[y[i]]]);
swap(ip[x[i]], ip[y[i]]);
/*cout << "po" << endl;
for (int t = 0; t < n; ++t)
cout << s[ip[iz[t]]] << " ";
cout << endl;*/
}
while (j < n && j == s[ip[iz[j]]])
++j;
return j == n;
};
int l = 1, r = m;
while (l < r)
{
int mid = (l + r) / 2;
if (solve(mid))
r = mid;
else
l = mid + 1;
}
solve(l);
// solve(l);
return l;
}
