void ST_create(){
    k = log2(N);
    for(int j = 1; j <= k; j++)
        for(int i = 1; i <= n - (1<<j) + 1; i++)
            F[i][j] = F[F[i][j-1]][j-1];
}

int LCA_ST_query(int x, int y){
    if (d[x] > d[y]) swap(x, y);
    for(int i = k; i >= 0; i--)
        if (d[F[y][i]] >= d[x])
            y = F[y][i];
    if (x == y) return x;
    for(int i = k; i >= 0; i--)
        if (F[x][i] != F[y][i])
            x = F[x][i], y = F[y][i];
    return F[x][0];
}

pos[u] = ++tot;
seq[tot] = u;
dep[tot] = d;

void dfs(int u, int d){
    vis[u] = true;
    pos[u] = ++tot;
    seq[tot] = u;
    dep[tot] = d;
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v, w = e[i].c;
        if (!vis[v]){
            dist[v] = dist[u] + w;
            dfs(v, d + 1);
        }
        seq[++tot] = u;
        dep[tot] = d;
    }
}

void ST_create(){
    for(int i = 1; i <= tot; i++)
        F[i][0] = i;
    k = log2(tot);
    for(int j = 1; j <= k; j++)
        for(int i = 1; i <= tot - (1<<j) + 1; i++)
            if (dep[F[i][j-1]] < dep[F[i+(1<<(j-1))][j-1]])
                F[i][j] = F[i][j-1];
            else
                F[i][j] = F[i+(1<<(j-1))][j-1];
}

int RMQ_query(int l, int r){
    int k = log2(r - l + 1);
    if (dep[F[l][k]] < dep[F[r-(1<<k)+1][k]])
        return F[l][k];
    else
        return F[r-(1<<k)+1][k];
}

int LCA(int x, int y){
    int l = pos[x], r = pos[y];
    if (l > r) swap(l, r);
    return seq[RMQ_query(l, r)];
}