#include "worldmap.h"
int n, dcnt=0;
std::vector<int> vis;
std::vector<std::vector<int>> child, back, adj, ans;
void fill_diag(int d, int c) {
for (int x = 0; x < 2*n; x++) {
int y=d-x;
if (0<=y && y<2*n) ans[x][y]=c;
}
}
void dfs(int u, int p, int t=1) {
vis[u]=t;
int diag=dcnt+1; dcnt+=3;
fill_diag(diag-1, u);
fill_diag(diag, u);
fill_diag(diag+1, u);
int x=std::max(0, diag-2*n+1);
for (auto v : adj[u]) {
if (v==p) continue;
if (!vis[v]) {
dfs(v, u, t+1);
fill_diag(dcnt, v);
dcnt++;
} else if (vis[v]<vis[u]) {
ans[x][diag-x]=v;
x++;
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
n=N;
child.assign(N+1, std::vector<int>());
back.assign(N+1, std::vector<int>());
adj.assign(N+1, std::vector<int>());
vis.assign(N+1, 0);
for (int i = 0; i < M; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
ans.assign(2*N, std::vector<int>(2*N, 1));
dfs(1, 1);
return ans;
}
