#include "sorting.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;
const int maxn = 200010;
int pos[maxn];
int pospos[maxn];
int pos2[maxn];
void swap_by_idx(int a[], int p[], int i, int j)
{
swap(p[a[i]], p[a[j]]);
swap(a[i], a[j]);
}
void swap_by_val(int a[], int p[], int i, int j)
{
swap_by_idx(a, p, p[i], p[j]);
}
bool can(int r, int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
Loop (i,0,N)
pospos[i] = pos[i] = i;
LoopR (i,0,r)
swap_by_val(pos, pospos, X[i], Y[i]);
Loop (i,0,N)
pos2[S[i]] = i;
vector<pii> vec;
vector<int> where_should_go(N);
Loop (i,0,N)
where_should_go[pos[i]] = i;
Loop (i,0,N) {
while (where_should_go[pos2[i]] != i) {
vec.push_back({pos2[i], pos2[where_should_go[pos2[i]]]});
swap(pos2[i], pos2[where_should_go[pos2[i]]]);
}
}
if (vec.size() > r)
return 0;
if (P && Q) {
Loop (i,0,N)
pos[i] = pospos[i] = i;
Loop (i,0,vec.size()) {
swap_by_val(pos, pospos, X[i], Y[i]);
P[i] = pos[vec[i].first];
Q[i] = pos[vec[i].second];
}
Loop (i,vec.size(),r)
P[i] = Q[i] = 0;
}
return 1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int l = 0, r = M;
while (l < r) {
int m = (l+r)/2;
if (can(m, N, S, M, X, Y, 0, 0))
r = m;
else
l = m+1;
}
can(l, N, S, M, X, Y, P, Q);
return l;
}
