#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pp pair<int, int>
#define ppp pair<pp, int>
#define pp4 pair<pp, pp>
#define pp3 pair<ll, pair<int, int> >
#define mat vector<vector<int>>
#define fi first
#define se second
#define mod 1000000007
#define inf 2000000001
#define esp 1e-9
#define BLOCK 333
#define BITNUM 555
#define BASE 180518
typedef long long ll;
// const ll oo = (ll)1e18 + 1;
using namespace std;
mat concat_cols(const std::vector<mat>& childs, int parent) {
int mx = 0;
for (const auto& ch : childs) {
mx = std::max(mx, (int)ch.size());
}
mat ans;
for (int i = 0; i < mx; i++) {
std::vector<int> row;
for (const auto& ch : childs) {
int ncols = ch.empty() ? 0 : (int)ch[0].size();
row.push_back(parent);
for (int j = 0; j < ncols; j++) {
if (i >= (int)ch.size()) row.push_back(parent);
else row.push_back(ch[i][j]);
}
}
row.push_back(parent);
ans.push_back(std::move(row));
}
return ans;
}
mat concat_rows(const vector<mat>& childs, int parent) {
int mx = 0;
for (const auto &ch: childs) {
mx = max(mx, (int) ch[0].size());
}
// for (const auto& ch : childs) {
// for (auto row: ch) {
// for (int x: row) cout << x << " , ";
// cout << "\n";
// }
// cout << "====\n";
// }
mat ans;
for (const auto& ch : childs) {
for (auto row: ch) {
vector<int> concat_row = row;
while ((int) concat_row.size() < mx) {
concat_row.push_back(parent);
}
ans.push_back(std::move(concat_row));
}
}
return ans;
}
set<int> generated;
vector<vector<int>> generate(int parent, vector<vector<int>> &adj, ll mask) {
if (generated.count(parent)) {
return {{parent}};
}
generated.insert(parent);
vector<int> childs;
for (int c: adj[parent]) {
// not visited
if (!((mask >> c) & 1)) {
childs.push_back(c);
}
}
// no childs
if (childs.size() == 0) {
return {{parent}};
}
vector<mat> child_maps;
for (int c: childs) {
auto child_map = generate(c, adj, mask | (1ll << parent));
child_maps.push_back(child_map);
}
sort(child_maps.begin(), child_maps.end(), [&](auto c1, auto c2){
return c1[0].size() > c2[0].size();
});
// zip them
int m = (int) child_maps.size();
int w = max(1, (int) sqrt(m));
// cout << "parent: " << parent << "size = " << m << "\n";
vector<mat> rows;
for (int i = 0; i < m; i += w) {
int l = i;
int r = min(m - 1, i + w - 1);
// cout << "play[ " << l << ", " << r << " ]\n";
vector<mat> subs;
for (int j = l; j <= r; j++) subs.push_back(child_maps[j]);
mat center = concat_cols(subs, parent);
int col = (int)center[0].size();
mat ret;
vector<int> last_row(col, parent);
ret.push_back(std::move(last_row));
for (auto r: center) ret.push_back(r);
ret.push_back(std::move(last_row));
rows.push_back(ret);
}
// // temp concat all
// mat ret = concat_cols(child_maps, parent);
// int col = (int)ret[0].size();
// vector<int> last_row(col, parent);
// ret.push_back(std::move(last_row));
// return ret;
return concat_rows(rows, parent);
}
mat create_full_map(int N, mat &adj) {
int mx = N + N;
mat ret(mx, vector<int>(mx, 0));
for (int i = 0; i < N; i++) {
int idx = 0;
for (auto c: adj[i]) {
ret[i][idx] = i;
ret[i][idx + 1] = c;
idx += 2;
}
}
for (int i = 0; i < mx; i++)
for (int j = 0; j < mx; j++)
ret[i][j]++;
return ret;
}
mat create_one_map(int N, vector<pp> edge) {
int idx = 0;
int m = edge.size();
vector<vector<int>> ret(4 * N, vector<int>(4 * N, 0));
for (int i = 0; i < N; i++) {
if (idx >= m) break;
int st = (i & 1) ? 0 : 2;
for (int j = 0; j < N; j++) {
if (idx >= m) break;
ret[i][st] = edge[idx].first;
ret[i][st + 1] = edge[idx].second;
idx++;
st += 4;
}
}
for (int i = 0; i < 4 * N; i++)
for (int j = 0; j < 4 * N; j++)
ret[i][j]++;
return ret;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
generated.clear();
vector<vector<int>> adj(N, vector<int>());
for (int i = 0; i < M; i++) {
int u = A[i], v = B[i];
u--;
v--;
adj[u].pb(v);
adj[v].pb(u);
}
if (M == N * (N - 1) / 2) {
return create_full_map(N, adj);
}
if (adj[0].size() == N - 1) {
vector<pp> edge;
for (int i = 0; i < M; i++) edge.push_back({A[i] - 1, B[i] - 1});
return create_one_map(N, edge);
}
auto rec_map = generate(0, adj, 1);
int h = rec_map.size();
int w = rec_map[0].size();
int mx = max(h, w);
vector<vector<int>> ret(mx, vector<int>(mx, 0));
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
ret[i][j] = rec_map[i][j];
for (int i = 0; i < mx; i++)
for (int j = 0; j < mx; j++)
ret[i][j]++;
return ret;
}
