#include "permgame.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ' ' << x << endl;
#define ll long long
#define inf (ll) 1e17
using namespace std;
// vector<int> t={ind[i],i};
// int j = Bob(t);
// std::swap(p[t[u[j]]], p[t[v[j]]]);
vector<bool> vis;
vector<int> ind;
void dfs(ll node, ll par, vector<vector<ll>>& adj)
{
if(vis[node]) return;
vis[node]=true;
ind.push_back(node);
for (auto &&e : adj[node])
{
if(e!=par)
{
dfs(e,node,adj);
}
}
}
void combine(vector<int>& p, vector<int>& v1, vector<int>& v2, vector<int>& u, vector<int>& v)
{
vector<int> t(4);
t[ind[0]]=v1[0];
t[ind[1]]=v2[0];
t[ind[2]]=v1[1];
t[ind[3]]=v2[1];
int j = Bob(t);
std::swap(p[t[u[j]]], p[t[v[j]]]);
}
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
vector<vector<ll>> adj(m);
vis.assign(n,0);
ll curans=0;
for (int i=0;i<n;i++)
{
curans+=p[i]==i;
}
for (int i=0;i<e;i++)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
for (int i=0;i<m;i++)
{
if(adj[i].size() > 2)
{
return curans;
}
}
dfs(0,0,adj);
vis.assign(n,0);
vector<vector<int>> grps;
for (int i=0;i<n;i++)
{
if(p[i]!=i && !vis[i])
{
vector<int> g;
for (int j=i;true;j=p[j])
{
vis[j]=true;
g.push_back(j);
if(p[j]==i) break;
}
grps.push_back({g[0],g[1]});
}
}
for (int i=0;i<grps.size()-1;i++)
{
combine(p,grps[i],grps[i+1],u,v);
}
for (int i=0;i<n;i++)
{
if(p[i]!=i)
{
vector<int> g;
for (int j=i;true;j=p[j])
{
vis[j]=true;
g.push_back(j);
if(p[j]==i) break;
}
while(g.size() > 4)
{
vector<int> t(4);
t[ind[0]]=g[0];
t[ind[1]]=g[1];
t[ind[2]]=g[3];
t[ind[3]]=g[4];
int j = Bob(t);
std::swap(p[t[u[j]]], p[t[v[j]]]);
g.clear();
for (int j=i;true;j=p[j])
{
g.push_back(j);
if(p[j]==i) break;
}
}
break;
}
}
grps.clear();
vis.assign(n,0);
for (int i=0;i<n;i++)
{
if(p[i]!=i && !vis[i])
{
vector<int> g;
for (int j=i;true;j=p[j])
{
vis[j]=true;
g.push_back(j);
if(p[j]==i) break;
}
if(g.size()==4)
{
vector<int> t(4);
t[ind[0]]=g[0];
t[ind[1]]=g[1];
t[ind[2]]=g[2];
t[ind[3]]=g[3];
int j = Bob(t);
std::swap(p[t[u[j]]], p[t[v[j]]]);
g.clear();
for (int j=i;true;j=p[j])
{
g.push_back(j);
if(p[j]==i) break;
}
}
else if(g.size()==2)
{
grps.push_back(g);
}
}
}
for (int i=1;i<grps.size();i+=2)
{
combine(p,grps[i],grps[i-1],u,v);
}
vis.assign(n,0);
for (int i=0;i<n;i++)
{
if(p[i]!=i && !vis[i])
{
vector<int> g;
for (int j=i;true;j=p[j])
{
vis[j]=true;
g.push_back(j);
if(p[j]==i) break;
}
if(g.size()==4)
{
vector<int> t(4);
t[ind[0]]=g[0];
t[ind[1]]=g[1];
t[ind[2]]=g[2];
t[ind[3]]=g[3];
int j = Bob(t);
std::swap(p[t[u[j]]], p[t[v[j]]]);
g.clear();
for (int j=i;true;j=p[j])
{
g.push_back(j);
if(p[j]==i) break;
}
}
}
}
ll cnt=0;
for (int i=0;i<n;i++)
{
cnt+=p[i]==i;
}
return cnt;
}
