#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <queue>
#include <random>
#include "sorting.h"
using namespace std;
#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())
#define pb push_back
#define chmin(x, y) (x = min(x, y))
#define chmax(x, y) (x = max(x, y))
/********* DEBUG *********/
bool grrrrrrrrrr = 1;
template <typename T>
void outvec(const vector<T>& Z){
if (!grrrrrrrrrr)
return;
for (const T& x : Z)
cout << x << ' ';
cout << "\n";
}
void printVariable(const any& var) {
if (!var.has_value()) {
cout << "null";
return;
}
if (var.type() == typeid(int)) {
cout << any_cast<int>(var);
} else if (var.type() == typeid(double)) {
cout << any_cast<double>(var);
} else if (var.type() == typeid(float)) {
cout << any_cast<float>(var);
} else if (var.type() == typeid(char)) {
cout << any_cast<char>(var);
} else if (var.type() == typeid(bool)) {
cout << (any_cast<bool>(var) ? "true" : "false");
} else if (var.type() == typeid(string)) {
cout << any_cast<string>(var);
} else if (var.type() == typeid(const char*)) {
cout << any_cast<const char*>(var);
} else if (var.type() == typeid(long long)) {
cout << any_cast<long long>(var);
} else {
cout << "[unknown type]";
}
}
template<typename... Args>
void outval(Args... args) {
if (!grrrrrrrrrr)
return;
vector<any> variables = {args...};
for (size_t i = 0; i < variables.size(); ++i) {
printVariable(variables[i]);
if (i != variables.size() - 1) {
cout << " ";
}
}
cout << "\n";
}
#define sp << " " <<
#define fi first
#define se second
/********* DEBUG *********/
const ll MOD2 = 1e9 + 7;
const ll MOD = 998244353;
const ll inf = 1e18;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<ll> place(N), orig(N);
for (int i = 0; i < N; i++){
place[S[i]] = i;
orig[i] = S[i];
}
int l = 0, r = N;
while (l < r){
int m = (l + r) / 2;
for (int i = 0; i < N; i++)
S[i] = orig[i];
for (int i = 0; i < m; i++){
swap(S[X[i]], S[Y[i]]);
}
for (int i = 0; i < N; i++){
place[S[i]] = i;
}
int ans = 0;
vector<bool> seen(N, 0);
for (int i = 0; i < N; i++){
if (seen[i])
continue;
seen[i] = 1;
int cur = i;
while (!seen[S[cur]]){
seen[S[cur]] = true;
cur = S[cur];
if (++ans > m)
break;
}
}
if (ans > m)
l = m+1;
else
r = m;
}
for (int i = 0; i < N; i++) S[i] = orig[i], place[S[i]] = i;
for (int i = 0; i < r; i++) swap(orig[X[i]], orig[Y[i]]);
vector<bool> seen(N, 0);
int p = 0;
for (int i = 0; i < N; i++){
if (seen[i])
continue;
seen[i] = 1;
int cur = i;
while (!seen[orig[cur]]){
seen[orig[cur]] = 1;
swap(S[X[p]], S[Y[p]]);
place[S[X[p]]] = X[p];
place[S[Y[p]]] = Y[p];
P[p] = place[orig[cur]];
Q[p] = place[orig[orig[cur]]];
swap(S[P[p]], S[Q[p]]);
place[S[P[p]]] = P[p];
place[S[Q[p]]] = Q[p];
cur = orig[cur];
p++;
}
}
for (int i = 0; i < N; i++){
cout << S[i] << ' ';
}
return r;
}
