#include <bits/stdc++.h>
int rt;
std::vector <std::vector <int>> maxdia(const std::vector <std::vector <int>>& g) {
auto dia = [] (const std::vector <std::vector <int>>& t, int r) -> int {
std::vector <int> d(t.size());
d.assign(t.size(), -1);
std::queue <int> q;
q.push(r);
d[r] = 0;
int mx = 0;
while (q.size()) {
int v = q.front();
q.pop();
for (int x : t[v]) {
if (d[x] != -1) continue;
mx = std::max(mx, d[x] = d[v] + 1);
q.push(x);
}
}
for (int j = 0; j < (int) t.size(); j++) if (d[j] == mx) r = j;
return r;
};
std::vector <std::vector <int>> res;
int bst = -1;
for (int i = 0; i < (int) g.size(); i++) {
std::vector <std::vector <int>> t(g.size());
std::vector <bool> vis(g.size(), false);
auto dfs = [&] (auto&& self, int node) -> void {
vis[node] = true;
for (int x : g[node]) {
if (vis[x]) continue;
t[node].push_back(x);
t[x].push_back(node);
self(self, x);
}
};
dfs(dfs, i);
int now = dia(t, i);
if (now > bst) bst = now, res = t, rt = i;
}
return res;
}
struct Line {
bool wide = false;
int who = -1;
std::vector <int> nei;
bool canskip = false;
};
std::vector <std::vector <int>> create_map(int n, int m, std::vector <int> a, std::vector <int> b) {
if (n == 1) return { { 1 } };
std::vector <std::vector <int>> g(n);
for (int i = 0; i < m; i++) {
g[--a[i]].push_back(--b[i]);
g[b[i]].push_back(a[i]);
}
auto t = maxdia(g);
std::vector <Line> lines;
// std::cerr << "rt = " << rt << std::endl;
// for (int i = 0; i < n; i++) {
// std::cerr << i << ":";
// for (int x : t[i]) std::cerr << " " << x;
// std::cerr << std::endl;
// }
// assert(t[rt].size() == 1);
std::vector <int> d(n, -1);
{
std::queue <int> q;
q.push(0);
while (q.size()) {
int v = q.front();
q.pop();
for (int x : t[v]) if (d[x] == -1) d[x] = d[v] + 1, q.push(x);
}
}
std::vector <bool> vis(n, false);
auto dfs = [&] (auto&& self, int node, int par = -1) -> void {
std::sort(t[node].begin(), t[node].end(), [&] (int u, int v) -> bool { return d[u] < d[v]; });
vis[node] = true;
Line line;
bool leafnei = false;
for (int x : t[node]) if (t[x].size() == 1) leafnei = true;
if (g[node].size() == t[node].size() && !leafnei) {
line.wide = false;
line.who = node;
} else {
line.wide = true;
line.who = node;
for (int x : g[node]) {
if (vis[x]) continue;
line.nei.push_back(x);
}
if (line.nei.empty()) line.wide = false;
}
lines.push_back(line);
for (int x : t[node]) {
if (x == par) continue;
if (t[x].size() == 1) continue;
self(self, x, node);
lines.push_back({ false, node, { }, true });
}
};
if (g[rt].size() == 1) dfs(dfs, t[rt][0], rt);
else dfs(dfs, rt, -1);
std::vector <int> cnt(n, 0);
for (const Line& line : lines) cnt[line.who]++;
// std::cerr << lines.size() << " lines before pruning" << std::endl;
while (!lines.back().wide && cnt[lines.back().who] > 1) cnt[lines.back().who]--, lines.pop_back();
// std::cerr << lines.size() << " lines after pruning" << std::endl;
// assert(lines.back().wide);
{
std::vector <std::pair <int, int>> sq;
int l, r;
for (l = 0, r = 0; r < (int) lines.size(); r++) {
if (lines[r].wide || !lines[r].canskip) {
if (l == r) {
l++;
continue;
}
sq.emplace_back(l, r - 1);
l = r + 1;
}
}
assert(r == (int) lines.size());
if (l < r) sq.emplace_back(l, r - 1);
std::vector <Line> nlines;
for (int i = 0, j = 0; i < (int) lines.size(); i++) {
if (lines[i].wide || !lines[i].canskip) {
nlines.push_back(lines[i]);
continue;
}
assert(j < (int) sq.size());
assert(sq[j].first == i);
int s = lines[sq[j].first].who;
int e = lines[sq[j].second].who;
if (s == e) {
nlines.push_back(lines[i]);
j++;
continue;
}
std::vector <int> par(n, -1);
std::queue <std::pair <int, int>> q;
q.emplace(s, s);
while (q.size()) {
auto [v, p] = q.front();
q.pop();
if (par[v] != -1) continue;
par[v] = p;
for (int x : g[v]) q.emplace(x, v);
}
// std::cerr << s << " -> " << e << " par:";
// for (int x : par) std::cerr << " " << x;
// std::cerr << std::endl;
std::vector <int> path;
int v = e;
do {
path.push_back(v);
v = par[v];
} while (v != par[v]);
assert(path.back() != s);
path.push_back(s);
while (path.size()) {
Line line;
line.wide = false;
line.who = path.back();
path.pop_back();
nlines.push_back(line);
}
while (i < (int) lines.size() && lines[i].wide == false && lines[i].canskip) i++;
i--;
j++;
}
lines = nlines;
}
const int SZ = n * 2;
std::vector <std::vector <int>> con(241, std::vector <int> (241, -1));
int i = SZ, j = SZ;
int last = -1;
bool first = true;
for (Line line : lines) {
last = line.who;
if (!line.wide) {
first = false;
i = std::min(i, SZ - 1);
j = std::min(j, SZ - 1);
assert(i >= 0 && j >= 0);
for (int k = 0; k <= i; k++) con[k][j] = line.who + 1;
for (int k = 0; k <= j; k++) con[i][k] = line.who + 1;
i--;
j--;
continue;
}
if (i > j) {
for (int k = 0; k <= j; k++) con[i][k] = con[i - 1][k] = con[i - 2][k] = line.who + 1;
for (int k = 0; k < i; k++) con[k][j] = line.who + 1;
i--;
int k = 0;
for (int x : line.nei) {
assert(k < j);
con[i][k] = x + 1;
k += 2;
}
j--;
i -= 2;
if (first) j++;
first = false;
} else {
for (int k = 0; k <= i; k++) con[k][j] = con[k][j - 1] = con[k][j - 2] = line.who + 1;
for (int k = 0; k < j; k++) con[i][k] = line.who + 1;
j--;
int k = 0;
for (int x : line.nei) {
assert(k < i);
con[k][j] = x + 1;
k += 2;
}
i--;
j -= 2;
if (first) i++;
first = false;
}
}
{
std::queue <std::pair <int, int>> q;
q.emplace(0, 0);
while (q.size()) {
auto [I, J] = q.front();
q.pop();
if (con[I][J] != -1) continue;
con[I][J] = last + 1;
q.emplace(I + 1, J);
q.emplace(I, J + 1);
}
}
std::vector <std::vector <int>> ans(SZ, std::vector <int> (SZ, -1));
for (int I = 0; I < SZ; I++)
for (int J = 0; J < SZ; J++)
ans[I][J] = con[I][J];
// for (int I = 0; I < SZ; I++)
// for (int J = 0; J < SZ; J++)
// std::cerr << std::setw(2) << ans[I][J] << " \n"[J + 1 == SZ];
// {
// std::set <std::pair <int, int>> ed;
// for (i = 0; i < m; i++) ed.insert({ a[i], b[i] }), ed.insert({ b[i], a[i] });
// for (i = 0; i < n; i++) ed.insert({ i, i });
// for (i = 0; i < SZ; i++) {
// for (j = 0; j < SZ; j++) {
// if (i + 1 < SZ) assert(ed.contains({ ans[i][j] - 1, ans[i + 1][j] - 1 }));
// if (j + 1 < SZ) assert(ed.contains({ ans[i][j] - 1, ans[i][j + 1] - 1 }));
// }
// }
// }
return ans;
}
