#include "permgame.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;
vector<int>order;
void dfs(int st, vector<int>(g)[], bool vis[]){
order.push_back(st);
vis[st]=1;
for(int i : g[st]){
if(vis[i])
continue;
dfs(i,g,vis);
}
}
int score(vector<int> &p){
int n = p.size();
int ans = 0;
for(int i = 0;i<n;i++){
ans+=(p[i]==i);
}
return ans;
}
vector<vector<int>>cycles(vector<int> &p){
vector<vector<int>>ans;
int n = p.size();
bool vis[n];
fill(vis,vis+n,0);
for(int i = 0;i<n;i++){
vector<int>a;
int c = i;
while(!vis[c]){
a.push_back(c);
vis[c]=1;
c=p[c];
}
if(a.size()>=2&&a.size()%3!=0){
ans.push_back(a);
}
}
return ans;
}
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
order.clear();
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]);
}
int deg[n];
fill(deg,deg+n,0);
for(int i = 0;i<m;i++){
deg[i]=g[i].size();
}
if(*max_element(deg,deg+n)>=3){
return score(p);
}
//path or cycle exists now.
//one dfs for figuring out the path/cycle on the graph is required
bool vis[n];
fill(vis,vis+n,0);
dfs(0,g,vis);
if(e==m-1){
//path
int optimal = n-e;
if(e==1){
optimal=n;
}
if(score(p)>=optimal){
return score(p);
}
while(score(p)<optimal){
vector<vector<int>>cycs = cycles(p);
int i = 0;
vector<int>t(m);
for(vector<int>v:cycs){
for(int c : v){
if(i>=m){
break;
}
t[order[i]]=c;
i++;
}
}
int j = Bob(t);
swap(p[t[u[j]]],p[t[v[j]]]);
}
return optimal;
}
else{
//cycle
int odd = 0;
vector<vector<int>>cycs = cycles(p);
int c = 0;
for(vector<int>v:cycs){
if(v.size()%3==1)
odd++;
else{
c++;
}
}
odd+=c/2;
int optimal = score(p)+odd;
if(score(p)>=optimal){
return score(p);
}
while(score(p)<optimal){
vector<vector<int>>cycs = cycles(p);
vector<vector<int>>temp;
for(vector<int>v:cycs){
if(v.size()%3==1){
temp.push_back(v);
cycs=temp;
break;
}
}
vector<int>t(m);
int i=1;
t[order[0]]=cycs[cycs.size()-1][cycs[cycs.size()-1].size()-1];
for(vector<int>v:cycs){
for(int c : v){
if(i>=m){
break;
}
t[order[i]]=c;
i++;
}
}
assert(i>=m);
int j = Bob(t);
swap(p[t[u[j]]],p[t[v[j]]]);
}
return optimal;
}
return -1;
}
