#include "sorting.h"
#include <algorithm>
#include <iostream>
#include <set>
#include <assert.h>
using namespace std;
int N;
int S [1000000];
int X [1000000];
int Y [1000000];
bool check(int M){
int A_ [N];
for(int i = 0; i < N; i++){
A_[i] = i;
}
for(int i = M-1; i >= 0; i--){
swap(A_[X[i]], A_[Y[i]]);
}
int A [N];
for(int i = 0; i < N; i++){
A[A_[i]] = S[i];
}
int numCyc = 0;
bool vis [N];
for(int i = 0; i < N; i++){
vis[i] = false;
}
for(int i = 0; i < N; i++){
if(!vis[i]){
numCyc++;
int cur = i;
while(!vis[cur]){
vis[cur] = true;
cur = A[cur];
}
}
}
// cerr << numCyc << endl;
if((N - numCyc) <= M){
return true;
}else{
return false;
}
}
int findSwapPairs(int N_, int S_[], int M, int X_[], int Y_[], int P[], int Q[]) {
N = N_;
for(int i = 0; i < N; i++){
S[i] = S_[i];
}
for(int i = 0; i < M; i++){
X[i] = X_[i];
Y[i] = Y_[i];
}
int A [N];
int tmp [N];
int Sinv [N];
for(int i = 0; i < N; i++){
A[i] = i;
tmp[i] = S[i];
Sinv[S[i]] = i;
}
int low = 0;
int hig = M;
while(low != hig){
int mid = (low+hig)/2;
if(check(mid)){
hig = mid;
}else{
low = mid+1;
}
}
M = low;
// cerr << M << endl;
//go backwards
for(int i = M-1; i >= 0; i--){
swap(A[X[i]], A[Y[i]]);
}
set <int> mis;
for(int i = 0; i < N; i++){
if(A[i] != S[i]){
mis.insert(i);
}
}
for(int i = 0; i < M; i++){
swap(A[X[i]], A[Y[i]]);
swap(Sinv[S[X[i]]], Sinv[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
bool xin = mis.find(X[i]) != mis.end();
bool yin = mis.find(Y[i]) != mis.end();
if(xin && !yin){
mis.erase(X[i]);
mis.insert(Y[i]);
}
if(yin && !xin){
mis.erase(Y[i]);
mis.insert(X[i]);
}
bool done = false;
if(mis.empty()){
P[i] = 0;
Q[i] = 0;
}else{
int j = *(mis.begin());
int k = Sinv[A[j]];
/* for(int it = 0; it < N; it++){
cerr << S[it] << " ";
}
cerr << endl;
cerr << j << " " << k << endl;*/
P[i] = j;
Q[i] = k;
swap(Sinv[S[j]], Sinv[S[k]]);
swap(S[j], S[k]);
if(S[j] == A[j]){
mis.erase(j);
}else{
mis.insert(j);
}
if(S[k] == A[k]){
mis.erase(k);
}else{
mis.insert(k);
}
}
}
for(int i = 0; i < N; i++){
assert(S[i] == i);
}
for(int i = 0; i < M; i++){
swap(tmp[X[i]], tmp[Y[i]]);
swap(tmp[P[i]], tmp[Q[i]]);
//cerr << X[i] << " " << Y[i] << " ";
//cerr << P[i] << " " << Q[i] << " ";
/*for(int j = 0; j < N; j++){
cerr << tmp[j] << " ";
}
cerr << endl;*/
}
for(int i = 0; i < N; i++){
assert(tmp[i] == i);
}
//cerr << "ASSERTS OK" << endl;
/*for(int i = 0; i < N; i++){
cerr << A[i] << " ";
}
cerr << endl;
for(int i = 0; i < N; i++){
cerr << S[i] << " ";
}
cerr << endl;*/
return M;
}
