#include "permgame.h"
#include <cstring>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 400;
int ev[N][2], eo[N], ww[N], qu[N], cnt;
char visited[N];
void move(vi uu, vi vv, vi &pp, vi ii) {
int h = Bob(ii);
int i = ii[uu[h]], j = ii[vv[h]], tmp;
tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
}
int Alice(int m, int e, vi uu, vi vv, int n, vi pp) {
memset(eo, 0, m * sizeof *eo);
int bad = 0;
for (int h = 0; h < e; h++) {
int u = uu[h], v = vv[h];
if (eo[u] == 2 || eo[v] == 2) {
bad = 1;
break;
}
ev[u][eo[u]++] = v, ev[v][eo[v]++] = u;
}
int k = 0;
for (int i = 0; i < n; i++)
if (pp[i] == i)
k++;
if (bad)
return k;
if (e == m - 1) {
int u = 0;
while (eo[u] == 2)
u++;
ww[cnt++] = u;
int v = ev[u][0];
while (1) {
ww[cnt++] = v;
if (eo[v] == 1)
break;
int w = u ^ ev[v][0] ^ ev[v][1];
u = v, v = w;
}
} else {
int u = 0, v = ev[u][0];
ww[cnt++] = u;
while (1) {
ww[cnt++] = v;
int w = u ^ ev[v][0] ^ ev[v][1];
if (w == 0)
break;
u = v, v = w;
}
}
if (e == m - 1) {
if (k > n - m)
return k;
vi ii(m);
while (1) {
memset(visited, 0, n * sizeof *visited);
int k = 0;
for (int i = 0; i < n && k < m; i++)
if (pp[i] != i && !visited[i])
while (!visited[i] && k < m)
ii[ww[k++]] = i, visited[i] = 1, i = pp[i];
if (k < m)
break;
move(uu, vv, pp, ii);
}
return m == 2 ? n : n - m + 1;
} else if (m == 3) {
memset(visited, 0, n * sizeof *visited);
int k = 0;
for (int i = 0; i < n; i++)
if (!visited[i]) {
int c = 0;
while (!visited[i])
c++, visited[i] = 1, i = pp[i];
if (c % 2 != 0)
k++;
}
vi ii(m);
while (1) {
memset(visited, 0, n * sizeof *visited);
int moved = 0;
for (int i = 0; i < n; i++)
if (pp[i] != i && !visited[i]) {
int c = 0;
while (!visited[i])
c++, visited[i] = 1, i = pp[i];
if (c % 2 != 0) {
ii[ww[0]] = i, ii[ww[1]] = pp[i], ii[ww[2]] = pp[pp[i]];
move(uu, vv, pp, ii);
moved = 1;
break;
}
}
if (!moved)
break;
}
return k;
} else if (m == 4) {
int ans = k > n - m ? k : (k == n - m ? n - m + 1 : n - m - 1);
vi ii(m);
while (1) {
int k = 0;
for (int i = 0; i < n; i++)
if (pp[i] != i)
k++;
if (k < m)
break;
if (k == m) {
memset(visited, 0, n * sizeof *visited);
k = 0;
for (int i = 0; i < n; i++)
if (pp[i] != i && !visited[i])
while (!visited[i])
ii[ww[k++]] = i, visited[i] = 1, i = pp[i];
move(uu, vv, pp, ii);
continue;
}
if (k == m + 1)
break;
memset(visited, 0, n * sizeof *visited);
k = 0;
for (int i = 0; i < n && k < m; i++)
if (pp[i] != i && !visited[i]) {
int c = 0;
while (!visited[i])
c++, visited[i] = 1, i = pp[i];
if (c < 4)
while (visited[i] == 1 && k < m)
ii[ww[k++]] = i, visited[i] = 2, i = pp[i];
}
if (k > 0) {
for (int i = 0; i < n && k < m; i++)
if (pp[i] != i && visited[i] == 1)
while (visited[i] == 1 && k < m)
ii[ww[k++]] = i, visited[i] = 2, i = pp[i];
move(uu, vv, pp, ii);
continue;
}
memset(visited, 0, n * sizeof *visited);
int moved = 0;
for (int i = 0; i < n; i++)
if (pp[i] != i && !visited[i]) {
int c = 0;
while (!visited[i])
qu[c++] = i, visited[i] = 1, i = pp[i];
if (c == 4) {
ii[ww[0]] = qu[0], ii[ww[1]] = qu[1], ii[ww[2]] = qu[2], ii[ww[3]] = qu[3];
move(uu, vv, pp, ii);
moved = 1;
break;
} else if (c == 6) {
ii[ww[0]] = qu[0], ii[ww[1]] = qu[1], ii[ww[2]] = qu[3], ii[ww[3]] = qu[5];
move(uu, vv, pp, ii);
moved = 1;
break;
} else if (c != 5) {
ii[ww[0]] = qu[0], ii[ww[1]] = qu[1], ii[ww[2]] = qu[2], ii[ww[3]] = qu[6];
move(uu, vv, pp, ii);
moved = 1;
break;
}
}
if (!moved)
break;
}
return ans;
}
return -1;
}
