#include <iostream>
#include "sorting.h"
#include <vector>
using namespace std;
int const NMAX = 5e5;
bool canSort(int n, int s[], int m, int x[], int y[]) {
int aux[1 + NMAX], cycle = 0;
int visit[1 + NMAX];
for(int i = 0;i < n;i++) {
aux[i] = s[i];
visit[i] = false;
}
for(int i = 0;i < m;i++) {
swap(aux[x[i]], aux[y[i]]);
}
for(int i = 0;i < n;i++) {
int index = i;
if(!visit[index]) {
cycle++;
while(!visit[index]) {
visit[index] = true;
index = aux[index];
}
}
}
return (m >= n - cycle);
}
int cautbinAns(int from, int to, int n, int s[], int x[], int y[]) {
if(from >= to) {
return from;
} else {
int mid = (from + to) / 2;
if(canSort(n, s, mid, x, y)) {
return cautbinAns(from, mid, n, s, x, y);
} else {
return cautbinAns(mid+1, to, n, s, x, y);
}
}
}
int arr[1 + NMAX];
int arrPos[1 + NMAX];
vector <pair <int, int>> swaps;
void buildSwap(int n, int s[], int m, int x[], int y[]) {
int aux[1 + NMAX];
int visit[1 + NMAX];
for(int i = 0;i < n;i++) {
aux[i] = s[i];
visit[i] = false;
}
for(int i = 0;i < m;i++) {
swap(aux[x[i]], aux[y[i]]);
}
for(int i = 0;i < n;i++) {
//cerr << aux[i] << ' ';
int index = i, to;
if(!visit[index]) {
while(!visit[index]) {
visit[index] = true;
to = aux[index];
if(!visit[to]) {
swaps.push_back({index, to});
}
//cerr << index << ' ' << aux[index] << '\n';
index = to;
}
}
}
//cerr << '\n';
}
void buildArr(int n, int s[]) {
for(int i = 0;i < n;i++) {
arr[i] = s[i];
arrPos[arr[i]] = i;
}
}
void printArr(int n) {
for(int i = 0;i < n;i++) {
cerr << arr[i] << ' ';
}
cerr << "\n";
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
int ans = cautbinAns(0, m, n, s, x, y), fix = 0;
buildSwap(n, s, ans, x, y);
buildArr(n, s);
int ind = 0;
for(int i = 0;i < ans;i++) {
int a = x[i], b = y[i];
swap(arrPos[arr[a]], arrPos[arr[b]]);
swap(arr[a], arr[b]);
if(ind < swaps.size()) {
p[i] = arrPos[swaps[ind].first];
q[i] = arrPos[swaps[ind].second];
//cerr << swaps[ind].first << ' ' << swaps[ind].second << " : " << p[i] << ' ' << q[i] << "\n";
swap(arrPos[arr[p[i]]], arrPos[arr[q[i]]]);
swap(arr[p[i]], arr[q[i]]);
ind++;
} else {
p[i] = q[i] = 0;
}
//printArr(n);
}
return ans;
}
