/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const int MAX = 2e5+5;
int *s, *x, *y, *p, *q, n;
int obj[MAX], cur[MAX];
int orev[MAX], crev[MAX];
bool trial(int t) {
for (int i = 0; i < n; ++i)obj[i] = i;
for (int i = t-1; i >= 0; --i)swap(obj[x[i]], obj[y[i]]);
for (int i = 0; i < n; ++i)
orev[obj[i]] = i,
cur[i] = s[i],
crev[s[i]] = i;
int pt = 0;
for (int i = 0; i < t; ++i) {
swap(obj[x[i]], obj[y[i]]);
swap(cur[x[i]], cur[y[i]]);
crev[cur[x[i]]] = x[i];
orev[obj[x[i]]] = x[i];
crev[cur[y[i]]] = y[i];
orev[obj[y[i]]] = y[i];
while (pt < n && crev[pt] == orev[pt])pt += 1;
if (pt == n) {
p[i] = q[i] = 0;
continue;
}
int p1 = crev[pt];
int p2 = orev[pt];
p[i] = p1, q[i] = p2;
swap(cur[p1], cur[p2]);
crev[cur[p1]] = p1;
crev[cur[p2]] = p2;
}
while (pt < n && crev[pt] == orev[pt])pt += 1;
return (pt == n);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N, s = S, x = X, y = Y, p = P, q = Q;
int l = 0, r = M;
while (l != r) {
int m = l+r>>1;
if (trial(m))r = m;
else l = m+1;
}
trial(l);
return l;
}
