#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <random>
#include <numeric>
#include <set>
#include <map>
using namespace std;
// 预编译修改模板，提升数百倍搜寻速度
struct Pattern {
vector<int> vals;
int mask;
};
static bool initialized = false;
static map<pair<int, int>, vector<Pattern>> precomputed_patterns;
static vector<pair<int, int>> block_sizes = {
{1, 2}, {2, 1},
{1, 3}, {3, 1},
{2, 2},
{1, 4}, {4, 1},
{2, 3}, {3, 2},
{3, 3}
};
void initialize_patterns() {
if (initialized) return;
for (auto bs : block_sizes) {
int h = bs.first, w = bs.second;
vector<Pattern> res;
int total = 1;
for(int i=0; i<h*w; ++i) total *= 3;
for(int m=0; m<total; ++m) {
vector<int> assign(h * w);
int temp = m;
int pmask = 0;
for(int i=0; i<h*w; ++i) {
assign[i] = temp % 3;
if (assign[i] != 0) pmask |= (1 << i);
temp /= 3;
}
bool has_uv = false;
for (int i=0; i<h; ++i) {
for (int j=0; j<w; ++j) {
int val1 = assign[i * w + j];
if (val1 == 0) continue;
if (i + 1 < h) {
int val2 = assign[(i+1) * w + j];
if ((val1 == 1 && val2 == 2) || (val1 == 2 && val2 == 1)) has_uv = true;
}
if (j + 1 < w) {
int val2 = assign[i * w + j + 1];
if ((val1 == 1 && val2 == 2) || (val1 == 2 && val2 == 1)) has_uv = true;
}
}
}
if (has_uv) {
int min_r = h, max_r = -1, min_c = w, max_c = -1;
for(int i=0; i<h; ++i) {
for(int j=0; j<w; ++j) {
if (assign[i * w + j] != 0) {
min_r = min(min_r, i); max_r = max(max_r, i);
min_c = min(min_c, j); max_c = max(max_c, j);
}
}
}
if (min_r == 0 && max_r == h - 1 && min_c == 0 && max_c == w - 1) {
res.push_back({assign, pmask});
}
}
}
precomputed_patterns[bs] = res;
}
initialized = true;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
initialize_patterns();
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;
}
mt19937 rng(1337);
vector<vector<int>> best_C;
int best_K = 1e9;
// =========================================================
// 算法 1：欧拉路径序列矩阵法 (Sequence Matrix) - 专攻稀疏图
// =========================================================
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);
}
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() <= 240) {
int K = circuit.size();
best_K = K;
best_C.assign(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)];
}
}
}
if (best_K <= 2 * N) return best_C;
// =========================================================
// 算法 2：LCA 矩阵随机生成法 - 配合全尺寸渗透模板专攻稠密图
// =========================================================
int max_deg_node = 1;
for (int i = 1; i <= N; ++i) if (adj[i].size() > adj[max_deg_node].size()) max_deg_node = i;
for (int attempt = 0; attempt < 40; ++attempt) {
vector<vector<int>> tree_adj(N + 1);
vector<bool> vis(N + 1, false);
int root = max_deg_node;
if (attempt % 3 == 0) {
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); }
}
} else if (attempt % 3 == 1) {
root = (rng() % N) + 1;
auto dfs_rand = [&](auto& self, int u) -> void {
vis[u] = true;
vector<int> neighbors = adj[u]; shuffle(neighbors.begin(), neighbors.end(), rng);
for(int v : neighbors) if(!vis[v]){ tree_adj[u].push_back(v); tree_adj[v].push_back(u); self(self, v); }
};
dfs_rand(dfs_rand, root);
} else {
vector<int> parent(N + 1); iota(parent.begin(), parent.end(), 0);
auto find_set = [&](int i, auto& fs) -> int { return parent[i] == i ? i : (parent[i] = fs(parent[i], fs)); };
vector<pair<int, int>> edges; for(int i=0; i<M; ++i) edges.push_back({A[i], B[i]});
shuffle(edges.begin(), edges.end(), rng);
for(auto& e : edges){
int r_i = find_set(e.first, find_set), r_j = find_set(e.second, find_set);
if(r_i != r_j){ parent[r_i] = r_j; tree_adj[e.first].push_back(e.second); tree_adj[e.second].push_back(e.first); }
}
root = (rng() % N) + 1;
}
vector<pair<int, int>> non_tree_edges;
for(int i=0; i<M; ++i){
int u = A[i], v = B[i];
bool is_tree = false;
for(int child : tree_adj[u]) if(child == v){ is_tree = true; break; }
if(!is_tree) non_tree_edges.push_back({u, v});
}
shuffle(non_tree_edges.begin(), non_tree_edges.end(), rng);
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;
};
vector<vector<int>> lca_pre(N + 1, vector<int>(N + 1, 0));
for(int i=1; i<=N; ++i) for(int j=1; j<=N; ++j) lca_pre[i][j] = get_lca(i, j);
vector<int> E = E_base;
int K = E.size();
if (K > 240 || K >= best_K) continue;
vector<vector<int>> C(K, vector<int>(K));
for(int i=0; i<K; ++i) for(int j=0; j<K; ++j) C[i][j] = lca_pre[E[i]][E[j]];
vector<vector<bool>> modified(K, vector<bool>(K, false));
// 极简非对称保护：对角线及单上侧即可保证树边完美相接，彻底释放其余大量空间！
auto is_protected = [&](int r, int c) {
if (r == c) return true;
if (r == c - 1 && E[r] != E[c]) return true;
return false;
};
auto valid_neighbor = [&](int r, int c, int u) -> bool {
if(r < 0 || r >= K || c < 0 || c >= K) return true;
int color = C[r][c];
return color == u || adj_matrix[u][color];
};
bool all_placed = true;
for(auto& edge : non_tree_edges){
int u = edge.first, v = edge.second;
bool placed = false;
// Phase 1: 单点接触
for(int r = 0; r < K && !placed; ++r){
for(int c = 0; c < K && !placed; ++c){
if(is_protected(r, c) || modified[r][c]) continue;
int v_r = -1, v_c = -1;
if(r > 0 && C[r-1][c] == v) { v_r = r - 1; v_c = c; }
else if(r + 1 < K && C[r+1][c] == v) { v_r = r + 1; v_c = c; }
else if(c > 0 && C[r][c-1] == v) { v_r = r; v_c = c - 1; }
else if(c + 1 < K && C[r][c+1] == v) { v_r = r; v_c = c + 1; }
if(v_r != -1) {
if(valid_neighbor(r-1, c, u) && valid_neighbor(r+1, c, u) && valid_neighbor(r, c-1, u) && valid_neighbor(r, c+1, u)){
C[r][c] = u; modified[r][c] = true; modified[v_r][v_c] = true; placed = true;
}
}
}
}
if(placed) continue;
for(int r = 0; r < K && !placed; ++r){
for(int c = 0; c < K && !placed; ++c){
if(is_protected(r, c) || modified[r][c]) continue;
int u_r = -1, u_c = -1;
if(r > 0 && C[r-1][c] == u) { u_r = r - 1; u_c = c; }
else if(r + 1 < K && C[r+1][c] == u) { u_r = r + 1; u_c = c; }
else if(c > 0 && C[r][c-1] == u) { u_r = r; u_c = c - 1; }
else if(c + 1 < K && C[r][c+1] == u) { u_r = r; u_c = c + 1; }
if(u_r != -1) {
if(valid_neighbor(r-1, c, v) && valid_neighbor(r+1, c, v) && valid_neighbor(r, c-1, v) && valid_neighbor(r, c+1, v)){
C[r][c] = v; modified[r][c] = true; modified[u_r][u_c] = true; placed = true;
}
}
}
}
if(placed) continue;
// Phase 2: 高维全尺寸模块化渗透搜寻
for (auto& bs : block_sizes) {
if (placed) break;
int h = bs.first, w = bs.second;
const auto& patterns = precomputed_patterns[bs];
for (int r = 0; r <= K - h && !placed; ++r) {
for (int c = 0; c <= K - w && !placed; ++c) {
int bad_mask = 0;
for(int i=0; i<h; ++i) {
for(int j=0; j<w; ++j) {
if (modified[r+i][c+j] || is_protected(r+i, c+j)) bad_mask |= (1 << (i * w + j));
}
}
for (const auto& pat : patterns) {
if ((pat.mask & bad_mask) != 0) continue;
bool ok = true;
for (int i=0; i<h && ok; ++i) {
for (int j=0; j<w && ok; ++j) {
if (pat.vals[i * w + j] == 0) continue;
int target_color = (pat.vals[i * w + j] == 1) ? u : v;
int gr = r + i, gc = c + j;
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
for (int d=0; d<4; ++d) {
int nr = gr + dr[d], nc = gc + dc[d];
if (nr >= 0 && nr < K && nc >= 0 && nc < K) {
int ncolor;
if (nr >= r && nr < r + h && nc >= c && nc < c + w) {
int nval = pat.vals[(nr - r) * w + (nc - c)];
if (nval == 1) ncolor = u;
else if (nval == 2) ncolor = v;
else ncolor = C[nr][nc];
} else {
ncolor = C[nr][nc];
}
if (ncolor != target_color && !adj_matrix[target_color][ncolor]) {
ok = false; break;
}
}
}
}
}
if (ok) {
for (int i=0; i<h; ++i) {
for (int j=0; j<w; ++j) {
int val = pat.vals[i * w + j];
if (val != 0) { C[r+i][c+j] = (val == 1) ? u : v; modified[r+i][c+j] = true; }
}
}
placed = true; break;
}
}
}
}
}
if(!placed) { all_placed = false; break; }
}
if(all_placed){
if(K < best_K){ best_K = K; best_C = C; }
if(best_K <= 2 * N) break;
}
}
return best_C;
}
