#include "permgame.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> void show(vector<T> &v) {
for (T i : v) {
cout << i << ' ';
}
cout << ln;
}
int getScore(int n, vi &p) {
int score = 0;
for (int i = 0; i < n; ++i) {
if (p[i] == i) ++score;
}
return score;
}
vvi getCycles(int n, vi &p) {
vvi cycles;
vi vis(n, 0);
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
vi cycle;
int node = i;
while (!vis[node]) {
vis[node] = 1;
cycle.eb(node);
node = p[node];
}
cycles.eb(cycle);
}
}
sort(all(cycles), [&](vi &i, vi &j) {return i.size() > j.size();});
return cycles;
}
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
int curScore = getScore(n, p);
vvi g(m);
for (int i = 0; i < e; ++i) {
g[u[i]].eb(v[i]);
g[v[i]].eb(u[i]);
}
int a = -1;
for (int i = 0; i < m; ++i) {
if (g[i].size() > 2) return curScore; // can't improve
if (g[i].size() == 1) a = i; // end of chain
}
vi ord;
if (a == -1) a = 0; // cycle
int b = -1;
for (int i = 0; i < m; ++i) {
ord.eb(a);
int nxt = g[a][0];
if (nxt == b) nxt = g[i][1];
b = a;
a = nxt;
}
int optimalScore;
vi t(m);
if (e == m - 1) {
if (curScore >= n - (m - 1)) return curScore;
optimalScore = n - (m - 1);
if (m == 2) optimalScore = n;
while (curScore < optimalScore) {
vvi cycles = getCycles(n, p);
int id = 0, pos = 0;
for (int i = 0; i < m; ++i) {
if (pos == size(cycles[id])) {
pos = 0;
++id;
}
t[ord[i]] = cycles[id][pos++];
}
int j = Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
curScore = getScore(n, p);
}
} else if (m == 3) {
vvi cycles = getCycles(n, p);
//for (auto c : cycles) show(c);
int oddCycles = 0;
for (auto c : cycles) if (c.size() % 2 == 1) ++oddCycles;
//cerr << "oddCycles = " << oddCycles << ln;
optimalScore = oddCycles;
int ops = 0;
while (curScore < optimalScore) {
vi oddCycle;
for (auto c : cycles) if (c.size() % 2 == 1) {
oddCycle = c;
break;
}
for (int i = 0; i < m; ++i) {
t[ord[i]] = oddCycle[i];
}
int j = Bob(t);
++ops;
assert(ops <= 3 * n);
swap(p[t[u[j]]], p[t[v[j]]]);
curScore = getScore(n, p);
}
} else if (m == 4) {
if (curScore == n - 5 || curScore >= n - 3) return curScore;
if (curScore == n - 4) optimalScore = n - 3;
else optimalScore = n - 5;
while (curScore < optimalScore) {
vvi cycles = getCycles(n, p);
int sz = cycles.size();
if (cycles[0].size() >= 4) {
for (int i = 0; i < m; ++i) {
t[ord[i]] = cycles[0][i];
}
if (cycles[0].size() == 6) t[ord[m - 1]] = cycles[0][m];
} else { // merge two cycles of size = 3 or size = 2
if (cycles[0].size() == 3 && cycles[1].size() == 3) {
for (int i = 0; i < m - 1; ++i) t[ord[i]] = cycles[0][i];
t[ord[m - 1]] = cycles[1][0];
} else {
while (cycles[sz - 1].size() == 1) --sz;
if (cycles[sz - 1].size() == 2 && cycles[sz - 2].size() == 2) {
t[ord[0]] = cycles[sz - 1][0];
t[ord[1]] = cycles[sz - 1][1];
t[ord[2]] = cycles[sz - 2][0];
t[ord[3]] = cycles[sz - 2][1];
} else {
assert(false);
}
}
}
int j = Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
curScore = getScore(n, p);
}
}
return optimalScore;
}
