#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;
};
auto transpose = [&](vector<vector<ll>> v) {
vector w(v.back().size(), vector<ll>(v.size(), 0));
for (ll i = 0; i < v.size(); i++) {
for (ll j = 0; j < v.back().size(); j++) {
w[j][i] = v[i][j];
}
}
return w;
};
function<void(ll)> build = [&](ll s) {
vector<vector<ll>> last = frame(s, subs[s]);
for (auto u : children[s]) {
build(u);
}
dp[s] = vector(1, vector<ll>(1, s));
ll curr_j = 1;
auto onion = [&](vector<vector<ll>> v) {
ll w = dp[s].back().size();
dp[s].resize(max(dp[s].size(), v.size() + 2));
for (auto &u : dp[s]) {
u.resize(w + v.back().size() + 1, s);
}
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(transpose(dp[u]));
}
onion(last);
if (children[s].empty()) dp[s] = {{s}};
/* cout << "build" _ s << nf;
for (auto v : dp[s]) {
for (auto u : v) {
cout << u << ' ';
}
cout << nf;
} */
};
build(1);
/* cout << N _ M << nf;
for (ll i = 0; i < M; i++) {
cout << A[i] _ B[i] << nf;
} */
ll sz = max(dp[1].size(), dp[1].back().size()) - 1;
// assert(sz <= 3 * N);
vector<vector<int>> ans(sz, vector<int>(sz, 1));
for (ll i = 0; i < min(sz, (ll)dp[1].size()); i++) {
for (ll j = 0; j < min(sz, (ll)dp[1].back().size()); j++) {
ans[i][j] = dp[1][i][j];
}
}
return ans;
}
