#include "worldmap.h"
using namespace std;
#include <bits/stdc++.h>
int dfs(int u, int row, int col, vector<int>& node_sizes, vector<vector<int>>& adj, vector<vector<int>>& res){
/*
For each node, we wish to determine the size of each of its children
*/
if(u == 6) cout << "GDFIOHJSDFUIOGHJDFGIO";
if(node_sizes[u] != 0) return 0; // skip visited nodes
node_sizes[u] = 1;
// Base case: leaf node
if(adj[u].size() == 1){
//node_sizes[u] = 1;
return 1;
}
// Recursion case
int pos = col + 1;
res[row][col] = u;
for(int v : adj[u]){
int width_v = dfs(v, row+1, pos, node_sizes, adj, res);
if(width_v){
for(int j = pos; j < pos + width_v; j ++){
res[row][j] = v;
}
res[row][pos+width_v] = u;
pos += width_v + 1;
}
}
//node_sizes[u] = pos-col;
return pos - col;
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
// std::vector<std::vector<int>> ans(2 * N, std::vector<int>(2 * N, 1));
// if (M > 0) {
// ans[0][0] = A[0];
// ans[0][1] = B[0];
// }
vector<vector<int>> res(20, vector<int>(20, 0));
for(int i = 0; i < res[0].size(); i ++){
res[0][i] = 1;
}
vector<vector<int>> adj(N+1, vector<int>());
for(int i = 0; i < M; i ++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<int> node_sizes(N+1, 0);
dfs(1, 1, 0, node_sizes, adj, res);
for(int i = 1; i < res.size(); i ++){
for(int j = 0; j < res[i].size(); j ++){
if(res[i][j] == 0){
res[i][j] = res[i-1][j];
}
}
}
return res;
}
/*
1
3 2
1 2
1 3
1
6 5
1 2
1 3
1 4
4 5
4 6
Parents of leaf nodes require 2x+1 horizontal cells
1 1 1 1 1 1 1 1 1 1 1
1 2 1 3 1 4 4 4 4 4 1
0 0 0 0 0 4 5 4 6 4 0
For exmaple, node 1 requires 7 cells.
But let's say, 4 is the parent of 5 6
4 4 4 4 4
4 5 4 6 4
If a node x requires N cells, add N+1 to the number of cells the parent requires.
Finally, add an extra cell to the parent
*/
