#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int mod = 1e9+7;
int N, M;
vi S, X, Y, P, Q;
vii swaps;
bool solve(int R){
swaps.clear();
vi perm = S;
FOR(i, 0, R) swap(perm[X[i]], perm[Y[i]]);
// VALUES that should be swapped
vi idx(N);
FOR(i, 0, N) idx[perm[i]] = i;
int cnt = 0;
FOR(i, 0, N){
if(i != perm[i]) {
cnt++;
swaps.pb({perm[i], i});
//cout << perm[i] << " " << i << endl;
int pi = perm[i];
swap(perm[i], perm[idx[i]]);
swap(idx[i], idx[pi]);
}
}
FOR(i, swaps.size(), R) swaps.pb({0, 0});
//for(int i : perm) cout << i << " ";
//cout << endl;
return cnt <= R;
}
INT findSwapPairs(INT n, INT s[], INT m, INT x[], INT y[], INT p[], INT q[]) {
N = n; M = m;
FOR(i, 0, N) S.pb(s[i]);
FOR(i, 0, M) X.pb(x[i]), Y.pb(y[i]);
int lb = -1, rb = M;
while(lb + 1 != rb){
int mb = (lb+rb)/2;
if(solve(mb)) rb = mb;
else lb = mb;
}
solve(rb);
vi idx(N);
FOR(i, 0, N) idx[S[i]] = i;
FOR(i, 0, swaps.size()){
swap(idx[S[X[i]]], idx[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
p[i] = idx[swaps[i].fst];
q[i] = idx[swaps[i].snd];
swap(S[idx[swaps[i].fst]], S[idx[swaps[i].snd]]);
swap(idx[swaps[i].fst], idx[swaps[i].snd]);
}
return swaps.size();
}
