Untitled

template<typename T>
class graph {
public:
    struct child {
        int to, ind;
        T cost;
    };
    vector<vector<child>> adj;
    int n, m;
    graph() : n(0), m(0) {}
    explicit graph(const int &_n) : n(_n), m(0) { adj.assign(n, vector<child>()); }
    void add(int N1, int N2, int i = -1, T cost = 0) {
        i = ~i ? i : m;
        adj[N1].push_back({N2, i, cost});
        adj[N2].push_back({N1, i, cost});
        ++m;
    }
};
template<typename T>
class LCA {
public:
    vector<vector<int>> up;
    vector<int> depth;
    int lg;
    explicit LCA(const graph<T> &g) : lg(25) {
        up.assign(g.n, vector<int>(lg));
        depth.assign(g.n, 0);
        buildBL(0, 0, g);
    }
    void buildBL(int u, int p, const graph<T> &g) {
        up[u][0] = p, depth[u] = depth[p] + 1;
        for (int i = 1; i < lg; ++i) up[u][i] = up[up[u][i - 1]][i - 1];
        for (const auto &ch: g.adj[u])
            if (ch.to != p) buildBL(ch.to, u, g);
    }
    int Kth(int u, int k) {
        for (int i = 0; i < lg; ++i)
            if (k >> i & 1) u = up[u][i];
        return u;
    }
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        u = Kth(u, depth[u] - depth[v]);
        if (u == v) return u;
        for (int i = lg - 1; i >= 0; --i)
            if (up[u][i] != up[v][i])
                u = up[u][i], v = up[v][i];
        return up[u][0];
    }
};