#include <bits/stdc++.h>
using namespace std;
// Subtask 5 solution: N <= 15, any K <= 240 works. We choose K = 4*N.
// Build multi-source BFS from seeds to color grid satisfying adjacency constraints.
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
// 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;
}
int K = 4 * N;
vector<vector<int>> grid(K, vector<int>(K, 0));
queue<pair<int,int>> q;
// Place initial seeds for each country at (3*(i-1), 3*(i-1))
for(int i = 1; i <= N; i++){
int r = 3*(i-1);
int 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 col){
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[col][k]) return false;
}
return true;
};
// Multi-source BFS
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);
}
}
}
// Fill any remaining zeros with a valid color
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;
}
