#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
using namespace std;
vector<pair<int,int>> solve(int n, vector<int> oldvec, int x[], int y[], int m) {
//cout << m << endl << "=======================" << endl;
vector<int> newvec = oldvec;
for (int i=0;i<m;i++) swap(newvec[x[i]], newvec[y[i]]);
vector<int> newvecpos(n);
//for (int i=0;i<n;i++) {cout << newvec[i] << endl;}
for (int i=0;i<n;i++) newvecpos[newvec[i]] = i;
vector<pair<int,int>> swapvals, moves;
unordered_set<int> visited;
int val;
for (int i=0;i<n;i++) {
if (visited.find(i) != visited.end()) continue;
val = i;
while (visited.find(val) == visited.end()) {
swapvals.pb(mp(val, newvec[val]));
visited.insert(val);
val = newvec[val];
}
swapvals.pop_back();
}
//for (pair<int,int> i: swapvals) {
// cout << i.ff << ' ' << i.ss << endl;
//}
//cout << endl;
if (swapvals.size() > m) return moves;
vector<int> oldvecpos(n);
for (int i=0;i<n;i++) oldvecpos[oldvec[i]] = i;
for (int i=0;i<swapvals.size();i++) {
swap(oldvec[x[i]], oldvec[y[i]]);
swap(oldvecpos[oldvec[x[i]]], oldvecpos[oldvec[y[i]]]);
moves.pb(mp(oldvecpos[swapvals[i].ff], oldvecpos[swapvals[i].ss]));
swap(oldvecpos[swapvals[i].ff], oldvecpos[swapvals[i].ss]);
swap(oldvec[oldvecpos[swapvals[i].ff]], oldvec[oldvecpos[swapvals[i].ss]]);
}
for (int i=0;i<m-swapvals.size();i++) {
moves.pb(mp(0, 0));
}
return moves;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
bool asdf = true;
for (int i=0;i<n;i++) {
if (s[i] != i) {
asdf = false;
break;
}
}
if (asdf) return 0;
vector<int> seq(n);
for (int i=0;i<n;i++) seq[i] = s[i];
vector<pair<int,int>> tempans, ans;
int top = m, bottom = 0, middle;
while (top > bottom + 1) {
middle = (top + bottom) / 2;
tempans = solve(n, seq, x, y, middle);
if (tempans.size() == 0) {
bottom = middle;
} else {
top = middle;
ans = tempans;
}
}
for (int i=0;i<ans.size();i++) {
p[i] = ans[i].ff;
q[i] = ans[i].ss;
}
return ans.size();
}
