#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
ll N,M,K;
vector<vector<ll>> adj;
vector<vector<ll>> fadj;
vector<ll> radj;
vector<ll> tpls;
vector<ll> sts; //subtree size
vector<vector<ll>> gmap(ll r0, ll W, ll H) { //current root in subtree, width, height
vector<vector<ll>> ans = vector<vector<ll>>(W,vector<ll>(H,r0+1));
ll D = adj[r0].size();
for (ll d=0;d<D;d++) {
ans[1][1+2*d]=adj[r0][d]+1;
}
ll XMIN = 3;
for (ll r1: fadj[r0]) {
vector<vector<ll>> m1 = gmap(r1,4*sts[r1]-1,H-1);
for (ll x=0;x<(4*sts[r1]-1);x++) {
for (ll y=0;y<(H-1);y++) {
ans[x+XMIN][y+1]=m1[x][y];
}
}
XMIN += 4*sts[r1];
}
return ans;
}
vector<vector<int>> create_map(int _N, int _M, vector<int> A, vector<int> B) {
N=_N; M=_M;
adj=vector<vector<ll>>(N);
fadj=vector<vector<ll>>(N);
radj=vector<ll>(N,-1);
sts=vector<ll>(N,0);
for (ll m=0;m<M;m++) {
adj[A[m]-1].push_back(B[m]-1);
adj[B[m]-1].push_back(A[m]-1);
}
queue<ll> q0;
q0.push(0);
tpls.clear();
vector<bool> found(N,0);
found[0]=1;
while (!q0.empty()) {
ll x0 = q0.front(); q0.pop();
tpls.push_back(x0);
for (ll y: adj[x0]) {
if (!found[y]) {
fadj[x0].push_back(y);
radj[y]=x0;
found[y]=1;
q0.push(y);
}
}
}
for (ll t=(N-1);t>=0;t--) {
ll xc = tpls[t];
sts[xc]=1;
for (ll y: fadj[xc]) {
sts[xc]+=sts[y];
}
}
K = 4*N;
return gmap(0,K,K);
}
