#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <random>
#include <numeric>
using namespace std;
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
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 = 1000;
int max_attempts = 60;
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 < max_attempts; ++attempt) {
vector<vector<int>> tree_adj(N + 1);
vector<bool> vis(N + 1, false);
int root = max_deg_node;
// 随机化各种生成树类型：星状偏好 BFS、随机 BFS、随机 DFS、Kruskal 树
if (attempt % 4 == 0) {
queue<int> q; q.push(max_deg_node); vis[max_deg_node] = 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 % 4 == 1) {
root = (rng() % N) + 1;
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 % 4 == 2) {
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 root_i = find_set(e.first, find_set);
int root_j = find_set(e.second, find_set);
if(root_i != root_j){
parent[root_i] = root_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;
// 极度稠密图多轮寻找失败后的备用方案，利用加倍欧拉序来强开宽广的地形，但有了不对称保护后几乎用不上
if (attempt >= 40 && attempt < 50) {
E.clear(); for(int x : E_base){ E.push_back(x); E.push_back(x); }
} else if (attempt >= 50) {
E.clear(); for(int x : E_base){ E.push_back(x); E.push_back(x); E.push_back(x); }
}
int K = E.size();
if (K > 240) 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) {
return r == c || r == c - 1;
};
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;
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;
for(int r = 0; r < K && !placed; ++r){
for(int c = 0; c < K - 1 && !placed; ++c){
if(is_protected(r, c) || is_protected(r, c+1) || modified[r][c] || modified[r][c+1]) continue;
if(valid_neighbor(r-1, c, u) && valid_neighbor(r+1, c, u) && valid_neighbor(r, c-1, u) &&
valid_neighbor(r-1, c+1, v) && valid_neighbor(r+1, c+1, v) && valid_neighbor(r, c+2, v)){
C[r][c] = u; C[r][c+1] = v;
modified[r][c] = true; modified[r][c+1] = true;
placed = true; break;
}
if(valid_neighbor(r-1, c, v) && valid_neighbor(r+1, c, v) && valid_neighbor(r, c-1, v) &&
valid_neighbor(r-1, c+1, u) && valid_neighbor(r+1, c+1, u) && valid_neighbor(r, c+2, u)){
C[r][c] = v; C[r][c+1] = u;
modified[r][c] = true; modified[r][c+1] = true;
placed = true; break;
}
}
}
if(placed) continue;
for(int r = 0; r < K - 1 && !placed; ++r){
for(int c = 0; c < K && !placed; ++c){
if(is_protected(r, c) || is_protected(r+1, c) || modified[r][c] || modified[r+1][c]) continue;
if(valid_neighbor(r-1, c, u) && valid_neighbor(r, c-1, u) && valid_neighbor(r, c+1, u) &&
valid_neighbor(r+2, c, v) && valid_neighbor(r+1, c-1, v) && valid_neighbor(r+1, c+1, v)){
C[r][c] = u; C[r+1][c] = v;
modified[r][c] = true; modified[r+1][c] = true;
placed = true; break;
}
if(valid_neighbor(r-1, c, v) && valid_neighbor(r, c-1, v) && valid_neighbor(r, c+1, v) &&
valid_neighbor(r+2, c, u) && valid_neighbor(r+1, c-1, u) && valid_neighbor(r+1, c+1, u)){
C[r][c] = v; C[r+1][c] = u;
modified[r][c] = true; modified[r+1][c] = 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;
}
