#include "permgame.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int AliceL(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
vector<vector<int>> adjList(m);
vector<int> deg(m, 0);
for(int i = 0; i < e; i++){
adjList[u[i]].push_back(v[i]);
adjList[v[i]].push_back(u[i]);
deg[u[i]]++;
deg[v[i]]++;
}
// cout << "got degree\n";
bool isLine = true;
int end = 0;
for(int i = 0; i < m; i++){
if(deg[i] > 2) isLine = false;
if(deg[i] == 1) end = i;
}
// cout << "confirmed line " << end << '\n';
vector<int> line;
if(isLine){
line.push_back(end);
int prev = -1;
do{
int next = end;
for(const int &x : adjList[end]){
if(x != prev) next = x;
}
line.push_back(next);
prev = end;
end = next;
}while(deg[end] > 1);
}
// for(int i = 0; i < line.size(); i++){
// cout << line[i] << ' ';
// }
// cout << '\n';
// assert(line.size() == m);
// cout << "built line \n";
// cout << "hi\n";
while(true && isLine){
// cout << "in loop\n";
vector<bool> found(n, false);
vector<vector<int>> cycles;
int cycleTotal = 0;
for(int i = 0; i < n; i++){
// cout << "checking: " << i << '\n';
if(found[i]) continue;
found[i] = true;
if(i == p[i]) continue;
vector<int> cycle;
cycle.push_back(i);
int index = i;
while(p[index] != i){
index = p[index];
cycle.push_back(index);
found[index] = true;
}
// cout << "found cycle: ";
// for(const auto &x : cycle) cout << x << ", ";
// cout << '\n';
cycleTotal += cycle.size();
cycles.push_back(cycle);
}
// cout << "cycles: ";
// for(int i = 0; i < cycles.size(); i++) cout << cycles[i].size() << ' ';
// cout << '\n';
if(cycleTotal < line.size()) break;
sort(cycles.begin(), cycles.end(), [](const vector<int> &a, const vector<int> &b){
return a.size() > b.size();
});
vector<int> t(line.size());
// cout << "t: ";
int cycleI = 0;
int cycleO = 0;
for(int i = 0; i < line.size(); i++){
if(i - cycleO >= cycles[cycleI].size()){
cycleO += cycles[cycleI].size();
cycleI++;
}
t[line[i]] = cycles[cycleI][i-cycleO];
// cout << t[i] << ' ';
}
// cout << '\n';
int j = Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
}
int score = 0;
for(int i = 0; i < n; i++){
if(i == p[i]) score++;
}
return score;
}
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
assert(m == 4);
vector<vector<int>> adjList(m);
vector<int> deg(m, 0);
for(int i = 0; i < e; i++){
adjList[u[i]].push_back(v[i]);
adjList[v[i]].push_back(u[i]);
deg[u[i]]++;
deg[v[i]]++;
}
// cout << "got degree\n";
bool isLoop = true;
for(int i = 0; i < m; i++){
if(deg[i] > 2) isLoop = false;
}
// cout << "confirmed line " << end << '\n';
vector<int> line;
if(isLoop){
int end = 0;
line.push_back(end);
int prev = -1;
while(true){
int next = end;
for(const int &x : adjList[end]){
if(x != prev) next = x;
}
if(next == 0) break;
line.push_back(next);
prev = end;
end = next;
}
}
// cout << "line: ";
// for(int i = 0; i < line.size(); i++) cout << line[i] << ' ';
// cout << '\n';
while(true && isLoop){
assert(line.size() == 4);
bool foundCycle = false;
vector<bool> found(n, false);
for(int i = 0; i < n && !foundCycle; i++){
// cout << "checking: " << i << '\n';
if(found[i]) continue;
found[i] = true;
if(i == p[i]) continue;
vector<int> cycle;
cycle.push_back(i);
int index = i;
while(p[index] != i){
index = p[index];
cycle.push_back(index);
found[index] = true;
}
// cout << "found cycle: ";
// for(const auto &x : cycle) cout << x << ", ";
// cout << '\n';
if(cycle.size() < 4) continue;
foundCycle = true;
vector<int> t(m);
if(cycle.size() % 2 == 1 || cycle.size() == 4){
for(int i = 0; i < line.size(); i++){
t[line[i]] = cycle[i];
}
}else{
assert(cycle.size() >= 6);
for(int i = 0; i < line.size()-1; i++){
t[line[i]] = cycle[i];
}
t[line[line.size()-1]] = cycle[4];
}
int j = Bob(t);
swap(p[t[u[j]]], p[t[v[j]]]);
}
if(!foundCycle) break;
}
int score = 0;
for(int i = 0; i < n; i++){
if(i == p[i]) score++;
}
return score;
}
