#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 2
ll sz = 240;
vector<vector<int>> ans(sz, vector<int>(sz, 1));
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<bool> vis(N + 1, false);
function<void(ll)> dfs = [&](ll s) {
vis[s] = true;
ll h = 2, w = 1;
for (auto u : adj[s]) {
if (vis[u]) continue;
pr[u] = s;
dfs(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;
for (auto u : adj[s]) {
if (pr[s] == u) continue;
for (ll i = 0; i < dp[u].size(); i++) {
for (ll j = 0; j < dp[u].back().size(); j++) {
dp[s][i + 1][curr_j + j] = dp[u][i][j];
}
}
curr_j += dp[u].back().size() + 1;
}
/* cout << "dfs" _ s << nf;
for (auto v : dp[s]) {
for (auto u : v) {
cout << u << ' ';
}
cout << nf;
} */
};
dfs(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;
}
