#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define SUBMIT 1
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p);
int Bob(vector<int> t);
#include <utility>
////////////////////////////////////////////////////////////////////////////////////
int cost(vector<int>& a) {
int ans = 0;
for (int i = 0; i < a.size(); ++i)
ans += (a[i] == i);
return ans;
}
vector<int> g[401], path, vis;
vector<pair<int, vector<int>>> a;
void pre(int node, int par) {
path.push_back(node);
for (auto x : g[node])
if (x != par) pre(x, node);
}
void dfs(int node, vector<int>& p) {
a.back().second.push_back(node);
vis[node] = 1;
if (!vis[p[node]]) dfs(p[node], p);
}
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
if (e > m) return cost(p);
vector<int> deg(m);
for (int i = 0; i < e; ++i)
g[u[i]].push_back(v[i]),
g[v[i]].push_back(u[i]),
++deg[u[i]], ++deg[v[i]];
for (int i = 0; i < m; ++i)
if (deg[i] > 2) return cost(p);
if (e == (m - 1)) {
int best = (m == 2 ? n : n - m + 1);
if (cost(p) >= best) return cost(p);
path.clear(), a.clear();
vis.assign(n + 1, 0);
for (int i = 0; i < m; ++i)
if (deg[i] == 1) { pre(i, -1); break; }
while (1) {
vis.assign(n, 0), a.clear();
for (int i = 0; i < n; ++i)
if (!vis[i]) a.push_back({}), dfs(i, p),
a.back().first = a.back().second.size();
sort(a.begin(), a.end(), greater<pair<int, vector<int>>>());
while ((!a.empty()) && (a.back().first == 1)) a.pop_back();
int tot = 0;
for (auto& x : a) tot += x.first;
if (tot < m) break;
vector<int> cur;
for (int i = 0; i < n; ++i) {
for (auto x : a[i].second) {
if (cur.size() == m) break;
cur.push_back(x);
}
if (cur.size() == m) break;
}
vector<int> res(m);
for (int i = 0; i < m; ++i)
res[path[i]] = cur[i];
int op = Bob(res);
swap(p[res[u[op]]], p[res[v[op]]]);
}
for (int i = 0; i < m; ++i)
g[i].clear();
return best;
}
if (m == 3) {
path.clear(), a.clear();
vis.assign(n + 1, 0);
int ans = 0;
while (1) {
vis.assign(n, 0), a.clear();
for (int i = 0; i < n; ++i)
if (!vis[i]) a.push_back({}), dfs(i, p),
a.back().first = a.back().second.size();
sort(a.begin(), a.end(), greater<pair<int, vector<int>>>());
vector<pair<int, vector<int>>> na;
for (auto& x : a) if (x.first & 1)
if (x.first != 1)
na.push_back(x);
a = na;
ans = max(ans, (int)a.size() + cost(p));
int tot = 0;
for (auto& x : a) tot += x.first;
if (tot < m) break;
vector<int> cur;
for (int i = 0; i < n; ++i) {
for (auto x : a[i].second) {
if (cur.size() == m) break;
cur.push_back(x);
}
if (cur.size() == m) break;
}
vector<int> res(m);
for (int i = 0; i < m; ++i)
res[i] = cur[i];
int op = Bob(res);
swap(p[res[u[op]]], p[res[v[op]]]);
}
for (int i = 0; i < m; ++i)
g[i].clear();
return ans;
}
path.clear(), a.clear();
vis.assign(n, 0);
int ans = -1;
while (1) {
if ((ans != -1) && (cost(p) >= ans)) break;
vis.assign(n, 0), a.clear();
for (int i = 0; i < n; ++i)
if (!vis[i]) a.push_back({}), dfs(i, p),
a.back().first = a.back().second.size();
sort(a.begin(), a.end(), greater<pair<int, vector<int>>>());
vector<pair<int, vector<int>>> m2, m1;
for (auto &x : a) if (x.first % 3) if (x.first != 1)
if ((x.first % 3) == 1) m1.push_back(x);
else m2.push_back(x);
if (ans == -1) ans = ((int)m1.size())
+ ((int)m2.size()) / 2 + cost(p);
vector<int> cur;
if (m2.size() >= 2)
cur.push_back(m2[0].second[0]),
cur.push_back(m2[0].second[1]),
cur.push_back(m2[1].second[0]),
cur.push_back(m2[1].second[1]);
else if (m1.size())
for (int i = 0; i < m; ++i)
cur.push_back(m1[0].second[i]);
else break;
vector<int> res(m);
for (int i = 0; i < m; ++i)
res[i] = cur[i];
int op = Bob(res);
swap(p[res[u[op]]], p[res[v[op]]]);
}
for (int i = 0; i < m; ++i)
g[i].clear();
return ans;
}
////////////////////////////////////////////////////////////////////////////////////
#if SUBMIT == 0
//grader
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <random>
static int m, e, n;
static vector<int> u, v, p;
static int moves_taken;
int Bob(vector<int> t) {
moves_taken++;
if (t.size() != m) {
printf("Invalid interaction, t is not size m\n");
exit(0);
}
vector<int> cnt(n, 0);
for (int i = 0; i < m; i++) {
int ind = t[i];
if (ind < 0 || ind >= n) {
printf("Invalid interaction, t[i] out of range\n");
exit(0);
}
if (cnt[ind]) {
printf("Invalid interaction, t has duplicate elements\n");
exit(0);
}
cnt[ind]++;
}
if (moves_taken > (3 * n)) {
cout << "Too many moves!!" << endl;
exit(0);
}
cout << "current p: " << endl;
for (auto x : p) cout << x << " ";
cout << endl;
for (int i = 0; i < n; ++i) cout << i << " ";
cout << endl;
cout << "options: " << endl;
for (int i = 0; i < e; ++i)
cout << i << ": " << t[u[i]] << " " << t[v[i]] << endl;
vector<pair<int, int>> ops;
for (int i = 0; i < e; ++i) {
swap(p[t[u[i]]], p[t[v[i]]]);
ops.push_back({ cost(p), i });
swap(p[t[u[i]]], p[t[v[i]]]);
}
sort(ops.begin(), ops.end());
int j = ops[0].second;
swap(p[t[u[j]]], p[t[v[j]]]);
cout << "new score: " << cost(p) << endl;
return j;
}
int main() {
srand(time(NULL));
scanf("%d %d", &m, &e);
u.resize(e);
v.resize(e);
for (int i = 0; i < e; i++) {
scanf("%d %d", &u[i], &v[i]);
}
scanf("%d", &n);
p.resize(n);
for (int i = 0; i < n; i++) {
scanf("%d", &p[i]);
}
moves_taken = 0;
int optimal_score = Alice(m, e, u, v, n, p);
int actual_score = 0;
for (int i = 0; i < n; i++) {
actual_score += (p[i] == i);
}
for (int i = 0; i < n; i++) printf("%d ", p[i]);
printf("\n");
printf("optimal reported score: %d\n", optimal_score);
printf("score achieved: %d\n", actual_score);
printf("moves taken: %d\n", moves_taken);
return 0;
}
#endif
