#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define pii pair<int,int>
vector<pii> swaps;
vector<pii> evil;
vector<int> arr;
int n;
vector<pii> insertion_sort(vector<int> arr){
vector<int> pos(n);
for(int i = 0; i < n; i++){
pos[arr[i]] = i;
}
vector<pii> ops;
for(int i = n-1; i >= 0; i--){
if(arr[i] == i) continue;
int p = pos[i];
swap(arr[i], arr[pos[i]]);
pos[arr[i]] = i;
pos[arr[p]] = p;
ops.push_back({i,p});
}
return ops;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
int ops = 0;
arr.resize(N);
evil.resize(M);
for(int i = 0; i < M; i++){
evil[i] = {X[i], Y[i]};
}
for(int i = 0; i < n; i++){
arr[i] = S[i];
}
vector<int> cur = arr;
for(int i = 0; i <= M; i++){
auto moves = insertion_sort(cur);
if(moves.size() <= i){
for(int j = 0; j < moves.size(); j++){
P[j] = moves[j].first;
Q[j] = moves[j].second;
}
return moves.size();
}
if(i == M) break;
swap(cur[evil[i].first], cur[evil[i].second]);
}
return swaps.size();
}
