const int N =40040;
const int M=25;
int dp[N<<1][M];
bool vis[N];
struct edge
{
int u,v,w,next;
}e[N<<1];
int tot,head[N];
inline void add(int u,int v,int w,int &k)
{
e[k].u=u;e[k].v=v;e[k].w=w;
e[k].next=head[u];head[u]=k++;
u^=v^=u=^v;
e[k].u=u;e[k].v=v;e[k].w=w;
e[k].next=head[u];head[u]=k++;
}
int ver[N<<1],R[N<<1],first[N],dir[N];
int tot,head[N],ver[2*N],R[2*N],first[N],dir[N];
//ver:节点编号 R：深度 first：点编号位置 dir：距离
void dfs(int u ,int dep)
{
vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep;
for(int k=head[u]; k!=-1; k=e[k].next)
if( !vis[e[k].v] )
{
int v = e[k].v , w = e[k].w;
dir[v] = dir[u] + w;
dfs(v,dep+1);
ver[++tot] = u; R[tot] = dep;
}
}
void ST(int n)
{
for(int i=1;i<=n;i++)
dp[i][0] = i;
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
int a = dp[i][j-1] , b = dp[i+(1<<(j-1))][j-1];
dp[i][j] = R[a]<R[b]?a:b;
}
}
}
//中间部分是交叉的。
int RMQ(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1)
k++;
int a = dp[l][k], b = dp[r-(1<<k)+1][k]; //保存的是编号
return R[a]<R[b]?a:b;
}
int LCA(int u ,int v)
{
int x = first[u] , y = first[v];
if(x > y) swap(x,y);
int res = RMQ(x,y);
return ver[res];
}