#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int MAXN = 305;
int n, m;
int e[MAXN][MAXN];
vector<int> G[MAXN];
int dfn[MAXN], sz[MAXN], revv[MAXN];
vector<int> son[MAXN];
int tot;
vector<vi> emp;
void dfs(int u){
dfn[u] = ++tot;
revv[tot] = u;
sz[u] = 1;
for(int v: G[u]){
if(dfn[v]) continue;
dfs(v);
sz[u] += sz[v];
son[u].push_back(v);
}
}
vi mergev(const vi &L, const vi &R){
vi res = L;
res.insert(res.end(), R.begin(), R.end());
return res;
}
// build a block for subtree of u; len is the target width we will pad to
vector<vi> solve(int u, int len){
// if leaf
if(son[u].empty()) return emp;
// s = list of neighbors inside subtree that have an edge to u but are not parent and are not direct children in tree order
vi s;
// nodes in dfs order between dfn[u]+1 and dfn[u]+sz[u]-1 are exactly nodes in subtree except u
for(int i = dfn[u]+1; i <= dfn[u]+sz[u]-1; ++i){
int v = revv[i];
if(e[u][v]) s.push_back(v);
}
vector<vi> res(2 * (int)s.size());
vi outer(1, u);
if(u == 1){
// root: keep a border of u
for(auto &z: res) z.push_back(u);
}
for(size_t i = 0; i < s.size(); ++i){
res[2*i].push_back(u);
res[2*i+1].push_back(s[i]);
}
for(auto &z: res) if(z.back() != u) z.push_back(u);
int j = 1; // index in res where to place child blocks
for(int v: son[u]){
vector<vi> cur = solve(v, len - 2 - (u==1));
if(cur.empty()) continue;
// ensure there is space
while(j + (int)cur.size() + 1 > (int)res.size()) res.push_back(outer);
if((int)res[j+1].size() >= 2 + (u==1)) j++;
for(auto &z: cur){
if((int)res[j].size() < 2 + (u==1)) res[j].push_back(v);
res[j] = mergev(res[j], z);
j++;
}
res[j++].push_back(u);
}
// check last row all u
bool all_u = true;
for(int id: res.back()) if(id != u) { all_u = false; break; }
if(!all_u) res.push_back(outer);
// pad each row to length len by repeating last element
for(auto &z: res){
while((int)z.size() < len) z.push_back(z.back());
}
return res;
}
vector<vi> create_map(int N, int M, vi A, vi B){
n = N; m = M;
emp.clear();
for(int i = 1; i <= n; ++i){
G[i].clear(); son[i].clear(); dfn[i]=sz[i]=revv[i]=0;
for(int j = 1; j <= n; ++j) e[i][j]=0;
}
tot = 0;
for(int i = 0; i < m; ++i){
e[A[i]][B[i]] = e[B[i]][A[i]] = 1;
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
if(n == 1){
vector<vi> ans(1, vi(1,1));
return ans;
}
// run DFS from 1 (input guarantees a solution exists, graph should be connected for feasible maps)
dfs(1);
// solve for root with length 2*n (heuristic from editorial/accepted solutions)
vector<vi> ans = solve(1, 2*n);
vi base = ans.back();
while((int)ans.size() < 2*n) ans.push_back(base);
return ans;
}
