/// HLD + LCA
/// call  hld(n)
vector < int > v[N];
bool mark[N];   /// 0 for light edges and 1 for heavy
int deg[N], par[logn+2][N], lv[N], last[N], id[N], path[N], cnt;  /// last[n] = node with the lowest depth which lies on the same heavy path as node n
queue < int > q;
int findpar(int n, int k){
    for(int i = 0; k>0; i++){
        if(k&(1<<i)){
            k -= (1<<i);
            n = par[i][n];
        }
    }
    return n;
}
int lca(int a, int b){
    if(lv[a]>lv[b]) swap(a,b);
    b = findpar(b,lv[b]-lv[a]);
    if(a==b) return a;
    for(int i = logn; i>=0; i--){
        if(par[i][a]!=par[i][b]){
            a = par[i][a];
            b = par[i][b];
        }
    }
    return par[0][a];
}
int dfs(int n, int p){
    par[0][n] = p;
    lv[n] = lv[p]+1;
    deg[n] = 0;
    int cntt = 1, mx = 0, b = 0;
    for(int i = 0; i<v[n].size(); i++){
        int a = v[n][i];
        if(a!=p){
            deg[n]++;
            int tmp = dfs(a,n);
            cntt += tmp;
            if(mx<tmp){
                mx = tmp;
                b = a;
            }
            mark[a] = 0;
        }
    }
    if(mx*2>=cntt){
        mark[b] = 1;
    }
    return cntt;
}
int fun(int n){
    path[n] = cnt++;
    id[path[n]] = n;
    if(mark[n]==0){
        deg[par[0][n]]--;
        if(deg[par[0][n]]==0) q.push(par[0][n]);
        last[n] = n;
    }
    else last[n] = fun(par[0][n]);
    return last[n];
}
void hld(int n){
    mark[1] = 0;
    dfs(1,0);
    for(int i = 1; i<=n; i++) if(deg[i]==0) q.push(i);
    cnt = 1;
    while(!q.empty()){
        int a = q.front();
        q.pop();
        fun(a);
    }
    for(int i = 1; i<=logn; i++)
        for(int j = 1; j<=n; j++) par[i][j] = par[i-1][par[i-1][j]];
}