#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
// DFS sinh Euler tour từ đỉnh u
void dfs(int u, vector<bool>& vis, vvi& adj, vi& tour) {
vis[u] = true;
tour.push_back(u);
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v, vis, adj, tour);
tour.push_back(u);
}
}
}
vvi create_map(int n, int m, vi a, vi b) {
vvi adj(n + 1);
for (int i = 0; i < m; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
vector<bool> vis(n + 1, false);
vi tour;
dfs(1, vis, adj, tour);
const int K = 3 * n - 1;
vector<set<pair<int, int>>> diags(2 * K - 1);
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
int diag_id = i + j;
diags[diag_id].insert({i, j});
}
}
vvi ans(K, vi(K));
vvi diag_usage(n + 1);
int current_diag = 0;
for (int i = 0; i < (int)tour.size(); i++) {
int color = tour[i];
diag_usage[color].push_back(current_diag + 1);
while (current_diag < 3 * (i + 1)) {
for (auto [x, y] : diags[current_diag]) {
ans[x][y] = color;
}
++current_diag;
}
}
for (int u = 1; u <= n; u++) {
int idx = 0;
for (int diag_id : diag_usage[u]) {
for (auto [x, y] : diags[diag_id]) {
if (idx >= (int)adj[u].size()) break;
ans[x][y] = adj[u][idx++];
}
}
}
return ans;
}
