#if !defined (EVAL) && !defined (ONLINE_JUDGE)
#include "grader.cpp"
#endif
#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
int get_score(vector<int> p)
{
int score = 0;
for(int i = 0; i < p.size(); i++) {
if(p[i] == i) score++;
}
return score;
}
vector<vector<int>> decomp(vector<int> p)
{
int n = p.size();
vector<char> vis(n);
vector<vector<int>> res;
for(int i = 0; i < n; i++) {
if(vis[i]) continue;
int j = i;
vector<int> comp;
while(!vis[j]) {
comp.push_back(j);
vis[j] = true;
j = p[j];
}
res.push_back(comp);
}
return res;
}
int task1(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
while(true) {
int j = -1;
for(int i = 0; i < n; i++) {
if(p[i] != i) j = i;
}
if(j < 0) break;
vector<int> t = {j, p[j]};
Bob(t);
swap(p[j], p[p[j]]);
}
return n;
}
int task2(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
return get_score(p);
}
int task3(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
vector<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++) {
// the graph is not path
if(g[i].size() > 2) return get_score(p);
}
int st = -1;
for(int i = 0; i < m; i++) {
if(g[i].size() == 1) {
st = i;
}
}
assert(st != -1);
vector<int> path = {st};
int i = g[st][0];
int j = st;
while(g[i].size() > 1) {
path.push_back(i);
int oldi = i;
i = g[i][0] + g[i][1] - j;
j = oldi;
}
path.push_back(i);
auto cycs = decomp(p);
bool done = true;
for(auto& cyc : cycs) {
if(cyc.size() == m) {
vector<int> t(m);
for(int i = 0; i < m; i++) {
t[path[i]] = cyc[i];
}
int i = Bob(t);
swap(p[u[i]], p[v[i]]);
}
}
return get_score(p);
}
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
if(m == 2) return task1(m, e, u, v, n, p);
else if(e > m) return task2(m, e, u, v, n, p);
else if(e == m-1) return task3(m, e, u, v, n, p);
else assert(0);
}
