#include <vector>
#include <set>
#include <algorithm>
#include "worldmap.h"
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
int K = N * 7; // Đảm bảo R = K / N > 6 ⇒ "phá" subtask 6
std::vector<std::vector<int>> grid(K, std::vector<int>(K, 0));
// Tập hợp các cặp liền kề hợp lệ
std::set<std::pair<int, int>> neighbor_set;
for (int i = 0; i < M; ++i) {
neighbor_set.insert({A[i], B[i]});
neighbor_set.insert({B[i], A[i]});
}
// Tô từng cặp liền kề vào các vùng không giao nhau
int row = 0;
for (int i = 0; i < M; ++i) {
int a = A[i], b = B[i];
// Vị trí riêng biệt, đảm bảo không chạm các ô khác
int col = 0;
grid[row][col] = a;
grid[row][col + 1] = b;
row += 3; // cách dòng để không chạm nhau
}
// Tô mỗi quốc gia còn thiếu ít nhất 1 lần
std::vector<bool> seen(N + 1, false);
for (int i = 0; i < K; ++i)
for (int j = 0; j < K; ++j)
if (grid[i][j] != 0)
seen[grid[i][j]] = true;
row = K - 1;
for (int c = 1; c <= N; ++c) {
if (!seen[c]) {
grid[row][c] = c;
}
}
// Tô toàn bộ ô còn lại bằng quốc gia 1
for (int i = 0; i < K; ++i)
for (int j = 0; j < K; ++j)
if (grid[i][j] == 0)
grid[i][j] = 1;
// Đảm bảo: mỗi ô liền kề có màu khác đều là cặp hợp lệ
for (int i = 0; i < K; ++i) {
for (int j = 0; j < K; ++j) {
if (i + 1 < K && grid[i][j] != grid[i + 1][j]) {
if (!neighbor_set.count({grid[i][j], grid[i + 1][j]})) {
// Nếu là cặp không hợp lệ ⇒ sửa lại thành cùng màu
grid[i + 1][j] = grid[i][j];
}
}
if (j + 1 < K && grid[i][j] != grid[i][j + 1]) {
if (!neighbor_set.count({grid[i][j], grid[i][j + 1]})) {
grid[i][j + 1] = grid[i][j];
}
}
}
}
return grid;
}
