const int POW = ;

void dfs(int u,int fa){

d[u]=d[fa]+;

    p[u][]=fa;

for(int i=;i<POW;i++) p[u][i]=p[p[u][i-]][i-];

int sz=edge[u].size();

for(int i=;i<sz;i++){

int v=edge[u][i];

if(v==fa) continue;

dfs(v,u);

}

}

int lca( int a, int b ){

if( d[a] > d[b] ) a ^= b, b ^= a, a ^= b;

if( d[a] < d[b] ){

int del = d[b] - d[a];

for( int i = ; i < POW; i++ ) if(del&(<<i)) b=p[b][i];

}

if( a != b ){

for( int i = POW-; i >= ; i-- )

if( p[a][i] != p[b][i] )

     a = p[a][i] , b = p[b][i];

a = p[a][], b = p[b][];

}

return a;

}