#include <bits/stdc++.h>
#include "permgame.h"
using namespace std;
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
int cnt = 0;
for (int i = 0; i < n; i ++)
cnt += (p[i] == i);
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]);
}
for (int i = 0; i < m; i ++)
if (g[i].size() > 2)
return cnt;
bool vis[n] = {};
vector<int> order;
int ver = 0;
for (int i = 0; i < m; i ++)
if (g[ver].size() > g[i].size())
ver = i;
while (1){
order.push_back(ver);
vis[ver] = 1;
int nxt = g[ver][0];
if (vis[nxt] and g[ver].size() > 1) nxt = g[ver][1];
if (vis[nxt]) break;
ver = nxt;
}
int ind[n];
while (e + 1 == m){
vector<vector<int>> vec;
vector<int> cyc;
for (int i = 0; i < n; i ++)
ind[p[i]] = i;
memset(vis, 0, sizeof vis);
for (int i = 0; i < n; i ++){
if (vis[i]) continue;
cyc.clear();
int v = i;
while (1){
cyc.push_back(v);
vis[v] = 1;
v = p[v];
if (vis[v]) break;
}
vec.push_back(cyc);
}
int cur_ans = 0;
vector<int> tmp;
for (vector<int> cyc : vec){
if (cyc.size() == 1){
cur_ans++;
continue;
}
for (int x : cyc)
tmp.push_back(x);
}
if (tmp.size() < m) return cur_ans;
vector<int> t;
for (int i = 0; i < m; i ++)
t.push_back(tmp[order[i]]);
int e = Bob(t);
swap(p[t[u[e]]], p[t[v[e]]]);
}
while (1){
vector<vector<int>> vec;
vector<int> cyc;
for (int i = 0; i < n; i ++)
ind[p[i]] = i;
memset(vis, 0, sizeof vis);
for (int i = 0; i < n; i ++){
if (vis[i]) continue;
cyc.clear();
int v = i;
while (1){
cyc.push_back(v);
vis[v] = 1;
v = p[v];
if (vis[v]) break;
}
vec.push_back(cyc);
}
bool all_bad = 1;
int cur_ans = 0;
for (vector<int> cyc : vec){
cur_ans += (cyc.size() == 1);
if (cyc.size() > 1 and (cyc.size()) % (m - 1) == 1)
all_bad = 0;
}
if (all_bad){
int ind1 = -1, ind2 = -1;
for (int i = 0; i < vec.size(); i ++){
if (vec[i].size() % (m - 1) == 2 and ind1 == -1)
ind1 = i;
else if (vec[i].size() % (m - 1) == 2)
ind2 = i;
}
if (ind2 == -1) return cur_ans;
vector<int> tmp;
tmp.push_back(vec[ind1][0]);
tmp.push_back(vec[ind1][1]);
tmp.push_back(vec[ind2][0]);
tmp.push_back(vec[ind2][1]);
vector<int> t;
for (int i = 0; i < m; i ++)
t.push_back(tmp[order[i]]);
int e = Bob(t);
swap(p[t[u[e]]], p[t[v[e]]]);
continue;
}
for (vector<int> cyc : vec){
if (cyc.size() < m) continue;
if (cyc.size() % (m - 1) != 1) continue;
vector<int> t;
for (int i = 0; i < m; i ++)
t.push_back(cyc[order[i]]);
int e = Bob(t);
swap(p[t[u[e]]], p[t[v[e]]]);
break;
}
}
}
