#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 = 40;
for (int attempt = 0; attempt < max_attempts; ++attempt) {
vector<vector<int>> tree_adj(N + 1);
vector<bool> vis(N + 1, false);
// 随机拓扑生成三种不同形态的生成树供尝试
if (attempt % 3 == 0) {
vector<int> nodes(N); iota(nodes.begin(), nodes.end(), 1);
shuffle(nodes.begin(), nodes.end(), rng);
queue<int> q; q.push(nodes[0]); vis[nodes[0]] = 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) {
vector<int> nodes(N); iota(nodes.begin(), nodes.end(), 1);
shuffle(nodes.begin(), nodes.end(), rng);
int start = nodes[0];
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, start);
} 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);
}
}
}
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, 1, 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 >= 25) {
E.clear();
for(int x : E_base){ 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 try 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; // 保护树边
if((r>0 && C[r-1][c]==v) || (r+1<K && C[r+1][c]==v) || (c>0 && C[r][c-1]==v) || (c+1<K && C[r][c+1]==v)) {
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; placed = true;
}
}
}
}
if(placed) continue;
// 2. Single cell try 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;
if((r>0 && C[r-1][c]==u) || (r+1<K && C[r+1][c]==u) || (c>0 && C[r][c-1]==u) || (c+1<K && C[r][c+1]==u)) {
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; placed = true;
}
}
}
}
if(placed) continue;
// 3. Double cell placement (水平强行植入 u-v 或 v-u)
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 (垂直强行植入 u-v 或 v-u)
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;
}
