#include "sorting.h"
#include<algorithm>
#define DIM 200005
#define f first
#define s second
using namespace std;
static int n, m, v[DIM], p[DIM], ind[DIM], viz[DIM], pos[DIM];
static pair<int, int> sol[DIM], w[DIM];
static void swappos(int x, int y){
swap(p[x], p[y]);
pos[ p[x] ] = x;
pos[ p[y] ] = y;
}
static int solve(int k){
int i, nr = 0, x;
for(i = 1; i <= n; i++){
ind[i] = i;
viz[i] = 0;
}
for(i = 1; i <= k; i++){
swap(ind[ w[i].f ], ind[ w[i].s ]);
}
for(i = 1; i <= n; i++){
p[i] = v[ ind[i] ];
}
for(i = 1; i <= n; i++){
if(viz[i] == 0){
viz[i] = 1;
x = i;
while(viz[ p[x] ] == 0){
sol[++nr] = make_pair(p[x], p[ p[x] ]);
x = p[x];
viz[x] = 1;
}
}
}
if(nr <= k){
for(i = 1; i <= n; i++){
p[i] = v[i];
pos[ p[i] ] = i;
}
for(i = 1; i <= nr; i++){
swappos(w[i].f, w[i].s);
sol[i].f = pos[ sol[i].f ];
sol[i].s = pos[ sol[i].s ];
swappos(sol[i].f, sol[i].s);
}
for(; i <= k; i++){
sol[i] = make_pair(1, 1);
}
return 1;
}
return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int i, st, dr, mid;
n = N;
m = M;
for(i = 1; i <= n; i++){
v[i] = S[i - 1] + 1;
}
for(i = 1; i <= m; i++){
w[i] = make_pair(X[i - 1] + 1, Y[i - 1] + 1);
}
st = 0;
dr = m;
while(st <= dr){
mid = (st + dr) / 2;
if( solve(mid) ){
dr = mid - 1;
}
else{
st = mid + 1;
}
}
solve(st);
for(i = 0; i < st; i++){
P[i] = sol[i + 1].f - 1;
Q[i] = sol[i + 1].s - 1;
}
return st;
}
