#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vector<vi> create_map(int N, int M, vi A, vi B) {
vector<vector<bool>> adj(N + 1, vector<bool>(N + 1, false));
for (int i = 0; i < M; i++) {
adj[A[i]][B[i]] = adj[B[i]][A[i]] = true;
}
int K = 4 * N;
vector<vi> grid(K, vi(K, 0));
queue<pair<int, int>> q;
// Gieo hạt ban đầu
for (int i = 1; i <= N; i++) {
int r = 3 * (i - 1), c = 3 * (i - 1);
grid[r][c] = i;
q.emplace(r, c);
}
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
auto can_color = [&](int r, int c, int color) {
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
int k = grid[nr][nc];
if (k != 0 && !adj[color][k]) return false;
}
return true;
};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
int col = grid[r][c];
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
if (grid[nr][nc] == 0 && can_color(nr, nc, col)) {
grid[nr][nc] = col;
q.emplace(nr, nc);
}
}
}
// Điền ô trống còn lại nếu có
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
if (grid[r][c] == 0) {
for (int col = 1; col <= N; col++) {
if (can_color(r, c, col)) {
grid[r][c] = col;
break;
}
}
}
}
}
return grid;
}
