#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).
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 (is_graph_bipartite) {
return initial_score;
}
// 3. If non-bipartite, find winnable permutation cycles.
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 (optimal_score > initial_score) {
for (const auto& cycle_to_fix : winnable_cycles_nodes) {
int target_node = cycle_to_fix[0];
// This vector will hold the nodes of the cycle piece we are currently working on.
std::vector<int> current_piece_nodes = cycle_to_fix;
while (p[target_node] != target_node) {
// The condition k >= 2m-1 guarantees that the piece containing the
// target node will have a size of at least m, until it is fully resolved.
std::vector<int> t(m);
for (int k = 0; k < m; ++k) {
t[k] = current_piece_nodes[k];
}
int edge_j = Bob(t);
// Find which permutation indices correspond to the swapped edge
int p_idx1 = -1, p_idx2 = -1;
for(int k=0; k<m; ++k){
if(t[k] == u[edge_j] || t[k] == v[edge_j]){
bool mapping_found = false;
for(int l=0; l<m; ++l){
if(u[edge_j] == l && t[l] == t[k]) mapping_found = true;
if(v[edge_j] == l && t[l] == t[k]) mapping_found = true;
}
}
}
// We need to find which t[k] were mapped to the vertices u[j] and v[j]
// This requires reversing the implicit mapping.
// A simpler way is to just find the values in t that correspond to the vertices.
int t_for_u = -1, t_for_v = -1;
// This is a simplification; the t vector index is the vertex number.
t_for_u = t[u[edge_j]];
t_for_v = t[v[edge_j]];
std::swap(p[t_for_u], p[t_for_v]);
// After Bob's swap, re-evaluate the cycle piece containing our target node.
std::vector<bool> visited_piece(n, false);
current_piece_nodes.clear();
int current = target_node;
// We trace the new cycle path starting from our target node.
while (!visited_piece[current] && p[current] != current) {
visited_piece[current] = true;
current_piece_nodes.push_back(current);
current = p[current];
}
if(p[current] == current && !visited_piece[current]){
visited_piece[current] = true;
current_piece_nodes.push_back(current);
}
}
}
}
return optimal_score;
}
