#include "permgame.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
vector<vector<int>> neigh(m);
for (int i = 0; i < e; i++)
{
neigh[u[i]].push_back(v[i]);
neigh[v[i]].push_back(u[i]);
}
int sc=0;
for (int i = 0; i < sz(p); i++)
{
sc+=(p[i]==i);
}
vector<int> cnt(m);
for (int i = 0; i < e; i++) { cnt[u[i]]++; cnt[v[i]]++; }
int st=0;
for (int i = 0; i < m; i++)
{
if(cnt[i]==1) {st=i; break; }
}
vector<int> tree;
int pr=-1;
while(sz(tree)<m){
tree.push_back(st);
bool br=false;
for (auto ne : neigh[st])
{
if(pr==ne) continue;
pr=st;
st=ne;
br=true;
break;
}
if(!br) break;
}
if(sz(tree)!=m) return sc;
bool b=true;
while(b){
b=false;
for (int i = 0; i < n; i++)
{
int x=i;
vector<int> visited(n,0);
vector<int> q;
while(!visited[x]&&sz(q)<m){
visited[x]=true;
q.push_back(x);
x=p[x];
}
if(sz(q)==m){
vector<int> t(m);
for (int i = 0; i < m; i++)
{
t[tree[i]]=q[i];
}
int j=Bob(t);
swap(p[t[u[j]]],p[t[v[j]]]);
b=true;
break;
}
}
}
sc=0;
for (int i = 0; i < n; i++) sc+=(p[i]==i);
return sc;
}
