#include "worldmap.h"
#include <vector>
#include <algorithm>
using namespace std;
void color(int d, int val, vector<vector<int>> &ans) {
int n = ans.size();
for (int i = 0; i <= d; ++i)
if (max(i, d - i) < n)
ans[i][d - i] = val + 1;
}
void dfs(int x, int pa, int n, int &k, vector<vector<int>> &ans, vector<vector<int>> &adj, vector<int> &vis) {
vis[x] = 1;
color(k++, x, ans);
for (auto y : adj[x])
if (!vis[y]) dfs(y, x, n, k, ans, adj, vis);
if (x == 0) return;
int e = max(0, k - 2 * n + 1);
color(k++, x, ans);
color(k++, x, ans);
color(k++, pa, ans);
for (auto y : adj[x])
if (vis[y] != 2)
ans[e++][k - 1 - e] = y + 1;
vis[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)), adj(N);
vector<int> vis(N, 0);
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);
}
int k = 0;
dfs(0, 0, N, k, ans, adj, vis);
return ans;
}
