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]];
}