#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#include "worldmap.h"
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
// subtask 5
vector<vector<ll>> adj(N + 1);
for (ll i = 0; i < M; i++) {
adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]);
}
vector<vector<vector<ll>>> dp(N + 1);
vector<ll> pr(N + 1, -1);
vector<vector<ll>> children(N + 1), subs(N + 1);
vector<bool> vis(N + 1, false);
vector<ll> tin(N + 1, -1);
ll curr_time = 1;
function<void(ll)> dfs = [&](ll s) {
vis[s] = true;
tin[s] = curr_time; curr_time++;
for (auto u : adj[s]) {
if (vis[u]) continue;
pr[u] = s; children[s].pb(u);
dfs(u);
}
};
dfs(1);
for (ll i = 0; i < M; i++) {
ll a = A[i], b = B[i];
if (tin[a] > tin[b]) swap(a, b);
if (pr[b] == a) continue;
subs[a].pb(b);
}
auto frame = [&](ll s, vector<ll> v) {
if (v.empty()) v = {s};
vector ans(2 * (ll)v.size() - 1, vector<ll>(1, s));
for (ll i = 0; i < v.size(); i++) ans[2 * i][0] = v[i];
return ans;
};
function<void(ll)> build = [&](ll s) {
vector<vector<ll>> last = frame(s, subs[s]);
ll h = last.size() + 2, w = 3;
for (auto u : children[s]) {
build(u);
h = max(h, (ll)dp[u].size() + 2);
w += dp[u].back().size() + 1;
}
dp[s] = vector(h, vector<ll>(w, s));
ll curr_j = 1;
auto onion = [&](vector<vector<ll>> v) {
for (ll i = 0; i < v.size(); i++) {
for (ll j = 0; j < v.back().size(); j++) {
dp[s][i + 1][curr_j + j] = v[i][j];
}
}
curr_j += v.back().size() + 1;
};
for (auto u : children[s]) {
onion(dp[u]);
}
onion(last);
/* cout << "build" _ s << nf;
for (auto v : dp[s]) {
for (auto u : v) {
cout << u << ' ';
}
cout << nf;
} */
};
build(1);
ll sz = max(dp[1].size(), dp[1].back().size());
vector<vector<int>> ans(sz, vector<int>(sz, 1));
for (ll i = 0; i < dp[1].size(); i++) {
for (ll j = 0; j < dp[1].back().size(); j++) {
ans[i][j] = dp[1][i][j];
}
}
return ans;
}
