int depth[N],fa[N][17];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void build(int root){
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;
    queue<int> q;q.push(root);
    while(!q.empty()){
        int t=q.front();q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(depth[j]>depth[t]+1){
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                for(int k=1;k<=16;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}
int LCA(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=16;k>=0;k--)
        if(fa[a][k]!=fa[b][k]){
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];
}