#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;
}
vector<int> bfs(int s, int m, int e, vector<int> u, vector<int> v)
{
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]);
}
vector<char> vst(m);
vector<int> res;
queue<int> q;
q.push(s); vst[s] = true;
while(q.size()) {
int now = q.front(); q.pop();
res.push_back(now);
for(auto nxt : g[now]) {
if(vst[nxt] || q.size() >= 1) continue;
vst[nxt] = true;
q.push(nxt);
}
}
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);
}
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 task6(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);
}
vector<int> order = bfs(0, m, e, u, v);
auto BobAct = [&](vector<int> t) {
vector<int> tt(m);
for(int i = 0; i < m; i++) tt[order[i]] = t[i];
int i = Bob(tt);
swap(p[tt[u[i]]], p[tt[v[i]]]);
};
while(true) {
bool done = true;
auto cycs = decomp(p);
for(auto c : cycs) {
if(c.size() > m) {
vector<int> t(m);
for(int i = 0; i < m-1; i++) {
t[i] = c[i];
}
t[m-1] = c[m];
done = false;
BobAct(t);
} else if(c.size() == m) {
vector<int> t(m);
for(int i = 0; i < m; i++) {
t[i] = c[i];
}
done = false;
BobAct(t);
}
}
if(done) break;
}
while(true) {
bool done = true;
auto cycs = decomp(p);
vector<vector<int>> even, odd;
for(auto c : cycs) {
if(c.size() > m) {
vector<int> t(m);
for(int i = 0; i < m-1; i++) {
t[i] = c[i];
}
t[m-1] = c[m];
done = false;
BobAct(t);
} else if(c.size() == m) {
vector<int> t(m);
for(int i = 0; i < m; i++) {
t[i] = c[i];
}
done = false;
BobAct(t);
} else {
if(c.size()%2 == 0) even.push_back(c);
else odd.push_back(c);
}
}
sort(even.begin(), even.end(), [](vector<int>& a, vector<int>& b){return a.size() > b.size(); });
sort(odd.begin(), odd.end(), [](vector<int>& a, vector<int>& b){return a.size() > b.size(); });
if(m%2 == 0) {
vector<int> t;
for(int i = 0; i+1 < odd.size() && t.size() < m; i+=2) {
t.insert(t.end(), odd[i].begin(), odd[i].end());
t.insert(t.end(), odd[i+1].begin(), odd[i+1].end());
}
for(int i = 0; i < even.size() && t.size() < m; i++) {
t.insert(t.end(), even[i].begin(), even[i].end());
}
while(t.size() > m) t.pop_back();
if(t.size() >= m) {
done = false;
BobAct(t);
}
} else {
if(odd.size()) {
vector<int> t;
for(int i = 0; i < even.size() && t.size() + odd[0].size() < m; i++) {
t.insert(t.end(), even[i].begin(), even[i].end());
}
for(int i = 1; i+1 < odd.size() && t.size() + odd[0].size() < m; i+=2) {
t.insert(t.end(), odd[i].begin(), odd[i].end());
t.insert(t.end(), odd[i+1].begin(), odd[i+1].end());
}
t.insert(t.end(), odd[0].begin(), odd[0].end());
while(t.size() > m) t.pop_back();
if(t.size() >= m) {
done = false;
BobAct(t);
}
}
}
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 if(e == m) return task6(m, e, u, v, n, p);
else assert(0);
}
