#pragma GCC optimize("O3")
//#include "worldmap.h"
#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;
visited[u] = 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]+2;
std::vector<std::vector<int>> matrix(2*n, std::vector<int>(2*n, -1));
/*
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;
}*/
for(int i = 0; i < order.size(); ++i) matrix[2*n-1][i] = order[i];
for(int i = 0; i < order.size(); ++i) {
if(layer[order[i]] == mdepth) order[i] = par[order[i]];
}
--mdepth;
int crow = 2*n-2;
while(mdepth) {
for(int i = 0; i < order.size(); ++i) {
if(layer[order[i]] == mdepth) {
if(i > tin[order[i]] && i < tout[order[i]]) matrix[crow][i] = order[i];
else matrix[crow][i] = par[order[i]];
} else {
matrix[crow][i] = order[i];
}
}
--crow;
for(int i = 0; i < order.size(); ++i) {
if(layer[order[i]] == mdepth) {
if((tin[order[i]]%2) == (i%2)) matrix[crow][i] = order[i];
else matrix[crow][i] = par[order[i]];
} else {
matrix[crow][i] = order[i];
}
}
--crow;
for(int i = 0; i < order.size(); ++i) {
if(layer[order[i]] == mdepth) order[i] = par[order[i]];
}
--mdepth;
}
for(int i = 0; i < 2*n; ++i) {
for(int j = 0; j < 2*n; ++j) {
if(matrix[i][j] == -1 || matrix[i][j] == 0) matrix[i][j] = 1;
}
}
//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; ++i) {
while(matrix[i].size() < matn) matrix[i].push_back(matrix[i][matrix[i].size()-1]);
}
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});
}
}
if(matn < matrix[0].size()) {
while(matn < matrix[0].size()) {
matrix.push_back(matrix[matn-1]);
++matn;
}
}
for(auto [u, v] : edges) {
matrix[2*layer[u]-1][start[u]] = v;
start[u] += 2;
}
return matrix;
}
/*
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t;
std::cin >> t;
while(t--) {
int n, m;
std::cin >> n >> m;
std::vector<int> a(m), b(m);
for(int i = 0; i < m; ++i) std::cin >> a[i] >> b[i];
std::vector<std::vector<int>> matrix = create_map(n, m, a, b);
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";
}
std::cout << "\n";
}
}*/
///opt/homebrew/bin/g++-14
