#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];
}
if(comp.size() >= 2)
res.push_back(comp);
}
return res;
}
vector<int> get_path(vector<vector<int>>& g)
{
int st = -1;
for(int i = 0; i < g.size(); 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);
return path;
}
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);
}
auto path = get_path(g);
while(true) {
auto cycs = decomp(p);
vector<int> t(m);
int q = 0;
for(auto c : cycs) {
for(auto i : c) {
if(q < m) t[q++] = i;
}
}
if(q == m) {
int i = Bob(t);
swap(p[t[u[i]]], p[t[v[i]]]);
} else break;
}
return get_score(p);
}
int task4(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
while(true) {
auto cycs = decomp(p);
bool done = true;
for(auto c : cycs) {
if(c.size()%2 == 0) continue;
done = false;
vector<int> t(m);
t[0] = c[0];
t[1] = c[1];
t[2] = c[2];
int i = Bob(t);
swap(p[t[u[i]]], p[t[v[i]]]);
}
if(done) break;
}
return get_score(p);
}
int task5(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
vector<int> deg(m);
for(int i = 0; i < e; i++) deg[u[i]]++, deg[v[i]]++;
for(int i = 0; i < m; i++) {
if(deg[i] > 2) return get_score(p);
}
auto BobAct = [&](vector<int> t) {
int i = Bob(t);
swap(p[t[u[i]]], p[t[v[i]]]);
};
while(true) {
auto cycs = decomp(p);
bool done = true;
int u2, v2, u3, v3;
u2 = v2 = u3 = v3 = -1;
for(auto c : cycs) {
if(c.size() > 4) {
done = false;
BobAct({c[0], c[1], c[2], c[4]});
} else if(c.size() == 4) {
done = false;
BobAct({c[0], c[1], c[2], c[3]});
} else if(c.size() == 3) {
if(u3 < 0) {
u3 = c[0];
v3 = c[1];
} else {
done = false;
BobAct({u3, v3, c[0], c[1]});
u3 = v3 = -1;
}
} else if(c.size() == 2) {
if(u2 < 0) {
u2 = c[0];
v2 = c[1];
} else {
done = false;
BobAct({u2, v2, c[0], c[1]});
u2 = v2 = -1;
}
} else assert(0);
}
if(done) break;
}
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 if(e == 3 && m == 3) return task4(m, e, u, v, n, p);
else if(e == 4 && m == 4) return task5(m, e, u, v, n, p);
else assert(0);
}
