/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: sorting
* score: 100.0
* date: 2019-06-23 09:06:27.945005
*/
#include "sorting.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e6 + 500;
int E[N], EE[N], P[N], Q[N], S[N], SSS[N], X[N], Y[N], n;
queue < int > q;
bool check(int m){
for(int i = 0;i < n;i++) S[i] = SSS[i];
for(int i = 0;i < n;i++) EE[i] = i, E[i] = i;
for(int i = m - 1;i >= 0;i--) {
swap(E[EE[X[i]]], E[EE[Y[i]]]);
swap(EE[X[i]], EE[Y[i]]);
}
for(int i = 0;i < n;i++){
q.push(i);
}
for(int i = 0;i < m;i++){
swap(S[X[i]], S[Y[i]]);
swap(EE[X[i]], EE[Y[i]]);
swap(E[EE[X[i]]], E[EE[Y[i]]]);
if(X[i] != E[S[X[i]]]) q.push(X[i]);
if(Y[i] != E[S[Y[i]]]) q.push(Y[i]);
P[i] = 0, Q[i] = 0;
for(;!q.empty() && q.front() == E[S[q.front()]]; q.pop());
if(!q.empty()) P[i] = q.front(), Q[i] = E[S[q.front()]];
swap(S[P[i]], S[Q[i]]);
}
for(;!q.empty() && q.front() == E[S[q.front()]]; q.pop());
return q.empty();
}
int findSwapPairs(int nn, int SS[], int M, int XX[], int YY[], int PP[], int QQ[]) {
n = nn;
for(int i = 0;i < M;i++) X[i] = XX[i], Y[i] = YY[i];
for(int i = 0;i < n;i++) SSS[i] = SS[i];
int ans = -1;
for(int i = 20;i >= 0;i--){
if(ans + (1 << i) <= M && !check(ans + (1 << i)))
ans += (1 << i);
}
check(ans + 1);
for(int i = 0;i <= ans;i++)
PP[i] = P[i], QQ[i] = Q[i];
return ans + 1;
}
