#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct pair_hash{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
vector<vi> g;
vi dep, parent;
int n;
void dfs(int v, int p, int d){
dep[v] = d;
parent[v] = p;
for(auto u : g[v]){
if(u == 0 || dep[u] != 0){
continue;
}
dfs(u, v, d + 1);
}
}
vector<vi> f(int v){
vector<vi> vec;
int mx = 0;
vector<vector<vi>> curr;
for(auto u : g[v]){
if(dep[u] == dep[v] + 1){
curr.pb(f(u));
}
}
if(sz(curr) == 0){
vec.pb(vi());
vec.back().assign(1, v);
return vec;
}
for(auto ele : curr){
int mn = sz(ele[0]);
for(int j = 1; j < sz(ele); j++){
mn = min(mn, sz(ele[j]));
}
mx = max(mx, mn);
}
for(int i = 0; i < sz(curr); i++){
vec.pb(vi());
vec.back().assign(mx + 2, v);
for(auto ele : curr[i]){
vec.pb(ele);
}
}
vec.pb(vi());
vec.back().assign(mx + 2, v);
for(int i = 0; i < sz(vec); i++){
vec[i].pb(v);
while(sz(vec[i]) < mx + 1){
vec[i].pb(v);
}
}
for(int i = 0; i < sz(vec); i++){
if(sz(vec[i]) == mx + 3){
for(int j = -1; j <= 1; j += 2){
if(i + j >= 0 && i + j < sz(vec)){
while(sz(vec[i + j]) < mx + 2){
vec[i + j].pb(v);
}
}
}
}
}
int wsk = 1;
while(sz(vec[wsk]) > mx + 1){
wsk++;
}
for(auto u : g[v]){
if(dep[u] > dep[v] + 1){
vec[wsk].pb(u);
wsk+= 2;
while(sz(vec[wsk]) > mx + 1){
wsk++;
}
}
}
for(int i = 0; i < sz(vec); i++){
if(vec[i].back() != v || sz(vec[i]) == mx + 1){
vec[i].pb(v);
}
}
return vec;
}
vector<vi> create_map(int N, int M, vi A, vi B){
g.assign(N, vi());
parent.assign(N, 0);
dep.assign(N, 0);
n = N;
for(int i = 0; i < M; i++){
A[i]--;
B[i]--;
g[A[i]].pb(B[i]);
g[B[i]].pb(A[i]);
}
dfs(0, 0, 0);
vector<vi> map = f(0);
for(int i = 0; i < sz(map); i++){
for(int j = 0; j < sz(map[i]); j++){
map[i][j]++;
}
}
while(sz(map) < 2 * n){
map.pb(vi(2 * n, 1));
}
for(int i = 0; i < sz(map); i++){
while(sz(map[i]) < 2 * n){
map[i].pb(1);
}
}
return map;
}
