#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> tree(int n, vector<vector<int>> adj) {
vector<int> width(n + 1, 1);
auto calc_width = [&](auto&& self, int v, int par = -1) -> int {
width[v] = adj[v].size() + (par == -1);
for (int u : adj[v]) {
if (u == par) continue;
width[v] += self(self, u, v);
}
return width[v];
};
calc_width(calc_width, 1);
int k = width[1];
vector<vector<int>> ans(k, vector<int>(k));
auto fill_column = [&](int start, int j, int c) -> void {
for (int i = start; i < k; ++i)
ans[i][j] = c;
};
auto paint = [&](auto&& self, int v, int i, int j, int par = -1) -> void {
for (int l = 0; l < width[v]; ++l)
ans[i][j + l] = v;
fill_column(i, j, v);
int pref = 1;
for (int u : adj[v]) {
if (u == par) continue;
self(self, u, i + 1, j + pref, v);
pref += width[u] + 1;
fill_column(i, j + pref - 1, v);
}
};
paint(paint, 1, 0, 0);
return ans;
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; ++i) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
if (m == n - 1) {
return tree(n, adj);
} else if (m == n * (n - 1) / 2) {
vector<vector<int>> ans(n + 1, vector<int>(n + 1));
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
ans[i][j] = (j + i * (i + 1) / 2) % n + 1;
return ans;
}
return vector<vector<int>>{};
}
