#include "worldmap.h"
using namespace std;
#include<cassert>
int n, t=0, d=0;
std::vector<int> vis;
std::vector<std::vector<int>> ans, adj;
void fill_diag(int d, int v) {
for (int x = 0; x < 2*n; x++) {
int y=d-x;
if (0<=y && y<2*n) ans[x][y]=v;
}
}
void dfs(int v) {
vis[v] = ++t;
int diag = d + 1;
d += 3;
fill_diag(diag - 1, v);
fill_diag(diag, v);
fill_diag(diag + 1, v);
int x = std::max(0, diag - 2 * n + 1);
for (int w : adj.at(v)) {
if (!vis.at(w)) {
dfs(w);
fill_diag(d, v);
++d;
} else if (vis.at(w) < vis.at(v)) {
assert(0 <= diag - x && diag - x < 2 * n);
ans.at(x).at(diag - x) = w;
++x;
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A,
std::vector<int> B) {
n=N;
ans.assign(2 * N, std::vector<int>(2 * N, 0));
adj.assign(N+1, 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]);
}
dfs(1);
while (d < 4 * N) {
fill_diag(d, 1);
++d;
}
assert(t == N);
return ans;
}
