#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
static vector<vector<int>> adj;
static vector<int> vis, instk, dep, tin, tout, euler;
static vector<vector<int>> push_at;
static void dfs(int u, int p){
tin[u] = (int)euler.size();
euler.push_back(u);
vis[u] = 1;
instk[u] = 1;
for(int v : adj[u]){
if(v == p) continue;
if(!vis[v]){
dep[v] = dep[u] + 1;
dfs(v, u);
euler.push_back(u);
}else{
if(!instk[v]){
push_at[tin[v]].push_back(dep[u]);
}
}
}
tout[u] = (int)euler.size();
instk[u] = 0;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
adj.assign(N, {});
for(int i = 0; i < M; i++){
int u = A[i] - 1, v = B[i] - 1;
adj[u].push_back(v);
adj[v].push_back(u);
}
vis.assign(N, 0);
instk.assign(N, 0);
dep.assign(N, 0);
tin.assign(N, 0);
tout.assign(N, 0);
euler.clear();
push_at.assign(2 * N, {});
dfs(0, -1);
int K = 2 * N;
vector<vector<int>> grid(K, vector<int>(K, 0));
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
stable_sort(ord.begin(), ord.end(), [&](int x, int y){ return dep[x] < dep[y]; });
for(int u : ord){
int r0 = 2 * dep[u];
for(int r = r0; r < K; r++){
for(int c = tin[u]; c < tout[u]; c++){
grid[r][c] = u;
}
}
}
for(int c = 0; c < K; c++){
auto &v = push_at[c];
if(v.empty()) continue;
sort(v.begin(), v.end());
int j = 0;
while(j < (int)v.size()){
int k = j + 1;
while(k < (int)v.size() && v[k] == v[k - 1] + 1) k++;
int lastd = v[k - 1];
int rr = 2 * lastd + 2;
if(0 <= rr && rr < K) grid[rr][c] = grid[rr - 1][c];
for(int t = j; t < k; t++){
int d = v[t];
int r = 2 * d + 1;
if(0 <= r && r < K && c < (int)euler.size()) grid[r][c] = euler[c];
}
j = k;
}
}
for(int r = 0; r < K; r++){
for(int c = 0; c < K; c++){
grid[r][c] += 1;
}
}
return grid;
}
