#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 44;
int k;
int n;
vector<vector<int>> mp;
int adj[N][N];
int vis[N];
int cur;
int diag[N];
void fill_current(int col){
for (int i=0; i<k; i++)
for (int j=0; j<k; j++)
if (j-i == cur) mp[i][j] = col;
cur++;
}
void fill_neighbors(int idx){
vector<int> ng; for (int i=1; i<=n; i++) if (adj[idx][i]) ng.push_back(i);
while (ng.size() < k) ng.push_back(idx);
int nid = 0;
for (int i=0; i<k; i++)
for (int j=0; j<k; j++)
if (j-i == diag[idx]) mp[i][j] = ng[nid++];
}
void dfs(int nw){
vis[nw] = 1;
fill_current(nw);
diag[nw] = cur++;
fill_current(nw);
for (int c=0; c<=n; c++){
if (!adj[c][nw] || vis[c]) continue;
dfs(c);
fill_current(nw);
}
}
std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> a, std::vector<int> b) {
k = 2*n; ::n = n;
mp.assign(k, vector<int> (k,0));
for (int i=0; i<N; i++) for (int j=0; j<N; j++) adj[i][j] = 0;
for (int i=0; i<m; i++) adj[a[i]][b[i]] = 1, adj[b[i]][a[i]] = 1;
for (int i=0; i<N; i++) vis[i] = 0;
cur = -k+1;
dfs(1);
vector<pair<int,int>> nd;
for (int i=1; i<=n; i++) nd.push_back({abs(diag[i]), i});
sort(nd.begin(), nd.end());
for (auto [_, idx]: nd){
fill_neighbors(idx);
for (int i=1; i<=n; i++) adj[i][idx] = 0, adj[idx][i] = 0;
}
return mp;
}
