#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
const int NMAX = 41;
int adj[NMAX][NMAX];
int visited[NMAX];
int cnt[NMAX]; // cnt[u] := Number of child nodes in DFS-tree of node u (excluding u)
int w[NMAX]; // w[u] := Width of node
int n;
int vtime = 1;
vector<int> children[NMAX];
vector<int> backnodes[NMAX];
int dfs0(int u, int p) {
visited[u] = vtime++;
int childs = 0;
for (int v = 1; v <= n; ++v) {
if (v == u || !adj[u][v]) {continue;}
if (visited[v] && visited[v] < visited[u] && v != p) {
backnodes[v].push_back(u);
}
if (!visited[v]) {
children[u].push_back(v);
childs += dfs0(v, u);
}
}
cnt[u] = childs;
return childs + 1;
}
void dfs1(int u, int left, int right, int row, vector<vector<int>>& ma) {
const int MSIZE = ma.size();
visited[u] = true;
// Current color: u
// Fill parent rows in checkerboard pattern
bool up = true;
for (int i = left; i <= right; ++i) {
int rcurr = row + (1 - up);
ma[rcurr][i] = u;
up = !up;
}
for (int r = row+1; r < MSIZE; ++r) {
ma[r][left] = u;
ma[r][right] = u;
}
// Add backedge nodes in strip
int idx = left+1;
for (auto& bnode : backnodes[u]) {
ma[row][idx] = bnode;
if (row-1 >= 0) {
ma[row-1][idx] = u;
}
idx += 2;
}
// Fill empty space
for (int r = row; r < row+2; ++r) {
for (int c = left; c <= right; ++c) {
ma[r][c] = max(u, ma[r][c]);
}
}
int lbound = left+1;
for (int v : children[u]) {
// Children draws from [lbound ... lbound + w[v]-1]
dfs1(v, lbound, lbound+w[v]-1, row+2, ma);
// Draw separating border of parent node if more than 1 child
// If lbound
if (lbound+w[v] < right) {
for (int r = row; r < MSIZE; ++r) {
ma[r][lbound+w[v]] = max(ma[r][lbound+w[v]],u);
}
}
lbound += w[v]+1;
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
// Initialize
vtime = 1;
n = N;
for (int u = 1; u <= n; ++u) {
backnodes[u].clear();
visited[u] = 0;
cnt[u] = 0;
w[u] = 0;
children[u].clear();
for (int v = 1; v <= n; ++v) {
adj[u][v] = adj[v][u] = 0;
}
}
for (int i = 0; i < M; ++i) {
int u = A[i];
int v = B[i];
adj[u][v] = 1;
adj[v][u] = 1;
}
dfs0(1, -1);
vector<vector<int>> rmap(2*n, vector<int>(2*n,0));
for (int u = 1; u <= n; ++u) {
w[u] = 2*cnt[u] + 1;
}
for (int i = 1; i <= n; ++i) {visited[i] = 0;}
dfs1(1,0,w[1]-1,0,rmap);
// Fill every empty spot with color of root
for (int y = 0; y < 2*n; ++y) {
for (int x = 0; x < 2*n; ++x) {
rmap[y][x] = max(1, rmap[y][x]);
}
}
return rmap;
}
