#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "sorting.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200'000;
int val[MAXN + 10];
int pos[MAXN + 10];
int tmp[MAXN + 10];
bool check(int n, int lim, vector<pii> &ops) {
For(i, 0, n - 1) tmp[i] = val[i];
ops.clear();
For(i, 0, n - 1) {
while(tmp[i] != i) {
ops.eb(tmp[i], tmp[tmp[i]]);
swap(tmp[i], tmp[tmp[i]]);
}
}
return sz(ops) <= lim;
}
void out(int n) {
cerr << "out:\n";
cerr << " "; For(i, 0, n - 1) cerr << val[i] << " \n"[i == n - 1];
cerr << " "; For(i, 0, n - 1) cerr << pos[i] << " \n"[i == n - 1];
}
int32_t findSwapPairs(int32_t N, int32_t S[], int32_t M, int32_t X[], int32_t Y[], int32_t P[], int32_t Q[]) {
bool pote = true;
For(i, 0, N - 1) {
val[i] = S[i];
pos[val[i]] = i;
if(S[i] != i) pote = false;
}
if(pote) return 0;
// out(N);
For(i, 0, M - 1) {
int p1 = X[i], p2 = Y[i];
swap(pos[val[p1]], pos[val[p2]]);
swap(val[p1], val[p2]);
// For(j, 0, N - 1) cerr << val[j] << " \n"[j == N - 1];
vector<pii> op;
if(check(N, i + 1, op)) {
For(j, sz(op), i) P[j] = Q[j] = 0;
assert(sz(op) >= i);
Forr(j, i, 0) {
if(j < sz(op)) {
int v1 = op[j].F;
int v2 = op[j].S;
P[j] = (int32_t)pos[v1];
Q[j] = (int32_t)pos[v2];
swap(val[pos[v1]], val[pos[v2]]);
swap(pos[v1], pos[v2]);
// out(N);
}
p1 = X[j]; p2 = Y[j];
swap(pos[val[p1]], pos[val[p2]]);
swap(val[p1], val[p2]);
// out(N);
}
return (int32_t)(i + 1);
}
// cerr << "\n";
}
assert(false);
return 0;
}
/*
30421
10423
10243
*/
