#include <bits/stdc++.h>
using namespace std;
int Bob(vector<int> t);
const int NN = 410;
int MM;
vector<int> g[NN], ord, Uu, Vv;
bool used[NN];
int count_ones;
vector<vector<int>> cycles(const vector<int> &p) {
int n = (int) p.size();
vector<bool> used(n, false);
vector<vector<int>> res;
count_ones = 0;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
int t = i;
vector<int> cur;
do {
cur.push_back(t);
used[t] = true;
t = p[t];
} while (t != i);
if (cur.size() == 1)
count_ones++;
if (cur.size() != 1)
res.push_back(cur);
}
return res;
}
void dfs(int v) {
if (used[v]) return;
used[v] = true;
ord.push_back(v);
for (int u : g[v])
dfs(u);
}
void upd(vector<int> t, vector<int> &p) {
vector<int> val(MM);
for (int i = 0; i < MM; i++) val[ord[i]] = t[i];
int edge = Bob(val);
swap(p[val[Uu[edge]]], p[val[Vv[edge]]]);
}
void split(vector<int> t, vector<int> &p) {
vector<int> cur;
int k = (int) t.size() - MM;
cur.push_back(0);
for (int i = 0; i < MM / 2 - 1; i++)
if (cur.back() % (2 * k - 2) == 0)
cur.push_back(cur.back() + k);
else
cur.push_back(cur.back() + 1);
cur.push_back(cur.back() + 1);
cur.push_back(cur.back() - k);
for (int i = 0; i < MM / 2 - 2; i++)
if (cur.back() % (2 * k - 2) == 1)
cur.push_back(cur.back() - k);
else
cur.push_back(cur.back() - 1);
for (int i = 0; i < MM; i++)
cur[i] = t[cur[i]];
upd(cur, p);
}
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
MM = m;
Uu = u;
Vv = v;
if (m == 2) {
for (int i = 0; i < n; i++) {
int pos = -1;
for (int j = 0; j < n; j++)
if (p[j] == i) pos = j;
if (pos == i) continue;
Bob({i, pos});
swap(p[i], p[pos]);
}
return n;
}
int orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
if (orig >= n - m + 1) return orig;
for (int i = 0; i < e; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
int maxdeg = 0, mindeg = 2;
for (int i = 0; i < m; i++) {
maxdeg = max(maxdeg, (int) g[i].size());
mindeg = min(mindeg, (int) g[i].size());
}
if (maxdeg >= 3) return orig;
for (int i = 0; i < m; i++)
if ((int) g[i].size() == mindeg) {
dfs(i);
break;
}
if (mindeg <= 1 || (m % 2 == 0 && orig == n - m)) {
while (orig < n - m + 1) {
auto st = cycles(p);
vector<int> cur;
for (int i = 0; i < (int) st.size() && (int) cur.size() < m; i++)
for (int j = 0; j < (int) st[i].size() && (int) cur.size() < m; j++)
cur.push_back(st[i][j]);
upd(cur, p);
orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
}
return n - m + 1;
}
if (m % 2 == 1) {
auto st = cycles(p);
int opt = count_ones, sum = 0, k = 0;
for (int i = 0; i < (int) st.size(); i++)
if (st[i].size() % 2 == 1) opt++;
else sum += st[i].size();
sort(begin(st), end(st), [&](auto x, auto y) {
return x.size() > y.size();
});
for (int i = 0; i < (int) st.size() && sum < m; i++)
if ((int) st[i].size() % 2 == 1) {
k++;
sum += (int) st[i].size();
}
opt -= 2 * (k / 2);
while (orig < opt) {
vector<int> cur;
for (int i = 0; i < (int) st.size(); i++) {
if ((int) st[i].size() % 2 == 0) continue;
if ((int) st[i].size() < m) continue;
if ((int) st[i].size() == m) cur = st[i];
else {
for (int j = 0; j < m; j += 2)
cur.push_back(st[i][j]);
for (int j = m - 2; j > 0; j -= 2)
cur.push_back(st[i][j]);
}
upd(cur, p);
goto fin;
}
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() % 2 == 0)
for (int j = 0; j < (int) st[i].size(); j++)
cur.push_back(st[i][j]);
while ((int) cur.size() > m - 1)
cur.pop_back();
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() % 2 == 1)
for (int j = 0; j < (int) st[i].size(); j++)
cur.push_back(st[i][j]);
while ((int) cur.size() > m)
cur.pop_back();
upd(cur, p);
fin:;
orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
st = cycles(p);
}
return opt;
}
int opt = n - m - 1;
auto st = cycles(p);
while (orig < opt) {
int all = 0;
vector<int> cur;
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() == m) {
upd(st[i], p);
goto fin1;
}
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() >= m + 2) {
split(st[i], p);
goto fin1;
}
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() > 2)
all += (int) st[i].size();
if (all < m + 2)
break;
sort(begin(st), end(st), [&](auto x, auto y) {
return x.size() < y.size();
});
for (int i = 0; i < (int) st.size() && (int) cur.size() < m; i++)
if (st[i].size() > 2)
for (int j = 0; j < (int) st[i].size() && (int) cur.size() < m; j++)
cur.push_back(st[i][j]);
upd(cur, p);
fin1:;
orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
st = cycles(p);
}
orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
st = cycles(p);
while (orig < opt) {
vector<int> cur;
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() == m) {
upd(st[i], p);
goto fin2;
}
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() >= 2 * m - 1) {
split(st[i], p);
goto fin2;
}
if ((int) st.size() == 1)
break;
sort(begin(st), end(st), [&](auto x, auto y) {
return x.size() > y.size();
});
for (int i = 0; i < (int) st.size(); i++) {
for (int j = 0; j < (int) st[i].size(); j++)
cur.push_back(st[i][j]);
if (cur.size() >= m && st[i].size() == cur.size()) {
while (cur.size() >= m)
cur.pop_back();
}
}
upd(cur, p);
fin2:;
orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
st = cycles(p);
}
orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
st = cycles(p);
while (orig < opt) {
vector<int> cur;
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() == m) {
upd(st[i], p);
goto fin3;
}
for (int i = 0; i < (int) st.size(); i++)
if ((int) st[i].size() >= m + 2) {
split(st[i], p);
goto fin3;
}
sort(begin(st), end(st), [&](auto x, auto y) {
return x.size() < y.size();
});
for (int i = 0; i < (int) st.size() && (int) cur.size() < m; i++)
for (int j = 0; j < (int) st[i].size() && (int) cur.size() < m; j++)
cur.push_back(st[i][j]);
upd(cur, p);
fin3:;
orig = 0;
for (int i = 0; i < n; i++)
if (p[i] == i)
orig++;
st = cycles(p);
}
return opt;
}
