#include "permgame.h"
#ifndef __BALU_DEFAULT_CODE__
#define __BALU_DEFAULT_CODE__
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &a) {
os << "(" << a.first << ", " << a.second << ")";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &a) {
os << "[ ";
for (int i = 0; i < int(a.size()); ++i) {
os << a[i];
if (i + 1 < int(a.size()))
os << ", ";
}
os << " ]";
return os;
}
#ifdef bbq
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
#endif // __BALU_DEFAULT_CODE__
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
auto cal = [&]() {
int ans = 0;
for (int i = 0; i < n; ++i)
ans += p[i] == i;
return ans;
};
if (e > m) return cal();
vector<int> t(m);
auto run = [&]() {
debug(t);
int j = Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
};
vector<vector<int>> G(m);
for (int i = 0; i < e; ++i) {
G[u[i]].pb(v[i]);
G[v[i]].pb(u[i]);
}
int s = 0;
for (int i = 0; i < m; ++i) {
if (SZ(G[i]) > 2) return cal();
if (SZ(G[i]) == 1)
s = i;
}
vector<int> ord;
{
vector<int> vis(m);
auto dfs = [&](auto _dfs, int u) -> void {
ord.pb(u), vis[u] = 1;
for (int i : G[u])
if (!vis[i])
_dfs(_dfs, i);
};
dfs(dfs, s);
}
auto handle4 = [&]() {
bool succ = false;
while (true) {
vector<int> vis(n);
vector<int> buk;
for (int i = 0; i < n; ++i) {
if (p[i] == i || vis[i]) continue;
vector<int> internal;
for (int j = i; !vis[j]; j = p[j])
internal.pb(j), vis[j] = 1;
if (SZ(internal) >= 4) {
buk = internal;
break;
}
}
if (buk.empty()) break;
succ = true;
for (int i = 0; i < m; ++i)
t[ord[i]] = buk[i];
run();
}
return succ;
};
auto handle6 = [&]() {
vector<int> vis(n);
vector<int> buk;
for (int i = 0; i < n; ++i) {
if (p[i] == i) continue;
vector<int> internal;
for (int j = i; !vis[j]; j = p[j])
internal.pb(j), vis[j] = 1;
if (SZ(internal) == 6) {
buk = internal;
break;
}
}
if (buk.empty()) return false;
t[ord[0]] = buk[0];
t[ord[1]] = buk[1];
t[ord[2]] = buk[2];
t[ord[3]] = buk[4];
run();
handle4();
return true;
};
auto handle22 = [&]() {
vector<int> vis(n);
vector<int> buk;
for (int i = 0; i < n; ++i) {
if (p[i] == i || vis[i]) continue;
vector<int> internal;
for (int j = i; !vis[j]; j = p[j])
internal.pb(j), vis[j] = 1;
if (SZ(internal) == 2) {
buk.insert(buk.end(), ALL(internal));
if (SZ(buk) == 4) break;
}
}
if (SZ(buk) < 4) return false;
t[ord[0]] = buk[0];
t[ord[1]] = buk[1];
t[ord[2]] = buk[2];
t[ord[3]] = buk[3];
run();
handle4();
return true;
};
auto handle33 = [&]() {
vector<int> vis(n);
vector<int> buk;
for (int i = 0; i < n; ++i) {
if (p[i] == i || vis[i]) continue;
vector<int> internal;
for (int j = i; !vis[j]; j = p[j])
internal.pb(j), vis[j] = 1;
if (SZ(internal) == 3) {
buk.insert(buk.end(), ALL(internal));
if (SZ(buk) == 6) break;
}
}
if (SZ(buk) < 6) return false;
t[ord[0]] = buk[0];
t[ord[1]] = buk[1];
t[ord[2]] = buk[2];
t[ord[3]] = buk[3];
run();
handle4();
return true;
};
int score = -1;
while (true) {
vector<int> vis(n);
vector<int> buk;
int odd = 0, two = 0, three = 0;
for (int i = 0; i < n; ++i) {
if (p[i] == i || vis[i]) continue;
vector<int> internal;
for (int j = i; !vis[j]; j = p[j])
internal.pb(j), vis[j] = 1;
if (m - 1 == e) {
buk.insert(buk.end(), ALL(internal));
}
else {
if (m == e && m == 4) {
if (SZ(internal) > 3) {
buk.insert(buk.end(), ALL(internal));
three += SZ(internal) / 3;
if (SZ(internal) % 3 == 2) ++two;
if (SZ(internal) % 3 == 1) ++odd;
}
if (SZ(internal) == 3) ++three;
if (SZ(internal) == 2) ++two;
}
else {
if (SZ(internal) > 2)
buk.insert(buk.end(), ALL(internal));
if (SZ(internal) & 1)
++odd;
}
}
}
if (score == -1) {
if (m == 3) score = cal() + odd;
else {
score = cal() + odd;
debug(score, two, three);
while (two + three >= 3 || (two + three == 2 && (two == 0 || three == 0))) {
score += two / 2, three += two / 2, two %= 2;
score += three / 2, two += three / 2, three = three % 2 + three / 2;
}
}
}
if (SZ(buk) < m) {
break;
}
for (int i = 0; i < m; ++i)
t[ord[i]] = buk[i];
run();
}
if (m == e && m == 4) {
while (handle22() || handle33() || handle6() || handle4());
}
if (m - 1 == e) return cal();
return score;
}
