#include "worldmap.h"
#include <functional>
#include <vector>
using namespace std;
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> ans(3*N, vector<int>(3*N, 1));
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++){
A[i]--; B[i]--;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<pair<int, int>> back_edges;
vector<int> depth(N, -1), tin(N), tout(N);
int tour = 0;
function<void(int, int, int, int, int)> draw = [&](int x0, int y0, int x1, int y1, int col) -> void {
for (int i = x0; i <= x1; i++){
for (int j = y0; j <= y1; j++){
ans[i][j] = col+1;
}
}
};
function<void(int, int, int)> dfs = [&](int v, int p, int d){
depth[v] = d;
draw(tour, 3*depth[v], tour, 3*N-1, v);
tin[v] = tour++;
for (int x : adj[v]){
if (x == p) continue;
if (depth[x] != -1){
back_edges.push_back({v, x});
continue;
}
dfs(x, v, d+1);
draw(tour, 3*depth[v], tour, 3*N-1, v);
tour++;
}
tout[v] = tour-1;
draw(tin[v], 3*depth[v], tout[v], 3*depth[v] + 2, v);
};
dfs(0, 0, 0);
for (auto [a, b] : back_edges){
if (depth[a] > depth[b])
swap(a, b);
draw(tin[b], 3*depth[a]+1, tin[b], 3*depth[a]+1, b);
}
return ans;
}
