#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
int n, m, s[lim], x[lim * 3], y[lim * 3];
bool check_sorted(){
for(int i = 0; i < n; i++){
if(s[i] != i){
return false;
}
}
return true;
}
namespace sub12{
int solve(int p[], int q[]){
int ans = 0;
for(int i = 0; i < n; i++){
if(s[i] != i){
swap(s[p[ans] = i], s[q[ans] = s[i]]);
ans++;
i--;
}
}
return ans;
}
}
namespace sub3{
int solve(int p[], int q[]){
int ans = 0;
for(int x = 2; x < n; x++){
int i = find(s, s + n, x) - s;
swap(s[0], s[1]);
if(i == 0){
i = 1;
}
else if(i == 1){
i = 0;
}
swap(s[p[ans] = i], s[q[ans] = x]);
ans++;
}
if(s[0] > s[1]){
p[ans] = q[ans] = 0;
ans++;
}
return ans;
}
}
namespace sub4{
int solve(int p[], int q[]){
memset(p, 0, sizeof(p));
memset(q, 0, sizeof(q));
vector<int>pos(n);
for(int i = 0; i < m; i++){
iota(pos.begin(), pos.end(), 0);
for(int j = i + 1; j < m; j++){
swap(pos[x[j]], pos[y[j]]);
}
swap(s[x[i]], s[y[i]]);
for(int j = 0; j < n; j++){
if(s[pos[j]] != j){
swap(s[p[i] = pos[j]], s[q[i] = find(s, s + n, j) - s]);
break;
}
}
}
return m;
}
}
namespace sub5{
int solve(int p[], int q[]){
vector<int>pos(n);
int low = 0, high = m, ans;
while(low <= high){
int mid = (low + high) >> 1;
vector<int>S(s, s + n);
iota(pos.begin(), pos.end(), 0);
for(int i = 0; i < mid; i++){
iota(pos.begin(), pos.end(), 0);
for(int j = i + 1; j < mid; j++){
swap(pos[x[j]], pos[y[j]]);
}
swap(S[x[i]], S[y[i]]);
for(int j = 0; j < n; j++){
if(S[pos[j]] != j){
swap(S[pos[j]], S[find(S.begin(), S.end(), j) - S.begin()]);
break;
}
}
}
bool flag = true;
for(int i = 0; i < n; i++){
if(S[i] != i){
flag = false;
break;
}
}
if(flag){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
memset(p, 0, sizeof(p));
memset(q, 0, sizeof(q));
for(int i = 0; i < ans; i++){
iota(pos.begin(), pos.end(), 0);
for(int j = i + 1; j < ans; j++){
swap(pos[x[j]], pos[y[j]]);
}
swap(s[x[i]], s[y[i]]);
for(int j = 0; j < n; j++){
if(s[pos[j]] != j){
swap(s[p[i] = pos[j]], s[q[i] = find(s, s + n, j) - s]);
break;
}
}
}
return ans;
}
}
namespace sub6{
int solve(int p[], int q[]){
vector<int>pos(n), ps(n);
int low = 0, high = m, ans;
while(low <= high){
int mid = (low + high) >> 1, cnt = 0;
vector<int>S(s, s + n);
for(int i = 0; i < mid; i++){
swap(S[x[i]], S[y[i]]);
}
for(int i = 0; i < n; i++){
ps[S[i]] = i;
}
for(int i = 0; i < n; i++){
if(ps[i] != i){
cnt++;
swap(S[i], S[ps[i]]);
swap(ps[S[i]], ps[S[ps[i]]]);
}
}
if(cnt <= mid){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
memset(p, 0, sizeof(p));
memset(q, 0, sizeof(q));
vector<int>S(s, s + n);
for(int i = 0; i < ans; i++){
swap(S[x[i]], S[y[i]]);
}
for(int i = 0; i < n; i++){
ps[S[i]] = i;
}
for(int i = 0; i < n; i++){
ps[s[i]] = i;
}
for(int i = 0, j = 0; i < n; i++){
if(S[i] != i){
swap(p[j] = S[i], q[j] = S[ps[i]]);
swap(ps[S[i]], ps[S[ps[i]]]);
j++;
}
}
for(int i = 0; i < ans; i++){
swap(s[x[i]], s[y[i]]);
swap(ps[s[x[i]]], ps[s[y[i]]]);
int x = p[i], y = q[i];
swap(s[p[i] = ps[x]], s[q[i] = ps[y]]);
swap(ps[x], ps[y]);
}
return ans;
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
memcpy(s, S, sizeof(int) * (n = N));
memcpy(x, X, sizeof(int) * (m = M));
memcpy(y, Y, sizeof(int) * m);
if(n == 1){
return 0;
}
if(m == 30 * n){
int mx = *max_element(x, x + m), my = *max_element(y, y + m);
if(mx == 0){
if(my == 0){
return sub12::solve(P, Q);
}
if(my == 1){
return sub3::solve(P, Q);
}
}
return sub4::solve(P, Q);
}
if(n <= 2000){
return sub5::solve(P, Q);
}
return sub6::solve(P, Q);
}
