#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)); ll D = adj[r0].size(); for (ll d=0;d<D;d++) { ans[1][1+2*d]=adj[r0][d]+1; } ll XMIN = 1; for (ll r1: fadj[r0]) { vector<vector<ll>> m1 = gmap(r1,3*sts[r1],H-1); for (ll x=0;x<(3*sts[r1]);x++) { for (ll y=0;y<(H-1);y++) { ans[x+XMIN][y+1]=m1[x][y]; } } XMIN += 3*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 = 3*N; return gmap(0,K,K); }