vector<ll> G[N];
ll par[N][LOGN], h[N];

void dfs(int u, int p = -1) {
    par[u][0] = p;
    if (~p)
        h[u] = h[p] + 1;
    for (int i = 1; i < LOGN; ++i)
        if (~par[u][i - 1])
            par[u][i] = par[par[u][i - 1]][i - 1];

    for (auto to : G[u])
        if (to != p)
            dfs(to, u);
}

int LCA(int u, int v) {
    if (h[u] < h[v])
        swap(u, v);

    for (int i = LOGN - 1; ~i; --i) // make them the same level
        if (~par[u][i] && h[par[u][i]] >= h[v])
            u = par[u][i];

    if (u == v)
        return u;

    for (int i = LOGN - 1; ~i; --i)
        if (par[u][i] != par[v][i])
            u = par[u][i], v = par[v][i];

    return par[u][0];
}

void clear() {
        memset(par, -1, sizeof(par));
        memset(h, 0, sizeof(h));

        for (int i = 0; i < n; ++i)
            G[i].clear();
}