vi adj[N];
int log1[N],first1[N];
vector<int> euiler,old_ind;
void dfs(int i,int par){
    int new_ind=old_ind.size();
    old_ind.push_back(i);
    first1[i]=euiler.size();
    euiler.push_back(new_ind);
    for(int x:adj[i]){
        if(x!=par){
            dfs(x,i);
            euiler.push_back(new_ind);
        }
    }
}
void sparse(int n,vector<vector<int>> &v){
    int p=log1[n];
    vector<int> v1(n+1,0);
    for(int i=0;i<=p;i++) v.push_back(v1);
    for(int i=1;i<=n;i++){
        v[0][i]=euiler[i];
    }
    for(int j=1;j<=p;j++){
        int len=(1<<j);
        int len1=len/2;
        for(int i=1;i+len-1<=n;i++){
            v[j][i]=min(v[j-1][i],v[j-1][i+len1]);
        }
    }
}
int query(int l,int r,vector<vector<int>> &v){
    int len=r-l+1;
    int p=log1[len];
    return min(v[p][l],v[p][r+1-(1<<p)]);
}