#include "worldmap.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<int> edges[45];
int h[45];
struct RectBoard
{
RectBoard(int c, int s) : color(c), sz(s) {}
int color;
int sz;
~RectBoard()
{
for (auto& [k, p] : childs)
delete p;
}
vector<pair<ii, RectBoard*>> childs;
void paint(vector<vector<int>>& res, int x, int y)
{
for (int i = x; i < x + sz; i++)
for (int j = y; j < y + sz; j++)
res[i][j] = color;
for (auto& [p, c] : childs)
c->paint(res, x + p.xx, y + p.yy);
}
};
RectBoard* dfs(int root)
{
vector<int> backEdges;
vector<RectBoard*> childBoards;
for (auto& c : edges[root])
{
if (h[c] != -1)
{
// back edge 여부 체크
if (h[c] > h[root])
backEdges.push_back(c);
}
else
{
h[c] = h[root] + 1;
childBoards.push_back(dfs(c));
}
}
// leaf node
if (childBoards.empty())
return new RectBoard(root, 1);
// 자식을 한 칸씩 띄고 배치할 수 있을 만큼으로 크기 지정
int childSz = childBoards.size();
int childMax = 0;
for (auto& c : childBoards)
{
childSz += c->sz;
childMax = max(childMax, c->sz);
}
int backEdgeSz = backEdges.size() * 2;
if (!backEdges.empty())
childMax += 3;
auto sz = max({ backEdgeSz, childSz, childMax });
auto res = new RectBoard(root, sz);
int x = 0, y = 0;
for (auto& c : childBoards)
{
res->childs.emplace_back(ii(x, y), c);
x += c->sz + 1;
}
x = 0;
y = sz - 2;
for (auto& b : backEdges)
{
res->childs.emplace_back(ii(x, y), new RectBoard(b, 1));
x += 2;
}
return res;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
for (int i = 1; i <= N; i++)
edges[i].clear();
memset(h, -1, sizeof(h));
for (int i = 0; i < M; i++)
{
edges[A[i]].push_back(B[i]);
edges[B[i]].push_back(A[i]);
}
h[1] = 0;
auto res = dfs(1);
vector<vector<int>> ans(res->sz, vector<int>(res->sz));
res->paint(ans, 0, 0);
delete res;
return ans;
}
