#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, 随机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 >= 45 && attempt < 55) {
E.clear();
for(int x : E_base){ E.push_back(x); E.push_back(x); }
} else if (attempt >= 55) {
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 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;
// 1. Single cell 修改为 u, 锚定它身旁早已存在的 v
for(int r=0; r<K && !placed; ++r){
for(int c=0; c<K && !placed; ++c){
if(abs(r - c) <= 1 || 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; // 核心修复点：将作为靠山的邻居 v 的位置也彻底冻结，保护该条边缘
placed = true;
}
}
}
}
if(placed) continue;
// 2. Single cell 修改为 v, 锚定身旁早已存在的 u
for(int r=0; r<K && !placed; ++r){
for(int c=0; c<K && !placed; ++c){
if(abs(r - c) <= 1 || 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; // 同理：保护身边的依靠锚点 u
placed = true;
}
}
}
}
if(placed) continue;
// 3. Double cell placement (水平成对空降生成)
for(int r=0; r<K && !placed; ++r){
for(int c=0; c<K-1 && !placed; ++c){
if(abs(r - c) <= 1 || abs(r - (c+1)) <= 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;
// 4. Double cell placement (竖向成对空降生成)
for(int r=0; r<K-1 && !placed; ++r){
for(int c=0; c<K && !placed; ++c){
if(abs(r - c) <= 1 || abs(r+1 - c) <= 1 || 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;
}
