#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int fa[MAXN];
int he[MAXN]={0,1};
int f[MAXN][25];
void init(){
f[0][0]=0;
for(int i=1;i<=n;i++){
f[i][0]=fa[i];
}
for(int j=1;j<int(log(n)/log(2))+1;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
}
int lca(int a,int b){
if(he[a]<he[b])swap(a,b);
for(int move=he[a]-he[b];move>0;move=he[a]-he[b]){
a=f[a][int(log(move)/log(2))];
}
if(a==b)return a;
else{
for(int x=int(log(he[a])/log(2));x>=0;x--){
if(f[a][x]!=f[b][x]){
a=f[a][x];
b=f[b][x];
}
}
return fa[a];
}
}