#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 6e5 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
int M;
int S[MAXN];
int X[MAXN], Y[MAXN];
int P[MAXN], Q[MAXN];
bool vis[MAXN];
int cur[MAXN], ind[MAXN];
bool moo (int nsteps, bool dbg = false) {
for (int i = 0; i < N; i++) {
cur[i] = S[i];
}
for (int i = 0; i < nsteps; i++) {
swap(cur[X[i]], cur[Y[i]]);
}
//check if you can do it
vector<pii> swaps;
for (int i = 0; i < N; i++) {
while (cur[i] != i) {
swaps.push_back({cur[i], cur[cur[i]]});
swap(cur[i], cur[cur[i]]);
}
}
if (swaps.size() > nsteps) {
return false;
}
while (swaps.size() < nsteps) {
swaps.push_back({0, 0});
}
for (int i = 0; i < N; i++) {
cur[i] = S[i];
ind[cur[i]] = i;
}
for (int i = 0; i < nsteps; i++) {
int x = X[i], y = Y[i];
swap(ind[cur[x]], ind[cur[y]]);
swap(cur[x], cur[y]);
x = swaps[i].fi;
y = swaps[i].se;
P[i] = ind[x];
Q[i] = ind[y];
swap(cur[ind[x]], cur[ind[y]]);
swap(ind[x], ind[y]);
}
return true;
}
int findSwapPairs (int nn, int ss[], int mm, int xx[], int yy[], int ansp[], int ansq[]) {
N = nn;
for (int i = 0; i < N; i++) {
S[i] = ss[i];
}
M = mm;
for (int i = 0; i < M; i++) {
X[i] = xx[i];
Y[i] = yy[i];
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
}
int lo = -1, hi = M; //lo is not possible, hi is
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (moo(mid)) {
hi = mid;
} else {
lo = mid;
}
}
moo(hi);
for (int i = 0; i < hi; i++) {
ansp[i] = P[i];
ansq[i] = Q[i];
}
return hi;
}
