#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 2e5;
int n, m;
vector<pii > ans;
void upd(pii cur_swap, vector<int> &pos, vector<int> &which, vector<int> &to, vector<int> &where) {
// cur_swap: position of two places
int pos_a = cur_swap.fi, pos_b = cur_swap.se;
int which_a = which[pos_a], which_b = which[pos_b];
swap(where[which_a], where[which_b]);
swap(to[pos_a], to[pos_b]);
swap(which[pos_a], which[pos_b]);
swap(pos[which_a], pos[which_b]);
}
bool ok(int k, vector<int> which, vector<pii > swaps, bool create_swap_order) {
swaps.resize(k);
if(k == 0) {
for(int i = 1; i <= n; i++) {
if(which[i] != i) {
return false;
}
}
return true;
}
vector<int> to(1 + n, 0);
for(int i = 1; i <= n; i++) {
to[i] = i;
}
for(auto it = swaps.rbegin(); it != swaps.rend(); it++) {
pii p = *it;
swap(to[p.fi], to[p.se]);
}
vector<int> where(1 + n, 0);
vector<int> pos(1 + n, 0);
for(int i = 1; i <= n; i++) {
where[to[i]] = i;
pos[which[i]] = i;
}
vector<int> perm(1 + n, 0);
for(int i = 1; i <= n; i++) {
perm[pos[i]] = where[i];
}
vector<pii > ans_elem;
vector<bool> vis(1 + n, false);
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
int x = i;
int depth = 0;
vis[x] = true;
while(!vis[perm[x]]) {
if(create_swap_order) {
ans_elem.pb(mp(which[x], which[perm[x]]));
}
x = perm[x];
vis[x] = true;
depth++;
}
cnt += depth;
}
}
if(!create_swap_order) {
return (cnt <= k);
}
while(ans_elem.size() < k) {
ans_elem.pb(mp(1, 1));
}
ans.resize(k);
for(int i = 0; i < k; i++) {
pii cur_swap = swaps[i];
upd(cur_swap, pos, which, to, where);
ans[i] = mp(pos[ans_elem[i].fi], pos[ans_elem[i].se]);
upd(ans[i], pos, which, to, where);
}
return true;
}
vector<int> which;
vector<pii > swaps;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
which.assign(1 + n, 0);
for(int i = 1; i <= n; i++) {
which[i] = S[i - 1] + 1;
}
m = M;
for(int i = 0; i < m; i++) {
swaps.pb(mp(X[i] + 1, Y[i] + 1));
}
int l = -1, r = m + 1;
while(l < r - 1) {
int mid = (l + r) / 2;
if(ok(mid, which, swaps, false)) {
r = mid;
} else {
l = mid;
}
}
int k = r;
if(k == 0) {
// no need to modify P/Q here
return 0;
}
ok(k, which, swaps, true);
for(int i = 0; i < k; i++) {
P[i] = ans[i].fi - 1;
Q[i] = ans[i].se - 1;
}
return k;
}
