/* https://codeforces.com/blog/entry/142848?#comment-1276236 (errorgorn) */
#include "permgame.h"
#include <cstring>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 400, M = N;
int min(int a, int b) { return a < b ? a : b; }
int uu[M], vv[M], ev[M][2], eo[M], ww[M], m;
int pp[N], rr[N], cc[N], ii[N], jj[N], n, k;
int score() {
int s = 0;
for (int i = 0; i < n; i++)
if (pp[i] == i)
s++;
return s;
}
char visited[N]; int kk[N + 1], rr_[N];
void decompose() {
memset(visited, 0, n * sizeof *visited), memset(kk, 0, (n + 1) * sizeof *kk);
k = 0;
for (int r = 0; r < n; r++)
if (!visited[r]) {
int c = 0;
while (!visited[r])
c++, visited[r] = 1, r = pp[r];
cc[r] = c, rr_[k++] = r;
kk[c - 1]++;
}
for (int c = n - 1; c >= 0; c--)
kk[c] += kk[c + 1];
for (int h = 0; h < k; h++) {
int r = rr_[h], c = cc[r];
rr[kk[c]++] = r;
}
}
void get_cycle(int *ii, int r) {
int i = r, cnt = 0;
do
ii[cnt++] = i;
while ((i = pp[i]) != r);
}
vi ii_;
void move() {
for (int h = 0; h < m; h++)
ii_[ww[h]] = ii[h];
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_) {
n = n_, m = m_;
for (int h = 0; h < m; h++)
uu[h] = uu_[h], vv[h] = vv_[h];
for (int i = 0; i < n; i++)
pp[i] = pp_[i];
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 s_ = score();
if (bad || s_ >= n - m + 1)
return s_;
if (e == m - 1) {
int u = 0;
while (eo[u] > 1)
u++;
int v = ev[u][0];
int cnt = 0;
ww[cnt++] = u;
while (eo[v] > 1) {
ww[cnt++] = v;
int w = u ^ ev[v][0] ^ ev[v][1];
u = v, v = w;
}
ww[cnt++] = v;
s_ = m == 2 ? n : n - m + 1;
} else {
int u = 0, v = ev[u][0];
int cnt = 0;
ww[cnt++] = u;
while (v != u) {
ww[cnt++] = v;
int w = u ^ ev[v][0] ^ ev[v][1];
u = v, v = w;
}
if (m % 2 == 0)
s_ = s_ == n - m ? n - m + 1 : n - m - 1;
else {
decompose();
int c = 0, k1 = 0, l1 = 0;
for (int h = 0; h < k; h++) {
int r = rr[h];
if (cc[r] % 2 == 0)
c += cc[r];
else
k1++;
}
for (int h = 0; h < k && c < m; h++) {
int r = rr[h];
if (cc[r] % 2 != 0)
c += cc[r], l1++;
}
s_ = k1 - l1 / 2 * 2;
}
}
ii_.resize(m);
int s;
while ((s = score()) < s_) {
decompose();
if (e == m - 1 || s == n - m) {
int cnt = 0;
for (int h = 0; h < k; h++) {
int r = rr[h];
get_cycle(ii + cnt, r), cnt += cc[r];
}
} else if (m % 2 != 0) {
int r_ = -1;
for (int h = 0; h < k; h++) {
int r = rr[h];
if (cc[r] % 2 != 0) {
r_ = r;
break;
}
}
if (cc[r_] == m)
get_cycle(ii, r_);
else if (cc[r_] > m) {
get_cycle(jj, r_);
int cnt = 0;
for (int h = 0; h < m; h += 2)
ii[cnt++] = jj[h];
for (int h = m - 2; h >= 1; h -= 2)
ii[cnt++] = jj[h];
} else {
get_cycle(ii, r_);
int cnt = cc[r_];
for (int h = 0; h < k; h++) {
int r = rr[h];
if (cc[r] % 2 == 0)
get_cycle(ii + cnt, r), cnt += cc[r];
}
for (int h = 0; h < k; h++) {
int r = rr[h];
if (cc[r] % 2 != 0 && r != r_)
get_cycle(ii + cnt, r), cnt += cc[r];
}
}
} else {
int r_ = rr[0];
for (int h = 0; h < k; h++) {
int r = rr[h];
if (cc[r] == m || cc[r] > m + 1) {
r_ = r;
break;
}
}
if (cc[r_] == m)
get_cycle(ii, r_);
else if (cc[r_] > m + 1) {
get_cycle(jj, r_);
int d = cc[r_] - m, md = (d - 1) * 2;
int cnt = 0, h = 0;
ii[cnt++] = jj[0];
while (cnt < m / 2) {
h += h % md == 0 ? d : 1;
ii[cnt++] = jj[h];
}
h++;
ii[cnt++] = jj[h];
h -= d;
ii[cnt++] = jj[h];
while (cnt < m) {
h -= h % md == 1 ? d : 1;
ii[cnt++] = jj[h];
}
} else {
get_cycle(ii, r_);
int cnt = min(cc[r_], m - 1);
for (int h = 0; h < k; h++) {
int r = rr[h];
if (r != r_)
get_cycle(ii + cnt, r), cnt += cc[r];
}
}
}
move();
}
return s_;
}
