//testing Ai code
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
class WorldMapCreator {
public:
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
// Build adjacency list for the country graph
vector<set<int>> adj(N + 1);
for (int i = 0; i < M; ++i) {
adj[A[i]].insert(B[i]);
adj[B[i]].insert(A[i]);
}
// Compute degrees
vector<int> degree(N + 1, 0);
for (int i = 1; i <= N; ++i) {
degree[i] = adj[i].size();
}
// Special case: subtask 1 (path graph)
if (M == N - 1 && N > 1) {
bool is_path = true;
for (int i = 1; i <= N; ++i) {
if (degree[i] > 2) {
is_path = false;
break;
}
}
if (is_path) {
return create_path_map(N, A, B);
}
}
// Special case: subtask 3 (M=4)
if (M == 4) {
return create_small_map(N, adj);
}
// Special case: subtask 4 (star-like: country 1 connected to all)
if (adj[1].size() == N - 1) {
return create_star_map(N, adj);
}
// General case: try to achieve K <= 2*N (aim for R <= 2)
int target_K = max(2, min(240, 2 * N));
return create_compact_map(N, adj, target_K);
}
private:
// Create map for path graph (subtask 1 & 2 when applicable)
vector<vector<int>> create_path_map(int N, vector<int>& A, vector<int>& B) {
vector<vector<int>> grid(2, vector<int>(N, 0));
// Place countries in order: 1,2,3,...,N
for (int i = 0; i < N; ++i) {
grid[0][i] = i + 1;
grid[1][i] = i + 1;
}
return grid; // 2 x N grid
}
// Create small map for M=4
vector<vector<int>> create_small_map(int N, vector<set<int>>& adj) {
if (N <= 4) {
// Try 2x2 if possible
vector<vector<int>> grid = {
{1, 2},
{3, 4}
};
if (validate_map(grid, N, adj)) {
return grid;
}
}
// Fall back to general compact
return create_compact_map(N, adj, 2 * N);
}
// Create star map (country 1 connected to all)
vector<vector<int>> create_star_map(int N, vector<set<int>>& adj) {
int K = (int)ceil(sqrt(N));
vector<vector<int>> grid(K, vector<int>(K, 1)); // Fill with country 1
int idx = 0;
for (int i = 2; i <= N; ++i) {
int r = idx / K;
int c = idx % K;
if (r < K) {
grid[r][c] = i;
}
++idx;
}
// Ensure all neighbors of 1 touch it
// Already satisfied since 1 is everywhere else
return grid;
}
// General compact map: place countries in 2 rows, snake pattern
vector<vector<int>> create_compact_map(int N, vector<set<int>>& adj, int max_K) {
int K = min(max_K, 240);
int rows = 2;
int cols = (N + 1) / 2;
if (cols > K) {
cols = K;
rows = (N + K - 1) / K;
}
if (rows * cols < N) {
rows = (N + K - 1) / K;
}
vector<vector<int>> grid(rows, vector<int>(K, 0));
vector<pair<int, int>> positions(N + 1, {-1, -1});
int country = 1;
// Place countries in snake order
for (int r = 0; r < rows && country <= N; ++r) {
int start_c = (r % 2 == 0) ? 0 : K - 1;
int end_c = (r % 2 == 0) ? K : -1;
int step = (r % 2 == 0) ? 1 : -1;
for (int c = start_c; (step > 0 ? c < end_c : c > end_c) && country <= N; c += step) {
grid[r][c] = country;
positions[country] = {r, c};
++country;
}
}
// Fill remaining cells with country 1 (or any high-degree country)
int filler = 1;
for (int i = 1; i <= N; ++i) {
if (adj[i].size() > adj[filler].size()) {
filler = i;
}
}
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < K; ++c) {
if (grid[r][c] == 0) {
grid[r][c] = filler;
}
}
}
// If validation fails, expand
if (!validate_map(grid, N, adj)) {
return create_expanded_map(N, adj);
}
return grid;
}
// Fallback: larger map with clear borders
vector<vector<int>> create_expanded_map(int N, vector<set<int>>& adj) {
int side = (int)ceil(sqrt(N));
int K = max(side + 2, min(240, N + 10)); // Extra border
vector<vector<int>> grid(K, vector<int>(K, 0));
// Place countries in grid
int idx = 0;
for (int i = 1; i <= N; ++i) {
int r = 1 + (idx / side);
int c = 1 + (idx % side);
grid[r][c] = i;
++idx;
}
// Flood fill borders with high-degree country
int border_country = 1;
for (int i = 1; i <= N; ++i) {
if (adj[i].size() > adj[border_country].size()) {
border_country = i;
}
}
for (int r = 0; r < K; ++r) {
for (int c = 0; c < K; ++c) {
if (grid[r][c] == 0) {
grid[r][c] = border_country;
}
}
}
return grid;
}
// Validate the map
bool validate_map(const vector<vector<int>>& grid, int N, const vector<set<int>>& adj) {
int K = grid.size();
if (K == 0) return false;
// Check all countries used
vector<bool> used(N + 1, false);
for (const auto& row : grid) {
for (int c : row) {
if (c < 1 || c > N) return false;
used[c] = true;
}
}
for (int i = 1; i <= N; ++i) {
if (!used[i]) return false;
}
// Check required adjacencies
vector<vector<bool>> observed_adj(N + 1, vector<bool>(N + 1, false));
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -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];
int nc = c + dc[d];
if (nr >= 0 && nr < K && nc >= 0 && nc < K) {
int v = grid[nr][nc];
if (u != v) {
observed_adj[u][v] = true;
observed_adj[v][u] = true;
}
}
}
}
}
// All required edges must be observed
for (int u = 1; u <= N; ++u) {
for (int v : adj[u]) {
if (!observed_adj[u][v]) {
return false;
}
}
}
// No forbidden adjacencies
for (int u = 1; u <= N; ++u) {
for (int v = u + 1; v <= N; ++v) {
if (adj[u].count(v) == 0 && observed_adj[u][v]) {
return false;
}
}
}
return true;
}
};
// Global function required by judge
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
WorldMapCreator solver;
return solver.create_map(N, M, A, B);
}
