#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
void color(int d, int val, vector<vector<int>> &ans) {
for (int i = 0; i <= d; ++i)
if (max(i, d-i) < ans.size())
ans[i][d - i] = val + 1;
}
void dfs(int x, int pa, int n, int &k, vector<vector<int>> &ans, auto &v, auto &f) {
f[x] = 1;
color(k, x, ans);
k++;
for (int y : v[x]) {
if(!f[y])
dfs(y, x, n, k, ans, v, f);
}
if(x == 0) return;
int e = max(0, k - 2 * n + 1);
color(k, x, ans);
color(k+1, x, ans);
color(k+2, pa, ans);
for (int y : v[x])
if(f[y] != 2)
ans[e][k - e] = y + 1,
e++;
k += 3;
f[x] = 2;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> ans(2 * N, vector<int>(2 * N, 1)), v(N);
vector<int> f(N, 0);
for (int i = 0; i < M; ++i) {
v[A[i] - 1].push_back(B[i] - 1);
v[B[i] - 1].push_back(A[i] - 1);
}
int k = 0;
dfs(0, 0, N, k, ans, v, f);
return ans;
}
