#include "permgame.h"
#include <bitset>
#include <vector>
#include <utility>
using namespace std;
#define sz(v) ((int)((v).size()))
#define _PERMGAME_SIGNATURE_ int m, int e, vector<int> u, vector<int> v, int n, vector<int> p
#define _PERMGAME_REF_SIGNATURE_ int m, int e, vector<int> &u, vector<int> &v, int n, vector<int> &p
#define params m, e, u, v, n, p
#define pb push_back
void _bob(vector<int> &mx, _PERMGAME_REF_SIGNATURE_) {
int j = Bob(mx);
int a = u[j], b = v[j];
swap(p[mx[a]], p[mx[b]]);
}
int _count_score(_PERMGAME_REF_SIGNATURE_) {
int ans = 0;
for (int i=0; i<n; ++i) if (p[i] == i) ++ans;
return ans;
}
int subtask1(_PERMGAME_REF_SIGNATURE_) {
vector<int> mx(m);
while (true) {
int broken;
for (broken=0; broken<n; ++broken) if (p[broken] != broken) break;
if (broken == n) break;
mx[0] = broken; mx[1] = p[broken]; _bob(mx, params);
}
return n;
}
int subtask2(_PERMGAME_REF_SIGNATURE_) { return _count_score(params); }
vector<vector<int>> _get_nonI_cycs(_PERMGAME_REF_SIGNATURE_) {
static bitset<401> chk; chk.reset();
vector<vector<int>> cycs;
for (int ci=0; ci<n; ++ci) if (!chk[ci]) {
if (p[ci] == ci) continue; // nonI part
cycs.emplace_back();
for (int x=ci;;) {
cycs.back().pb(x); chk.set(x);
x = p[x];
if (chk[x]) break;
}
}
return cycs;
}
int subtask3(_PERMGAME_REF_SIGNATURE_) {
vector<int> deg(m);
vector<int> es(m);
vector<int> ends;
for (int i=0; i<e; ++i) { ++deg[u[i]]; ++deg[v[i]]; es[u[i]] += v[i]; es[v[i]] += u[i]; }
for (int i=0; i<m; ++i) {
if (deg[i] > 2) return _count_score(params);
else if (deg[i] == 1) ends.pb(i);
}
vector<int> line;
for (int i=ends[0];;) {
line.pb(i);
if (i == ends[1]) break;
int j = es[i];
es[j] -= i; i = j;
}
vector<int> mx(m);
while (true) {
auto cycs = _get_nonI_cycs(params);
int sz_sum = 0;
for (auto &c: cycs) sz_sum += sz(c);
if (sz_sum < sz(line)) break;
{ int mc = 0; for (auto &c: cycs) for (int x: c) {
mx[line[mc++]] = x;
if (mc == sz(line)) goto hehe;
} }
hehe:
_bob(mx, params);
}
return _count_score(params);
}
vector<int> mcycle;
void _find_mgraph_cycle(_PERMGAME_REF_SIGNATURE_) {
vector<int> deg(m), es(m);
for (int i=0; i<e; ++i) {
++deg[u[i]], ++deg[v[i]];
es[u[i]] += v[i];
es[v[i]] += u[i];
}
for (int i=0; i<m; ++i) if (deg[i] != 2) return;
mcycle.clear();
es[u[0]] -= v[0];
for (int x=u[0];;) {
mcycle.pb(x);
if (sz(mcycle) == m) break;
int y=es[x]; es[y]-=x; x = y;
}
}
int subtask4(_PERMGAME_REF_SIGNATURE_) {
int expected_answer = 0;
{
for (auto &c: _get_nonI_cycs(params)) {
if (sz(c) >= 3 && sz(c)%2 == 1) {
++expected_answer;
}
}
expected_answer += _count_score(params);
}
vector<int> mx(m);
while (true) {
auto cycs = _get_nonI_cycs(params);
bool interesting = false;
for (auto &c: cycs) if (sz(c) >= 3) {
for (int i=0; i<m; ++i) {
mx[mcycle[i]] = c[i];
}
_bob(mx, params);
interesting = true;
break;
}
if (!interesting) break;
}
return expected_answer;
}
int subtask5(_PERMGAME_REF_SIGNATURE_) {
int expected_answer = _count_score(params);
{
int cnt2 = 0, cnt3 = 0;
for (auto &c: _get_nonI_cycs(params)) {
switch (sz(c)%3) {
case 1: {
expected_answer++;
int q = (sz(c)-1)/3;
cnt2 += (q-1); expected_answer += (q-1); ++cnt3;
} break;
case 2: {
++cnt2; cnt3 += (sz(c) - 2) / 3;
} break;
case 0: {
int q = sz(c)/3;
cnt2 += (q-1); expected_answer += (q-1); ++cnt3;
} break;
}
}
// if we jumble up all 3s...
if (cnt3) { cnt2 += cnt3-1; expected_answer += cnt3-1; }
// now make max use of 2s...
if (cnt2 >= 4) { expected_answer += cnt2/2 - 1; }
}
vector<int> mx(m);
vector<int> head2, head3;
while (_count_score(params) < expected_answer) {
auto cycs = _get_nonI_cycs(params);
bool interesting = false;
head2.clear(); head3.clear();
for (auto &c: cycs) {
if (sz(c) >= 4) {
for (int i=0; i<m; ++i) {
mx[mcycle[i]] = c[i];
}
_bob(mx, params);
interesting = true;
} else if (sz(c) == 2) head2.pb(c[0]);
else if (sz(c) == 3) head3.pb(c[0]);
}
if (interesting) continue;
if (sz(head3) >= 2) {
if (sz(head3) >= 4) {
for (int i=0; i<m; ++i) mx[mcycle[i]] = head3[i];
_bob(mx, params);
continue;
}
if (sz(head3) == 3) {
mx[mcycle[0]] = head3[0];
mx[mcycle[1]] = p[head3[0]];
mx[mcycle[2]] = head3[1];
mx[mcycle[3]] = head3[2];
} else {
mx[mcycle[0]] = head3[0];
mx[mcycle[1]] = p[head3[0]];
mx[mcycle[2]] = p[p[head3[0]]];
mx[mcycle[3]] = head3[1];
}
_bob(mx, params); continue;
}
if (sz(head2) >= 2) {
mx[mcycle[0]] = head2[0];
mx[mcycle[1]] = p[head2[0]];
mx[mcycle[2]] = head2[1];
mx[mcycle[3]] = p[head2[1]];
_bob(mx, params); continue;
}
break;
}
return expected_answer;
}
int Alice(_PERMGAME_SIGNATURE_) {
if (m == 2) return subtask1(params);
if (e > m) return subtask2(params);
if (e == m-1) return subtask3(params);
// from now on, e == m.
_find_mgraph_cycle(params);
if (mcycle.empty()) return _count_score(params);
if (m == 3) return subtask4(params);
if (m == 4) return subtask5(params);
return 42;
}
