#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vector<vi> create_map(int n, int m, vi a, vi b) {
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]);
}
// Duyệt DFS xây cây
vector<int> parent(n + 1, 0);
vector<vi> child(n + 1);
function<void(int)> dfs = [&](int u) {
for (int v : adj[u]) {
if (v == parent[u]) continue;
if (parent[v]) continue;
parent[v] = u;
child[u].push_back(v);
dfs(v);
}
};
parent[1] = -1;
dfs(1);
// Euler tour
vi ord;
function<void(int)> dfs_euler = [&](int u) {
ord.push_back(u);
for (int v : child[u]) {
dfs_euler(v);
ord.push_back(u);
}
};
dfs_euler(1); // kích thước = 2n - 1
// Tạo hàng
vector<vi> rows;
for (int u : ord) rows.push_back({u});
while ((int)rows.size() < 4 * n - 1)
rows.push_back(rows.back());
// Gán màu theo đường chéo
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++];
}
}
// ✅ Bổ sung dòng / cột cuối nếu còn ô chưa tô
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
if (grid[i][j] == 0)
grid[i][j] = 1; // tô tạm bằng màu 1 (đã đảm bảo hợp lệ trước đó)
}
}
return grid;
}
