#include "sorting.h"
#include <string.h>
#define N 200000
int findSwapPairs(int n, int pp[], int m, int aa[], int bb[], int ii[], int jj[]) {
static char visited[N];
static int vv[N];
int h, i, j, r, p, q, u, v, lower, upper, cnt;
for (i = 0; i < n; i++)
vv[pp[i]] = i;
lower = -1, upper = m;
while (upper - lower > 1) {
r = (lower + upper) / 2;
for (h = 0; h < r; h++) {
p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
}
memset(visited, 0, n * sizeof *visited);
cnt = 0;
for (i = 0; i < n; i++)
if (!visited[i]) {
visited[i] = 1;
for (j = pp[i]; !visited[j]; j = pp[j])
visited[j] = 1, cnt++;
}
for (h = r - 1; h >= 0; h--) {
p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
}
if (cnt <= r)
upper = r;
else
lower = r;
}
r = upper;
for (h = 0; h < r; h++) {
p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
}
memset(visited, 0, n * sizeof *visited);
cnt = 0;
for (i = 0; i < n; i++)
if (!visited[i]) {
visited[i] = 1;
for (j = pp[i]; !visited[j]; j = pp[j])
visited[j] = 1, ii[cnt] = pp[i], jj[cnt] = pp[j], cnt++;
}
for (h = r - 1; h >= 0; h--) {
if (h < cnt)
ii[h] = vv[ii[h]], jj[h] = vv[jj[h]];
else
ii[h] = 0, jj[h] = 0;
p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
}
return r;
}
