#include <bits/stdc++.h>
using namespace std;
/**
* N ≤ 15, M ≤ N*(N−1)/2
* Chạy tối đa 50 lần → O(N^2·K^2) mỗi lần là hoàn toàn ổn với K ~ 4N ≤ 60.
*/
vector<vector<int>> create_map(int N, int M,
vector<int> A, vector<int> B) {
// 1) Build adjacency matrix
vector<vector<bool>> adj(N+1, vector<bool>(N+1, false));
for(int i = 1; i <= N; i++) adj[i][i] = true;
for(int i = 0; i < M; i++){
adj[A[i]][B[i]] = adj[B[i]][A[i]] = true;
}
// 2) Chọn K đủ lớn: ta dùng K = 4*N
int K = 4 * N;
vector<vector<int>> grid(K, vector<int>(K, 0));
// 3) Đặt seed ban đầu cho mỗi quốc gia tại (3*i, 3*i)
queue<pair<int,int>> q;
for(int i = 1; i <= N; i++){
int r = 3*(i-1), c = 3*(i-1);
grid[r][c] = i;
q.emplace(r, c);
}
// 4) Multi‐source BFS
int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
auto can_color = [&](int cr, int cc, int color){
// Đảm bảo với mỗi ô đã tô cạnh (cr,cc), nếu màu là k ≠ color
// thì phải adj[color][k] == true
for(int d = 0; d < 4; d++){
int nr = cr + dr[d], nc = cc + 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) continue;
if(can_color(nr,nc,col)){
grid[nr][nc] = col;
q.emplace(nr,nc);
}
}
}
// 5) Nếu vẫn có ô bỏ trống (cực hiếm, chỉ xảy ra khi bị chặn giữa ba frontier),
// chúng ta điền tuỳ ý bằng một màu sao cho không vi phạm: thử các màu 1..N
for(int r = 0; r < K; r++){
for(int c = 0; c < K; c++){
if(grid[r][c] == 0){
for(int cand = 1; cand <= N; cand++){
if(can_color(r,c,cand)){
grid[r][c] = cand;
break;
}
}
// (về lý thuyết với đồ thị planar và seed đủ phân tán, vòng này hiếm khi chạy)
}
}
}
return grid;
}
