#include "sorting.h"
#include <stdio.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, cnt, sorted;
for (i = 0; i < n; i++)
vv[pp[i]] = i;
sorted = 1;
for (i = 0; i < n; i++)
if (pp[i] != i) {
sorted = 0;
break;
}
if (sorted)
return 0;
for (r = 1; r <= m; r++) {
int p, q, u, v;
p = pp[aa[r - 1]], q = pp[bb[r - 1]], u = aa[r - 1], v = bb[r - 1];
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++;
}
if (cnt <= r) {
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;
}
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;
p = pp[ii[h]], q = pp[jj[h]], u = ii[h], v = jj[h];
pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
}
return r;
}
}
return -1;
}
