#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
// Forward declaration of the grader's function for interaction with Bob.
int Bob(std::vector<int> t);
namespace {
// Helper structures for graph analysis and permutation tracking.
std::vector<std::vector<int>> adj;
std::vector<int> color;
std::vector<bool> visited;
// Utility function to check for bipartiteness using 2-coloring (BFS/DFS).
// It's run on the graph which is known to be connected.
bool is_bipartite_util(int u, int c) {
visited[u] = true;
color[u] = c;
for (int v : adj[u]) {
if (!visited[v]) {
if (!is_bipartite_util(v, 1 - c)) {
return false;
}
} else if (color[v] == color[u]) {
return false;
}
}
return true;
}
}
int Alice(int m, int e, std::vector<int> u, std::vector<int> v,
int n, std::vector<int> p) {
// 1. Calculate the initial score of the permutation.
int initial_score = 0;
for (int i = 0; i < n; ++i) {
if (p[i] == i) {
initial_score++;
}
}
// 2. Analyze the graph's structure.
adj.assign(m, std::vector<int>());
for (int i = 0; i < e; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
visited.assign(m, false);
color.assign(m, -1);
// The problem statement guarantees the graph is connected.
bool is_graph_bipartite = is_bipartite_util(0, 0);
// If the graph is bipartite, Alice cannot guarantee forcing the swaps she needs.
// No improvement is possible against an optimal Bob.
if (is_graph_bipartite) {
return initial_score;
}
// 3. If non-bipartite, find winnable permutation cycles.
// A cycle C is winnable if |C| >= 2m - 1. This ensures Alice can always
// continue breaking it down until a fixed point is made.
long long required_cycle_size = 2LL * m - 1;
int winnable_cycles_count = 0;
std::vector<std::vector<int>> winnable_cycles_nodes;
visited.assign(n, false);
for (int i = 0; i < n; ++i) {
if (p[i] == i || visited[i]) {
continue;
}
std::vector<int> current_cycle;
int current = i;
while (!visited[current]) {
visited[current] = true;
current_cycle.push_back(current);
current = p[current];
}
if (current_cycle.size() >= required_cycle_size) {
winnable_cycles_count++;
winnable_cycles_nodes.push_back(current_cycle);
}
}
int optimal_score = initial_score + winnable_cycles_count;
// 4. Play the game to achieve the optimal score, if it's higher than the start.
if (optimal_score > initial_score) {
for (const auto& cycle_to_fix : winnable_cycles_nodes) {
int target_node = cycle_to_fix[0];
std::vector<int> current_piece = cycle_to_fix;
// Keep playing on this cycle until our target becomes a fixed point.
while (p[target_node] != target_node) {
std::vector<int> t(m);
// Map the first m nodes of the current cycle piece to the graph vertices.
// The size condition guarantees the piece is large enough to do this
// until the very end.
for (int k = 0; k < m; ++k) {
t[k] = current_piece[k];
}
int edge_j = Bob(t);
std::swap(p[t[u[edge_j]]], p[t[v[edge_j]]]);
// After the swap, re-evaluate the cycle piece containing our target node.
std::vector<bool> visited_piece(n, false);
current_piece.clear();
int current = target_node;
while (!visited_piece[current] && p[current] != current) {
visited_piece[current] = true;
current_piece.push_back(current);
current = p[current];
}
}
}
}
return optimal_score;
}
