#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 40 + 11;
vector<int> G[N_MAX], adj[N_MAX];
vector<vector<int>> regulate(vector<vector<int>> board) {
int n = board.size(), m = board[0].size();
int K = max(n, m);
vector ans = vector(K, vector<int>(K));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i][j] = board[i][j];
}
}
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
if (!ans[i][j]) {
if (j > 0 && ans[i][j - 1]) ans[i][j] = ans[i][j - 1];
else if (i > 0 && ans[i - 1][j]) ans[i][j] = ans[i - 1][j];
else assert(false);
}
}
}
return ans;
}
bool vis[N_MAX];
int sz[N_MAX], dep[N_MAX];
vector<int> ch[N_MAX];
void dfs0(int v, int pa = -1) {
vis[v] = true; sz[v] = 1;
ch[v].clear();
for (int u : G[v]) {
if (vis[u]) continue;
ch[v].push_back(u);
dep[u] = dep[v] + 1;
dfs0(u, v);
sz[v] += sz[u];
}
}
vector<vector<int>> ans;
void paint(int x, int y, int c) {
if (x < 0 || x >= ans.size() || y < 0 || y >= ans[0].size()) return;
ans[x][y] = c;
}
void paint2(int x, int y, int c1, int c2) {
paint(x, y, c1);
for (auto [dx, dy] : vector<pair<int, int>>{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
paint(x + dx, y + dy, c2);
}
}
int _N;
void dfs(int v, int pa, int x = 0, int y = 0, int l = 0, int r = _N - 1) {
// cout << "DFS " << v << ' ' << pa << ' ' << x << ' ' << y << endl;
vis[v] = true;
for (int i = 0; i <= r - y / 2; i++) {
// paint(x, y + i * 2 + (x % 4 / 2), i < adj[v].size() ? adj[v][i] : v);
paint2(x, y + i * 2 + (x % 4 / 2), i < adj[v].size() ? adj[v][i] : v, v);
}
int lst = ch[v].empty() ? -1 : ch[v].back();
for (int u : G[v]) {
if (vis[u]) continue;
dfs(u, v, x + 2, y, l, l + sz[u] - 2);
y += sz[u] * 2;
if (u != lst) {
for (int i = x + 2; i < _N * 2; i++) {
paint(i, y + (x % 4 / 2) - 2, v);
}
}
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
_N = N;
for (int i = 1; i <= N; i++) {
G[i].clear(); adj[i].clear();
}
fill(vis, vis + N + 1, false);
for (int i = 0; i < M; i++) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
// for (int i = 1; i <= N; i++) {
// cout << "G[" << i << "] => "; for (auto x : G[i]) cout << x << ' '; cout << endl;
// }
dfs0(1);
for (int i = 0; i < M; i++) {
if (dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
adj[A[i]].push_back(B[i]);
}
ans = vector(N * 2, vector<int> (N * 2));
fill(vis, vis + N + 1, false);
dfs(1, -1);
// return ans;
return regulate(ans);
}
