#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vector<vi> create_map(int n, int m, vi a, vi b)
{
vi c(4 * n - 1), dfs_ord;
vector<vi> adj(n + 1);
for (int i = 0; i < m; i++)
{
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
vector<bool> vis(n + 1, false);
vi depth(n + 1, 0);
vi p(n + 1, -1);
vector<vi> ch(n + 1);
vi tin(n + 1), tout(n + 1);
int time = 0;
function<void(int, int)> dfs1 = [&](int u, int par)
{
vis[u] = 1, p[u] = par, tin[u] = ++time;
for (int v : adj[u])
{
if (vis[v]) continue;
ch[u].push_back(v);
depth[v] = depth[u] + 1;
dfs1(v, u);
}
tout[u] = time;
};
dfs1(1, -1);
int id = 1;
for (int i = 2; i <= n; i++)
if (depth[i] > depth[id])
id = i;
vector<bool> bad(n + 1, false);
while (id != 1)
{
bad[id] = 1;
id = p[id];
}
function<void(int, int)> dfs2 = [&](int u, int par)
{
dfs_ord.push_back(u);
for (int v : ch[u])
if (!bad[v])
{
dfs2(v, u);
dfs_ord.push_back(u);
}
for (int v : ch[u])
if (bad[v])
{
dfs2(v, u);
dfs_ord.push_back(u);
}
};
dfs2(1, -1);
assert(dfs_ord.size() == 2 * n - 1);
vector<vi> need(n + 1);
for (int i = 0; i < m; i++)
{
int u = a[i], v = b[i];
if (u == p[v] || v == p[u]) continue;
if (tin[v] <= tin[u] && tout[v] >= tout[u]){
swap(u, v);
}
need[v].push_back(u);
}
vector<bool> seen(n + 1, false);
assert(need[1].size() == 0);
vector<vi> rows;
for (auto x : dfs_ord)
{
rows.push_back({x});
if (!seen[x] && need[x].size() > 0)
{
rows.push_back(need[x]);
rows.push_back({x});
seen[x] = 1;
}
}
assert(rows.size() <= 4 * n - 1);
while (rows.size() < 4 * n - 1)
rows.push_back(rows.back());
vector<vi> ans(2 * n, vi(2 * n));
for (int i = 0; i < 4 * n - 1; i++)
{
int sz = min(i + 1, 4 * n - i - 1);
assert(sz >= rows[i].size());
assert(rows[i].size() > 0);
while (rows[i].size() < sz)
rows[i].push_back(rows[i].back());
// diag is x + y = i - 1
int p = 0;
for (int x = 0; x < 2 * n; x++)
{
int y = i - x;
if (0 <= y && y < 2 * n)
{
assert(p < rows[i].size());
ans[x][y] = rows[i][p];
++p;
}
}
}
return ans;
}
