#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <array>
#include <map>
#include <random>
#include <bitset>
#include <stack>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <chrono>
//#include "towns.h"
using namespace std;
typedef long long ll;
typedef long double ld;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
bool calc(int N, int S[], int T, int X[], int Y[], int P[], int Q[]) {
vector<int> p1(N), p2(N);
for (int i = 0; i < N; ++i) {
p1[i] = S[i];
p2[i] = S[i];
}
for (int i = 0; i < T; ++i) {
swap(p2[X[i]], p2[Y[i]]);
}
vector<int> q1(N), q2(N);
for (int i = 0; i < N; ++i) {
q1[p1[i]] = i;
q2[p2[i]] = i;
}
int j = 0;
for (int i = 0; i < T; ++i) {
swap(q1[p1[X[i]]], q1[p1[Y[i]]]);
swap(p1[X[i]], p1[Y[i]]);
P[i] = 0;
Q[i] = 0;
for (; j < N; ++j) {
if (q2[j] != j) {
P[i] = q1[j];
Q[i] = q1[p2[j]];
break;
}
}
swap(p2[q2[p1[P[i]]]], p2[q2[p1[Q[i]]]]);
swap(q2[p1[P[i]]], q2[p1[Q[i]]]);
swap(q1[p1[P[i]]], q1[p1[Q[i]]]);
swap(p1[P[i]], p1[Q[i]]);
}
for (; j < N; ++j) {
if (q2[j] != j) {
return false;
}
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int li = -1, ri = M;
while (ri - li > 1) {
int t = (li + ri) / 2;
if (calc(N, S, t, X, Y, P, Q)) {
ri = t;
}
else {
li = t;
}
}
calc(N, S, ri, X, Y, P, Q);
return ri;
}
