#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <cstring>
#include <set>
using namespace std;
struct SASolver {
int N, K_SA;
int is_edge[45][45];
int adj_count[45][45];
int color_count[45];
int color_cells_r[45][6400];
int color_cells_c[45][6400];
int color_cells_sz[45];
int cell_pos[85][85];
int missing_edge_u[1000];
int missing_edge_v[1000];
int missing_edge_pos[45][45];
int missing_edge_sz;
int invalid_pairs;
int missing_colors;
int C_grid[85][85];
void add_missing(int u, int v) {
if(u > v) swap(u, v);
missing_edge_u[missing_edge_sz] = u;
missing_edge_v[missing_edge_sz] = v;
missing_edge_pos[u][v] = missing_edge_sz;
missing_edge_sz++;
}
void remove_missing(int u, int v) {
if(u > v) swap(u, v);
int pos = missing_edge_pos[u][v];
int last_u = missing_edge_u[missing_edge_sz - 1];
int last_v = missing_edge_v[missing_edge_sz - 1];
missing_edge_u[pos] = last_u;
missing_edge_v[pos] = last_v;
missing_edge_pos[last_u][last_v] = pos;
missing_edge_sz--;
}
void add_adj(int u, int v, int delta) {
if(u == v) return;
if(u > v) swap(u, v);
int old_c = adj_count[u][v];
adj_count[u][v] += delta;
int new_c = adj_count[u][v];
if(is_edge[u][v]) {
if(old_c == 0 && new_c > 0) remove_missing(u, v);
if(old_c > 0 && new_c == 0) add_missing(u, v);
} else {
if(old_c == 0 && new_c > 0) invalid_pairs++;
if(old_c > 0 && new_c == 0) invalid_pairs--;
}
}
void add_color(int u, int delta) {
int old_c = color_count[u];
color_count[u] += delta;
int new_c = color_count[u];
if(old_c == 0 && new_c > 0) missing_colors--;
if(old_c > 0 && new_c == 0) missing_colors++;
}
void change_color(int r, int c, int new_col) {
int old_col = C_grid[r][c];
if(old_col == new_col) return;
if(r > 0) add_adj(old_col, C_grid[r-1][c], -1);
if(r < K_SA - 1) add_adj(old_col, C_grid[r+1][c], -1);
if(c > 0) add_adj(old_col, C_grid[r][c-1], -1);
if(c < K_SA - 1) add_adj(old_col, C_grid[r][c+1], -1);
C_grid[r][c] = new_col;
if(r > 0) add_adj(new_col, C_grid[r-1][c], 1);
if(r < K_SA - 1) add_adj(new_col, C_grid[r+1][c], 1);
if(c > 0) add_adj(new_col, C_grid[r][c-1], 1);
if(c < K_SA - 1) add_adj(new_col, C_grid[r][c+1], 1);
add_color(old_col, -1);
add_color(new_col, 1);
int pos = cell_pos[r][c];
int last_r = color_cells_r[old_col][color_cells_sz[old_col] - 1];
int last_c = color_cells_c[old_col][color_cells_sz[old_col] - 1];
color_cells_r[old_col][pos] = last_r;
color_cells_c[old_col][pos] = last_c;
cell_pos[last_r][last_c] = pos;
color_cells_sz[old_col]--;
int new_pos = color_cells_sz[new_col]++;
color_cells_r[new_col][new_pos] = r;
color_cells_c[new_col][new_pos] = c;
cell_pos[r][c] = new_pos;
}
void init(int n, int k, const vector<vector<int>>& initial_C, const vector<vector<int>>& adj_mat) {
N = n; K_SA = k;
invalid_pairs = 0; missing_colors = 0; missing_edge_sz = 0;
memset(is_edge, 0, sizeof(is_edge));
memset(adj_count, 0, sizeof(adj_count));
memset(color_count, 0, sizeof(color_count));
memset(color_cells_sz, 0, sizeof(color_cells_sz));
for(int i=1; i<=N; ++i) {
for(int j=1; j<=N; ++j) is_edge[i][j] = adj_mat[i][j];
}
for(int i=1; i<=N; ++i) {
for(int j=i+1; j<=N; ++j) if(is_edge[i][j]) add_missing(i, j);
}
missing_colors = N;
for(int i=0; i<K_SA; ++i) {
for(int j=0; j<K_SA; ++j) {
C_grid[i][j] = initial_C[i][j];
int c_val = C_grid[i][j];
int pos = color_cells_sz[c_val]++;
color_cells_r[c_val][pos] = i; color_cells_c[c_val][pos] = j;
cell_pos[i][j] = pos;
if(color_count[c_val] == 0) missing_colors--;
color_count[c_val]++;
}
}
for(int i=0; i<K_SA; ++i) {
for(int j=0; j<K_SA; ++j) {
int c_val = C_grid[i][j];
if(i < K_SA - 1) {
int c2 = C_grid[i+1][j];
if(c_val != c2) {
int u = c_val, v = c2; if(u > v) swap(u, v);
int old_a = adj_count[u][v]++;
if(is_edge[u][v]) { if(old_a == 0) remove_missing(u, v); }
else { if(old_a == 0) invalid_pairs++; }
}
}
if(j < K_SA - 1) {
int c2 = C_grid[i][j+1];
if(c_val != c2) {
int u = c_val, v = c2; if(u > v) swap(u, v);
int old_a = adj_count[u][v]++;
if(is_edge[u][v]) { if(old_a == 0) remove_missing(u, v); }
else { if(old_a == 0) invalid_pairs++; }
}
}
}
}
}
bool solve(mt19937& rng) {
double temp = 50.0;
double cooling_rate = 0.99995;
for(int iter = 0; iter < 150000; ++iter) {
if(invalid_pairs == 0 && missing_edge_sz == 0 && missing_colors == 0) return true;
int r, c, new_col;
if(missing_edge_sz > 0 && (rng() % 2 == 0)) {
int e_idx = rng() % missing_edge_sz;
int u = missing_edge_u[e_idx], v = missing_edge_v[e_idx];
if(rng() % 2) swap(u, v);
if(color_cells_sz[u] > 0) {
int cell_idx = rng() % color_cells_sz[u];
r = color_cells_r[u][cell_idx]; c = color_cells_c[u][cell_idx];
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
int dir = rng() % 4; r += dr[dir]; c += dc[dir];
if(r < 0 || r >= K_SA || c < 0 || c >= K_SA) continue;
new_col = v;
} else { r = rng() % K_SA; c = rng() % K_SA; new_col = (rng() % N) + 1; }
} else { r = rng() % K_SA; c = rng() % K_SA; new_col = (rng() % N) + 1; }
int old_col = C_grid[r][c];
if(old_col == new_col) continue;
int old_E = invalid_pairs * 100 + missing_edge_sz * 10 + missing_colors * 1000;
change_color(r, c, new_col);
int new_E = invalid_pairs * 100 + missing_edge_sz * 10 + missing_colors * 1000;
if(new_E > old_E) {
double prob = exp((old_E - new_E) / temp);
if((rng() % 1000000) / 1000000.0 >= prob) change_color(r, c, old_col);
}
temp *= cooling_rate;
}
return (invalid_pairs == 0 && missing_edge_sz == 0 && missing_colors == 0);
}
};
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
if (N == 1) return {{1}};
vector<vector<int>> adj_matrix(N + 1, vector<int>(N + 1, 0));
vector<vector<int>> adj(N + 1);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]);
adj_matrix[A[i]][B[i]] = 1; adj_matrix[B[i]][A[i]] = 1;
}
// Algorithm 1: Eulerian Path max Matrix (Perfect for sparse)
vector<vector<int>> dist(N + 1, vector<int>(N + 1, 1e9));
vector<vector<int>> nxt_node(N + 1, vector<int>(N + 1, 0));
for (int i = 1; i <= N; ++i) {
dist[i][i] = 0; queue<int> q; q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[i][v] > dist[i][u] + 1) {
dist[i][v] = dist[i][u] + 1;
nxt_node[i][v] = (u == i) ? v : nxt_node[i][u];
q.push(v);
}
}
}
}
vector<int> odd_nodes;
for (int i = 1; i <= N; ++i) if (adj[i].size() % 2 != 0) odd_nodes.push_back(i);
mt19937 rng(1337);
int min_added = 1e9;
vector<pair<int, int>> best_added;
for (int iter = 0; iter < 50; ++iter) {
vector<int> cur_odd = odd_nodes;
shuffle(cur_odd.begin(), cur_odd.end(), rng);
vector<bool> m(cur_odd.size(), false);
vector<pair<int, int>> cur_added;
int cur_dist = 0;
for (int i = 0; i < cur_odd.size(); ++i) {
if (m[i]) continue;
int best_j = -1, best_d = 1e9;
for (int j = i + 1; j < cur_odd.size(); ++j) {
if (!m[j] && dist[cur_odd[i]][cur_odd[j]] < best_d) {
best_d = dist[cur_odd[i]][cur_odd[j]]; best_j = j;
}
}
if (best_j != -1) {
m[i] = m[best_j] = true; cur_dist += best_d;
int curr = cur_odd[i], target = cur_odd[best_j];
while (curr != target) {
int nex = nxt_node[curr][target];
cur_added.push_back({curr, nex}); curr = nex;
}
}
}
if (cur_dist < min_added) { min_added = cur_dist; best_added = cur_added; }
}
vector<pair<int, int>> euler_edges;
for (int i = 0; i < M; ++i) euler_edges.push_back({A[i], B[i]});
euler_edges.insert(euler_edges.end(), best_added.begin(), best_added.end());
vector<multiset<int>> euler_adj(N + 1);
for (auto e : euler_edges) { euler_adj[e.first].insert(e.second); euler_adj[e.second].insert(e.first); }
vector<int> circuit;
auto dfs_euler = [&](auto& self, int u) -> void {
while (!euler_adj[u].empty()) {
int v = *euler_adj[u].begin();
euler_adj[u].erase(euler_adj[u].begin()); euler_adj[v].erase(euler_adj[v].find(u));
self(self, v);
}
circuit.push_back(u);
};
dfs_euler(dfs_euler, 1);
if (circuit.size() <= 2 * N) {
int K = circuit.size();
vector<vector<int>> best_C(K, vector<int>(K));
for (int i = 0; i < K; ++i) {
for (int j = 0; j < K; ++j) best_C[i][j] = circuit[max(i, j)];
}
return best_C;
}
// Algorithm 2: Initial LCA Tree Spanning Sequence + Simulated Annealing (Perfect for Dense)
SASolver solver;
auto start_time = chrono::steady_clock::now();
while(true) {
auto now = chrono::steady_clock::now();
if(chrono::duration_cast<chrono::milliseconds>(now - start_time).count() > 30) break;
int root = (rng() % N) + 1;
vector<vector<int>> tree_adj(N + 1);
vector<bool> vis(N + 1, false);
queue<int> q; q.push(root); vis[root] = true;
while(!q.empty()){
int u = q.front(); q.pop();
vector<int> neighbors = adj[u]; shuffle(neighbors.begin(), neighbors.end(), rng);
for(int v : neighbors) {
if(!vis[v]) {
vis[v] = true;
tree_adj[u].push_back(v); tree_adj[v].push_back(u);
q.push(v);
}
}
}
vector<int> depth(N + 1, 0), parent_node(N + 1, 0), E_base;
auto dfs_tour = [&](auto& self, int u, int p, int d) -> void {
depth[u] = d; parent_node[u] = p; E_base.push_back(u);
for(int v : tree_adj[u]) { if(v != p){ self(self, v, u, d+1); E_base.push_back(u); } }
};
dfs_tour(dfs_tour, root, 0, 0);
auto get_lca = [&](int u, int v) -> int {
while(depth[u] > depth[v]) u = parent_node[u];
while(depth[v] > depth[u]) v = parent_node[v];
while(u != v){ u = parent_node[u]; v = parent_node[v]; }
return u;
};
int K_SA = E_base.size();
vector<vector<int>> initial_C(K_SA, vector<int>(K_SA));
for(int i=0; i<K_SA; ++i) {
for(int j=0; j<K_SA; ++j) initial_C[i][j] = get_lca(E_base[i], E_base[j]);
}
solver.init(N, K_SA, initial_C, adj_matrix);
bool success = solver.solve(rng);
if (success) {
vector<vector<int>> best_C(K_SA, vector<int>(K_SA));
for(int i=0; i<K_SA; ++i) {
for(int j=0; j<K_SA; ++j) best_C[i][j] = solver.C_grid[i][j];
}
return best_C;
}
}
// Base fallback safety measure
int K = circuit.size();
if (K > 240) return {{1}};
vector<vector<int>> best_C(K, vector<int>(K));
for (int i = 0; i < K; ++i) {
for (int j = 0; j < K; ++j) best_C[i][j] = circuit[max(i, j)];
}
return best_C;
}
