// 0 indexed answer
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5, M = 1e6 + 5;
int n, m;
arr<int, N> sq;
arr<pii, M> ch;
arr<int, N> cr, ps;
void intl() {
cr = sq;
for (int i = 1; i <= n; i++) ps[cr[i]] = i;
}
void swp(int i, int j) {
int x = cr[i], y = cr[j];
swap(ps[x], ps[y]);
swap(cr[i], cr[j]);
}
vec<pii> act;
arr<pii, N> ans;
bool bld(int k) {
intl(), act.clear();
for (int i = 1; i <= k; i++) swp(ch[i].fir, ch[i].sec);
// for (int i = 1; i <= n; i++)
// cout << cr[i] << " ";
// cout << '\n';
for (int i = 1; i <= n; i++) {
if (cr[i] == i) continue;
act.push_back({cr[i], i});
swp(ps[cr[i]], ps[i]);
}
// for (pii x : act) cout << x.fir << " " << x.sec << '\n';
if (act.size() > k) return false;
intl(), ans.fill({0, 0});
for (int i = 1; i <= k; i++) {
swp(ch[i].fir, ch[i].sec);
if (act.size() < i) ans[i] = {1, 1};
else {
ans[i] = {ps[act[i - 1].fir], ps[act[i - 1].sec]};
swp(ans[i].fir, ans[i].sec);
}
}
// for (int i = 1; i <= n; i++)
// cout << cr[i] << " ";
// cout << '\n';
for (int i = 1; i <= n; i++) assert(cr[i] == i);
return true;
}
int srch() {
int lw = 0, hg = n;
while (lw != hg) {
int md = (lw + hg) / 2;
if (bld(md)) hg = md;
else lw = md + 1;
}
return lw;
}
int findSwapPairs(int _n, int _sq[], int _m, int _ch0[], int _ch1[], int ans0[], int ans1[]) {
n = _n, m = _m;
for (int i = 1; i <= n; i++) sq[i] = _sq[i - 1] + 1;
for (int i = 1; i <= m; i++) ch[i] = {_ch0[i - 1] + 1, _ch1[i - 1] + 1};
int k = srch();
bld(k);
for (int i = 1; i <= k; i++)
ans0[i - 1] = ans[i].fir - 1, ans1[i - 1] = ans[i].sec - 1;
return k;
}
