#include "sorting.h"
#include <vector>
const int NMAX = 2e5;
const int MMAX = 30 * NMAX;
int n, s[NMAX + 2], aux[NMAX + 2], inv[NMAX + 2];
int x[MMAX + 2], y[MMAX + 2];
bool vis[NMAX + 2];
std::vector <int> curr;
std::vector < std::vector <int> > cycles;
void dfs(int node)
{
vis[node] = 1;
curr.push_back(node);
if(!vis[aux[node]])
dfs(aux[node]);
}
bool Sorted(int limit)
{
for(int i = 0; i < n; i++)
aux[i] = s[i], vis[i] = 0;
for(int i = 0; i < limit; i++)
std::swap(aux[x[i]], aux[y[i]]);
cycles.clear();
for(int i = 0; i < n; i++)
if(!vis[i])
{
curr.clear();
dfs(i);
cycles.push_back(curr);
}
int t = 0;
for(auto it : cycles)
t += ((int)it.size() - 1);
return (t <= limit);
}
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 st = 0, dr = N, sol = -1;
while(st <= dr)
{
int mid = (st + dr) >> 1;
if(Sorted(mid))
{
sol = mid;
dr = mid - 1;
}
else
{
st = mid + 1;
}
}
///to reconstruct the cycles
Sorted(sol);
std::vector < std::pair<int,int> > moves;
for(auto it : cycles)
{
for(int i = 0; i < (int)it.size() - 1; i++)
{
moves.push_back({it[i], it[i + 1]});
}
}
for(int i = 0; i < n; i++)
{
inv[s[i]] = i;
}
for(int i = 0; i < sol; i++)
{
int preX = s[X[i]];
int preY = s[Y[i]];
inv[preX] = Y[i];
inv[preY] = X[i];
std::swap(s[X[i]], s[Y[i]]);
if(!moves.empty())
{
P[i] = inv[moves.back().first];
Q[i] = inv[moves.back().second];
moves.pop_back();
}
else
{
P[i] = Q[i] = 0;
}
}
return sol;
}
