#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <random>
#include <numeric>
#include <set>
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;
// =========================================================
// 算法 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 < 60; ++attempt) {
vector<vector<int>> tree_adj(N + 1);
vector<bool> vis(N + 1, false);
int root = max_deg_node;
// 随机产生多种样貌的生成树（BFS / DFS / Kruskal）
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;
if (attempt >= 45) { for(int x : E_base){ E.push_back(x); E.push_back(x); E.push_back(x); } }
else if (attempt >= 30) { for(int x : E_base){ E.push_back(x); E.push_back(x); } }
else { 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;
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;
}
