#include "worldmap.h"
#include <vector>
using namespace std;
struct Graph {
int n;
vector<vector<int>> adj;
vector<vector<int>> ch; // child in dfs tree
vector<int> lvl;
vector<int> w;
vector<vector<int>> back_dn; // back-edges down
Graph (int _n) : n(_n),
adj(_n, vector<int> (0)),
ch(_n, vector<int> (0)),
lvl(_n, 0),
w(_n, 0),
back_dn(_n, vector<int> (0)) { }
void add_edge (int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs (int u, int p) {
lvl[u] = lvl[p] + 1;
w[u] = 0;
for (int nxt : adj[u]) {
if (lvl[nxt] == 0) {
ch[u].push_back(nxt);
dfs(nxt, u);
w[u] += w[nxt];
} else if (lvl[nxt] > lvl[u]) {
back_dn[u].push_back(nxt);
}
}
if (ch[u].empty()) {
w[u] = 1;
} else {
w[u] += 1 + ch[u].size();
}
}
};
struct Canvas {
int k;
vector<vector<int>> grid;
Canvas (int _k, int init) : k(_k), grid(_k, vector<int> (_k, init)) { }
void fill_teeth (int x1, int x2, int y1, int y2, int c) {
for (int j = y1; j < y2; j += 2)
grid[x1][j] = c;
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1; j < y2; j++) {
grid[i][j] = c;
}
}
}
void fill (int x1, int x2, int y1, int y2, int c) {
for (int i = x1; i < x2; i++) {
for (int j = y1; j < y2; j++) {
grid[i][j] = c;
}
}
}
void dot (int x, int y, int c) {
grid[x][y] = c;
}
};
void draw (int u, int x1, int x2, int y1, int y2, Canvas &C, const Graph &G) {
C.fill_teeth(x1, x2, y1, y2, u);
int bey = y1 + 2;
for (int v : G.back_dn[u]) {
C.dot(x1 + 1, bey, v);
bey += 2;
}
int chy = y1 + 1;
for (int v : G.ch[u]) {
draw(v, x1 + 2, x2, chy, chy + G.w[v], C, G);
chy += G.w[v] + 1;
}
}
vector<vector<int>> create_map (int n, int m, vector<int> A, vector<int> B) {
Graph G (n + 1);
for (int i = 0; i < m; i++) {
G.add_edge(A[i], B[i]);
}
G.dfs(1, 1);
Canvas C (2 * n, 1);
draw(1, 0, C.k, 0, C.k, C, G);
return C.grid;
}
