#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
// Hàm tạo bản đồ thỏa mãn các điều kiện đề bài
vector<vi> create_map(int N, int M, vi A, vi B) {
// Danh sách kề dạng ma trận
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; // K vừa đủ với N <= 15
vector<vi> grid(K, vi(K, 0));
queue<pair<int, int>> q;
// Bước 1: Gieo hạt ban đầu cho mỗi quốc gia
for (int i = 1; i <= N; i++) {
int r = 3 * (i - 1), c = 3 * (i - 1);
grid[r][c] = i;
q.emplace(r, c);
}
// Hàm kiểm tra có thể tô màu tại (r,c) không
auto can_color = [&](int r, int c, int color) {
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
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 neighbor = grid[nr][nc];
if (neighbor != 0 && !adj[color][neighbor]) return false;
}
return true;
};
// Bước 2: Multi-source BFS để lan màu
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
int color = grid[r][c];
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
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, color)) {
grid[nr][nc] = color;
q.emplace(nr, nc);
}
}
}
// Bước 3: Điền các ô còn trống (hiếm gặp)
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
if (grid[r][c] == 0) {
for (int color = 1; color <= N; color++) {
if (can_color(r, c, color)) {
grid[r][c] = color;
break;
}
}
}
}
}
// ============================
// KIỂM TRA ĐẦU RA (ASSERTIONS)
// ============================
// Điều kiện 1: Mỗi quốc gia phải xuất hiện ít nhất một lần
vector<bool> used(N + 1, false);
for (int r = 0; r < K; r++)
for (int c = 0; c < K; c++) {
int color = grid[r][c];
assert(1 <= color && color <= N);
used[color] = true;
}
for (int i = 1; i <= N; i++) assert(used[i]);
// Điều kiện 2: Mỗi cặp (A[i], B[i]) phải có ít nhất một cặp ô liền kề
set<pair<int, int>> required;
for (int i = 0; i < M; i++) {
required.insert({A[i], B[i]});
required.insert({B[i], A[i]});
}
set<pair<int, int>> seen;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
int u = 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;
int v = grid[nr][nc];
if (u != v) {
seen.insert({u, v});
}
}
}
}
for (int i = 0; i < M; i++) {
assert(seen.count({A[i], B[i]}) || seen.count({B[i], A[i]}));
}
// Điều kiện 3: Không được có cặp màu khác nhau cạnh nhau nếu không nằm trong danh sách
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
int u = 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;
int v = grid[nr][nc];
if (u != v) {
assert(adj[u][v]); // chỉ được phép kề nếu có liên kết
}
}
}
}
return grid;
}
