void dfs(int x,int root){//预处理fa和dep数组

    fa[x][0]=root;

    dep[x]=dep[root]+1;

    for(int i=1;(1<<i)<dep[x];i++)

        fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=0;i<ve[x].size();i++)dfs(ve[x][i],x);

}

int lca(int a,int b){//计算两个节点的最近公共祖先

    if(dep[a]>dep[b])swap(a,b);

    for(int i=20;i>=0;i--){

        if(dep[fa[b][i]]>=dep[a])b=fa[b][i];

        if(dep[a]==dep[b])break;

    }

    if(a==b)return a;

    for(int i=20;i>=0;i--)

        if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];

    return fa[a][0];

}