#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const long long INF = 100000000000000;
std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> a, std::vector<int> b) {
std::vector<std::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]);
}
int mdepth = 0;
std::vector<int> order, visited(n+1, 0), layer(n+1, 0), par(n+1, 0), tin(n+1, 0), tout(n+1, 0);
auto dfs = [&](int u, int p, auto &&dfs) -> void {
order.push_back(u);
tin[u] = order.size()-1;
layer[u] = layer[p]+1;
mdepth = std::max(mdepth, layer[u]);
par[u] = p;
int cnt = 0;
for(auto v : adj[u]) cnt += !visited[v];
if(!cnt) {
tout[u] = order.size()-1;
return;
}
visited[u] = 1;
for(auto v : adj[u]) {
if(v == p || visited[v]) continue;
dfs(v, u, dfs);
order.push_back(u);
}
tout[u] = order.size()-1;
};
layer[1] = 1;
dfs(1, 0, dfs);
std::vector<int> start(n+1, 0);
for(int i = 1; i <= n; ++i) start[i] = tin[i]+1;
std::vector<std::vector<int>> matrix;
while(mdepth) {
for(int i = 0; i < 3; ++i) matrix.push_back(order);
for(int i = 0; i < order.size(); ++i) {
if(layer[order[i]] == mdepth) order[i] = par[order[i]];
}
--mdepth;
}
std::reverse(matrix.begin(), matrix.end());
std::set<std::array<int, 2>> edges;
for(int i = 1; i <= n; ++i) {
for(auto j : adj[i]) {
if(layer[i] < layer[j]) edges.insert({i, j});
else edges.insert({j, i});
}
}
int matn = matrix.size();
for(int i = 0; i < matn-1; ++i) {
for(int j = 0; j < order.size(); ++j) {
int u = matrix[i][j], v = matrix[i+1][j];
if(layer[u] > layer[v]) std::swap(u, v);
edges.erase({u, v});
}
}
for(auto [u, v] : edges) {
matrix[3*layer[u]-2][start[u]] = v;
start[u] += 2;
}
return matrix;
}
/*int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::vector<std::vector<int>> matrix = create_map(9, 8, {1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 5, 6, 7, 8, 9});
for(int i = 0; i < matrix.size(); ++i) {
for(int j = 0; j < matrix[i].size(); ++j) {
std::cout << matrix[i][j] << " ";
}
std::cout << "\n";
}
}*/
