#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
std::vector<std::vector<int>> ans(3 * N, std::vector<int>(3 * N, 1));
vector<vector<bool>> changed(3*N, vector<bool>(3*N, 0));
vector<vector<int>> adj(N);
for(int i = 0; i<M; i++){
adj[A[i]-1].push_back(B[i]-1);
adj[B[i]-1].push_back(A[i]-1);
}
vector<bool> vis(N, 0);
vector<vector<int>> back(N);
vector<vector<int>> t(N);
auto dfs = [&](auto&& dfs, int v, int p)->void{
vis[v] = 1;
for(int u: adj[v]){
if(u == p) continue;
if(vis[u]) back[u].push_back(v);
else{
t[v].push_back(u);
dfs(dfs, u, v);
}
}
return;
};
dfs(dfs, 0, -1);
vector<int> proc(N, INT_MAX);
int timer = 0;
auto rec = [&](auto&& rec, int c, int i0, int j0)->int{
proc[c] = timer++;
for(int i = i0+3; i<3*N; i++) ans[i][j0] = c+1;
int curr_j = j0+1;
for(int u: t[c]){
curr_j = rec(rec, u, i0+3, curr_j)+1;
for(int i = i0+3; i<3*N; i++) ans[i][curr_j] = c+1;
curr_j++;
}
curr_j--;
int curr_j2 = j0+1;
for(int u: back[c]){
if(proc[u] < proc[c]) continue;
ans[i0+1][curr_j2] = u+1;
changed[i0+1][curr_j2] = 1;
curr_j2+=2;
}
curr_j2--;
for(int i = i0; i<i0+3; i++){
for(int j = j0; j<=max(curr_j, curr_j2); j++) if(!changed[i][j]) ans[i][j] =c+1;
}
for(int j = curr_j+1; j<=curr_j2; j++){
for(int i = i0+3; i<3*N; i++){
ans[i][j] = c+1;
}
}
//assert(curr_j2 < curr_j-1);
return max(curr_j, curr_j2);
};
rec(rec, 0, 0, 0);
return ans;
}
