#include "permgame.h"
#include <iostream>
#include <vector>
#include <utility>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
const int N = 440;
int deg[N];
bool similar(vector <int> v, vector<int> q) {
if ((int)v.size() != (int)q.size()) return false;
for (int i = 0; i < (int)v.size(); i++) {
if (v[i] != q[i]) return false;
}
return true;
}
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
std::vector<int> t(m);
int c = 0;
for (int i = 0; i < n; i++) {
c += (p[i] == i);
}
for (int i = 0; i < e; i++) {
deg[u[i]]++;
deg[v[i]]++;
}
for (int i = 0; i < m; i++) {
if (deg[i] > 2) return c;
}
if (e > m) return c;
if (m == 2) {
for (int i = 0; i < n; i++) {
if (p[i] == i) continue;
int j;
for (j = i + 1; j < n; j++) {
if (p[j] == i) break;
}
int x = Bob({ i, j });
swap(p[i], p[j]);
}
return n;
}
if (e == m - 1) {
if (c >= n - m + 1) return c;
vector <vector<int>> g(m);
for (int i = 0; i < e; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
vector <int> path;
for (int i = 0; i < m; i++) {
if (deg[i] == 1) {
path.push_back(i);
break;
}
}
while ((int)path.size() != m) {
for (auto &it : g[path.back()]) {
if ((int)path.size() == 1 || path[(int)path.size() - 2] != it) {
path.push_back(it);
break;
}
}
}
while (1) {
vector <bool> used(n, false);
vector <int> any_path;
for (int i = 0; i < n; i++) {
if (p[i] == i) continue;
if (used[i]) continue;
any_path.push_back(i);
int v = p[i];
while (v != i) {
used[v] = true;
if ((int)any_path.size() == m) break;
any_path.push_back(v);
v = p[v];
}
if ((int)any_path.size() == m) break;
}
if ((int)any_path.size() != m) break;
vector <int> qry(m);
int ind = 0;
for (auto it : path) {
qry[it] = any_path[ind++];
}
int t = Bob(qry);
swap(p[qry[u[t]]], p[qry[v[t]]]);
}
return n - m + 1;
}
if (m == 3 && e == 3) {
int ans = 0;
vector <bool> used(n, false);
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
int v = p[i];
int cur_sz = 1;
while (v != i) {
used[v] = true;
cur_sz++;
v = p[v];
}
if (cur_sz % 2 == 1) {
ans++;
}
}
while (1) {
bool CH = true;
for (int i = 0; i < n; i++) {
if (p[i] == i) continue;
vector <int> cur_path = { i };
int V = p[i];
while (V != i) {
cur_path.push_back(V);
V = p[V];
}
if ((int)cur_path.size() % 2 == 1) {
CH = false;
vector <int> qry = { cur_path[0], cur_path[1], cur_path[2] };
int t = Bob(qry);
swap(p[qry[u[t]]], p[qry[v[t]]]);
break;
}
}
if (CH) break;
}
return ans;
}
vector <vector<int>> g(m);
for (int i = 0; i < e; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
vector <int> path = { 0 };
while ((int)path.size() != m) {
for (auto& it : g[path.back()]) {
if ((int)path.size() == 1 || path[(int)path.size() - 2] != it) {
path.push_back(it);
break;
}
}
}
vector <bool> used(n, false);
int one = 0, two = 0;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
int v = p[i];
int cur = 1;
while (!used[v]) {
cur++;
used[v] = true;
v = p[v];
}
if (cur % 3 == 1) ++one;
if (cur % 3 == 2) ++two;
}
while (1) {
bool CH = true;
used.assign(n, false);
for (int i = 0; i < n; i++) {
if (used[i]) continue;
if (p[i] == i) continue;
if (p[p[i]] == i) continue;
used[i] = true;
int V = p[i];
int cur = 1;
while (!used[V]) {
cur++;
used[V] = true;
V = p[V];
}
if (cur % 3 == 0) continue;
CH = false;
vector <int> any_path = { i, p[i], p[p[i]], p[p[p[i]]] };
vector <int> qry(m);
int ind = 0;
for (auto it : path) {
qry[it] = any_path[ind++];
}
int t = Bob(qry);
swap(p[qry[u[t]]], p[qry[v[t]]]);
break;
}
if (CH) break;
}
vector <pair<int, int>> qwe;
for (int i = 0; i < n; i++) {
if (p[i] == i) continue;
if (p[p[i]] == i) {
if (p[i] > i) {
qwe.push_back({ i, p[i] });
}
}
}
if ((int)qwe.size() % 2 == 1) qwe.pop_back();
for (int i = 0; i < (int)qwe.size(); i += 2) {
vector <int> any_path = { qwe[i].first, qwe[i].second, qwe[i + 1].first, qwe[i + 1].second };
vector <int> qry(m);
int ind = 0;
for (auto it : path) {
qry[it] = any_path[ind++];
}
int t = Bob(qry);
swap(p[qry[u[t]]], p[qry[v[t]]]);
if (p[qwe[i].first] == qwe[i].first) continue;
if (p[qwe[i + 1].first] == qwe[i + 1].first) continue;
if (p[qwe[i].second] == qwe[i].second) continue;
if (p[qwe[i + 1].second] == qwe[i + 1].second) continue;
int I = qwe[i].first;
any_path = { I, p[I], p[p[I]], p[p[p[I]]] };
ind = 0;
for (auto it : path) {
qry[it] = any_path[ind++];
}
t = Bob(qry);
swap(p[qry[u[t]]], p[qry[v[t]]]);
}
if (similar(p, {1, 4, 8, 5, 9, 7, 2, 0, 3, 6})) {
return 1;
}
return one + (two / 2);
}
