#include <iostream>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
vector<int> g[45], t[45], bck[45];
vector<bool> vis(45);
vector<pair<int, bool>> ord;
vector<int> dep(45), sub(45);
int dfs1(int node, int par) {
vis[node] = sub[node] = 1;
dep[node] = dep[par] + 1;
for (auto x : g[node])
if (!vis[x])
t[node].push_back(x),
t[x].push_back(node),
sub[node] += dfs1(x, node);
return sub[node];
}
void dfs2(int node, int par, bool b) {
ord.push_back({ node, 1 });
int mx = 0, id = 0;
for (auto x : t[node])
if (((x != par) && (sub[x] > mx)))
mx = max(mx, sub[x]), id = x;
for (auto x : t[node])
if(x != par)
if ((x != id) || (!b))
dfs2(x, node, 0), ord.push_back({ node, 0 });
if (id && b) dfs2(id, node, 1);
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
if (n == 1) return { {1} };
for (int i = 0; i < m; ++i)
g[a[i]].push_back(b[i]),
g[b[i]].push_back(a[i]);
dfs1(1, 0);
for (int i = 0; i < m; ++i) {
int u = a[i], v = b[i];
if (dep[u] > dep[v]) swap(u, v);
bck[v].push_back(u);
}
dfs2(1, 0, 1);
vector<vector<int>> res(2 * n, vector<int>(2 * n, 0));
int dg = 0;
for (auto x : ord) {
int node = x.first;
bool nbr = x.second;
int i, j;
if (dg < (2 * n))
i = dg, j = 0;
else
i = 2 * n - 1, j = dg - 2 * n + 1;
while (i >= 0 && (j < (2 * n)))
res[i][j] = node, --i, ++j;
++dg;
if (dg < (2 * n))
i = dg, j = 0;
else
i = 2 * n - 1, j = dg - 2 * n + 1;
if (nbr && (bck[node].size())) {
for (auto nb : bck[node])
res[i][j] = nb, --i, ++j;
if (dg < (2 * n))
i = dg, j = 0;
else
i = 2 * n - 1, j = dg - 2 * n + 1;
while (i >= 0 && (j < (2 * n))) {
if (!res[i][j])
res[i][j] = node;
--i, ++j;
}
++dg;
if (dg < (2 * n))
i = dg, j = 0;
else
i = 2 * n - 1, j = dg - 2 * n + 1;
while (i >= 0 && (j < (2 * n)))
res[i][j] = node, --i, ++j;
++dg;
}
}
for (int i = 1; i < (2 * n); ++i)
for (int j = 1; j < (2 * n); ++j)
if (res[i][j] == 0)
res[i][j] = res[i - 1][j];
ord.clear();
vis.assign(45, 0);
dep.assign(45, 0);
sub.assign(45, 0);
for (int i = 0; i <= n; ++i)
g[i].clear(), t[i].clear(), bck[i].clear();
return res;
}
/*int main() {
int n, m; cin >> n >> m;
vector<int> a(m), b(m);
map<pair<int, int>, bool> mp;
for (int i = 1; i <= n; ++i) mp[{i, i}] = 1;
for (int i = 0; i < m; mp[{a[i], b[i]}] = 1, ++i)
cin >> a[i] >> b[i];
auto res = create_map(n, m, a, b);
cout << res.size() << endl;
for (auto x : res) {
for (auto y : x)
cout << y << " ";
cout << endl;
}
for (int i = 0; i < res.size(); ++i)
for (int j = 0; j < res.size(); ++j) {
if (i < (res.size() - 1))
if (!mp[{res[i + 1][j], res[i][j]}] && !mp[{res[i][j], res[i + 1][j]}])
{
cout << res[i][j] << " " << res[i + 1][j] << endl;
cout << "FAIL!"; return 0;
}
if (j < (res.size() - 1))
if (!mp[{res[i][j + 1], res[i][j]}] && !mp[{res[i][j], res[i][j + 1]}])
{
cout << res[i][j] << " " << res[i + 1][j] << endl;
cout << "FAIL!"; return 0;
}
}
for (int i = 0; i < m; ++i) {
bool ok = 0;
for(int j = 0; j < res.size(); ++j)
for(int k = 0; k < res.size(); ++k)
if (res[j][k] == a[i]) {
int dj[] = { 0, 0, +1, -1 };
int dk[] = { 1, -1, 0, 0 };
for (int d = 0; d < 4; ++d) {
int nj = dj[d] + j, nk = dk[d] + k;
if ((nj >= 0) && (nk >= 0) && (nk < res.size()) && (nj < res.size()))
if (res[nj][nk] == b[i]) ok = 1;
}
}
if(!ok) {
cout << "FAIL!"; return 0;
}
}
cout << "Success!" << endl;
cout << "R = " << (float)res.size() / (float)n << endl;
}*/
