#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
int n,K;
int dx[4] = {-1,+1,0,0};
int dy[4] = {0,0,-1,+1};
const int R = 6;
bool con[45][45],needs[45][45];
vector<vector<int>> mat,visited;
vector<int> getord()
{
vector<pair<int,int>> v;
for(int i=1;i<=n;i++)
{
int cnt = 0;
for(int j=1;j<=n;j++)
if(needs[i][j])
cnt++;
v.push_back({-cnt,i});
}
sort(v.begin(),v.end());
vector<int> ord;
for(auto [_,x]:v)
ord.push_back(x);
return ord;
}
bool fill(int x, int y)
{
assert(mat[x][y] == 0);
vector<int> ord = getord();
int mxm=-1,care=-1;
for(int val:ord)
{
bool bun = 1;
int cate = 0;
for(int v=0;v<4;v++)
{
int newx = x + dx[v], newy = y + dy[v];
if(newx < 0 || newx >= K || newy < 0 || newy >= K)
continue;
if(mat[newx][newy] == 0)
continue;
if(!con[mat[newx][newy]][val])
{
bun = 0;
break;
}
if(needs[mat[newx][newy]][val])
cate++;
}
if(bun && cate > mxm)
{
mxm = cate;
care = val;
}
}
if(care == -1)
return 0;
mat[x][y] = care;
for(int v=0;v<4;v++)
{
int newx = x + dx[v], newy = y + dy[v];
if(newx < 0 || newx >= K || newy < 0 || newy >= K)
continue;
if(mat[newx][newy] == 0)
continue;
if(needs[mat[newx][newy]][care])
{
needs[mat[newx][newy]][care] = needs[care][mat[newx][newy]] = 0;
}
}
return 1;
}
bool tot;
void dfs(int x, int y)
{
visited[x][y] = 1;
tot &= fill(x,y);
for(int v=0;v<4;v++)
{
int newx = x + dx[v], newy = y + dy[v];
if(newx < 0 || newx >= K || newy < 0 || newy >= K)
continue;
if(!visited[newx][newy] && mat[newx][newy] == 0)
dfs(newx,newy);
}
}
vector<vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{
n = N;
K = N * R;
mat.clear();
mat.resize(K, vector<int>(K,0));
visited = mat;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
con[i][j] = needs[i][j] = 0;
for(int i=1;i<=N;i++)
con[i][i] = 1;
for(int i=0;i<M;i++)
{
needs[A[i]][B[i]] = needs[B[i]][A[i]] = 1;
con[A[i]][B[i]] = con[B[i]][A[i]] = 1;
}
tot = 1;
dfs(0,0);///K/2, K/2
return mat;
}
/*
1
3 2
1 2
2 3
*/
