//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "sorting.h"
#define all(x) x.begin(), x.end()
using namespace std;
vector<pair<int, int>> numswp(vector<int> a) {
    set<int> beba;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != i)
            beba.insert(i);
    }
    vector<pair<int, int>> swps;
    while (!beba.empty()) {
        int v = *beba.begin();
        int u = a[v];
        if (v != u)
            swps.push_back({a[v], a[u]});
        swap(a[v], a[u]);
    }
    if (!is_sorted(all(a))) exit(1);
    return swps;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    vector<int> astrt(N);
    for (int i = 0; i < N; ++i) {
        astrt[i] = S[i];
    }
    int l = -1, r = M;
    while (l + 1 < r) {
        int m = l + r >> 1;
        vector<int> beba = astrt;
        for (int i = 0; i < m; ++i) {
            swap(beba[X[i]], beba[Y[i]]);
        }
        if (numswp(beba).size() <= m)
            r = m;
    }
    int m = l + r >> 1;
    vector<int> beba = astrt;
    for (int i = 0; i < m; ++i) {
        swap(beba[X[i]], beba[Y[i]]);
    }
    vector<pair<int, int>> swp = numswp(beba);
    if (beba.size() > r)
        exit(1);
    beba = astrt;
    vector<int> ind(N);
    for (int i = 0; i < N; ++i) {
        ind[beba[i]] = i;
    }
    for (int i = 0; i < swp.size(); ++i) {
        swap(ind[beba[X[i]]], ind[beba[Y[i]]]);
        swap(beba[X[i]], beba[Y[i]]);
        P[i] = ind[swp[i].first];
        Q[i] = ind[swp[i].second];
        swap(beba[P[i]], beba[Q[i]]);
        swap(ind[swp[i].first], ind[swp[i].second]);
    }
    for (int i = swp.size(); i < r; ++i) {
        swap(ind[beba[X[i]]], ind[beba[Y[i]]]);
        swap(beba[X[i]], beba[Y[i]]);
        P[i] = 0;
        Q[i] = 0;
    }
    if (!is_sorted(all(beba)))
        exit(1);
    return r;
}