void add(int u,int v){
e[idx] = v;ne[idx] = head[u];head[u] = idx++;
}
void dfs(int u,int father){
depth[u] = depth[father]+1;
for(int i=0;i<=19;i++){
f[u][i+1] = f[u][f[u][i]];
}
for(int i = head[u];i;i = ne[i]){
int v = e[i];
if( v == father) continue;
f[v][0] = u;
dfs(v,u);
}
}
int LCA(int x,int y){
if(depth[x] < depth[y]) swap(x,y);
for(int i=20;i>=0;i--){
if(depth[f[x][i]]>depth[y]) x = f[x][i];
if(x==y) return x;
}
for(int i =20;i>=0;i--){
if(f[x][i]!=f[y][i]){
x = f[x][i];
y = f[y][i];
}
}
return f[x][0]; //x.y是深度不同且最浅的子节点
}