#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vector<vi> create_map(int n, int m, vi a, vi b) {
// Khởi tạo đồ thị
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]);
}
// Xây cây DFS
vector<bool> vis(n + 1, false);
vi depth(n + 1, 0), p(n + 1, -1), tin(n + 1), tout(n + 1);
vector<vi> ch(n + 1);
int time = 0;
function<void(int, int)> dfs1 = [&](int u, int par) {
vis[u] = true; 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);
// Đánh dấu đường dài nhất về gốc là back-path
int id = 1;
for (int i = 2; i <= n; i++)
if (depth[i] > depth[id]) id = i;
vector<bool> back(n + 1, false);
while (id != 1) {
back[id] = true;
id = p[id];
}
// Tạo DFS Euler Order
vi dfs_ord;
function<void(int, int)> dfs2 = [&](int u, int par) {
dfs_ord.push_back(u);
for (int v : ch[u])
if (!back[v]) {
dfs2(v, u);
dfs_ord.push_back(u);
}
for (int v : ch[u])
if (back[v]) {
dfs2(v, u);
dfs_ord.push_back(u);
}
};
dfs2(1, -1);
assert((int)dfs_ord.size() == 2 * n - 1);
// Tìm các back edges (cạnh không thuộc cây DFS)
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);
}
// Tạo rows theo thứ tự DFS
vector<vi> rows;
vector<bool> seen(n + 1, false);
for (int u : dfs_ord) {
rows.push_back({u});
if (!seen[u] && !need[u].empty()) {
rows.push_back(need[u]);
rows.push_back({u});
seen[u] = true;
}
}
// Đảm bảo đúng 4n − 1 hàng
while ((int)rows.size() < 4 * n - 1)
rows.push_back(rows.back());
// Tạo bản đồ 4n x 4n
int K = 4 * n;
vector<vi> grid(K, vi(K, 0));
for (int i = 0; i < 4 * n - 1; i++) {
int len = min(i + 1, 4 * n - 1 - i);
while ((int)rows[i].size() < len)
rows[i].push_back(rows[i].back());
int p = 0;
for (int x = 0; x < K; x++) {
int y = i - x;
if (0 <= y && y < K && p < (int)rows[i].size()) {
grid[x][y] = rows[i][p++];
}
}
}
// Lấp các ô chưa tô màu
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++)
if (grid[i][j] == 0) grid[i][j] = 1;
return grid;
}
