#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());
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int li = 0, ri = M + 1;
while (ri - li > 1) {
int t = (li + ri) / 2;
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]]);
}
bool fl = true;
for (; j < N; ++j) {
if (q2[j] != j) {
fl = false;
break;
}
}
if (fl) {
li = t;
}
else {
ri = t;
}
}
int t = li;
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]]);
}
return li;
}
