#include "worldmap.h"
#include <cstdlib>
#include <cstring>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int N = 40;
int max(int a, int b) { return a > b ? a : b; }
int n;
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int pp[N], dd[N], ta[N], tb[N], t_;
void dfs1(int p, int i, int d) {
ta[i] = t_++;
pp[i] = p, dd[i] = d;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (dd[j] == -1) {
dfs1(i, j, d + 1);
t_++;
}
}
tb[i] = t_;
}
int cc[N * 2 - 1][N * 2 - 1];
void dfs2(int i) {
for (int x = ta[i]; x < tb[i]; x++)
for (int y = max(dd[i] * 2 - (x - ta[i]) % 2, 0); y < n * 2 - 1; y++)
cc[x][y] = i + 1;
int x = ta[i] + 1, y = dd[i] * 2;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (pp[j] == i)
dfs2(j);
else if (dd[j] > dd[i])
cc[x][y] = j + 1, x += 2;
}
}
vvi create_map(int n_, int m, vi ii, vi jj) {
n = n_;
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
for (int h = 0; h < m; h++) {
int i = ii[h] - 1, j = jj[h] - 1;
append(i, j), append(j, i);
}
memset(dd, -1, n * sizeof *dd);
dfs1(-1, 0, 0);
dfs2(0);
vvi cc_(n * 2 - 1, vi(n * 2 - 1, 0));
for (int x = 0; x < n * 2 - 1; x++)
for (int y = 0; y < n * 2 - 1; y++)
cc_[x][y] = cc[x][y];
return cc_;
}
