class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UF uf(edges.size());
        for (const auto& edge : edges) {
            if (uf.IsConnected(edge[0], edge[1])) return edge;
            uf.Connect(edge[0], edge[1]);
        }
        return {};
    }
private:
    class UF {
    public:
        UF(int N) {
            data_ = vector<int>(N + 1, -1); // store weight of the subtree
        }

        void Connect(int v, int u) {
            auto p1 = GetParent(v);
            auto w1 = data_[p1];

            auto p2 = GetParent(u);
            auto w2 = data_[p2];

            if (w1 > w2) {
                data_[p2] = p1;  // connect smaller subtree to bigger one
                data_[p1] += w2; // add weights
            } else {
                data_[p1] = p2;
                data_[p2] += w1;
            }
        }

        bool IsConnected(int v, int u) {
            return GetParent(v) == GetParent(u);
        }

    private:
        vector<int> data_;

        int GetParent(int v) {
            int p = data_[v];

            while (p > 0) {
                int pp = data_[p];
                if (pp > 0) data_[v] = pp; // path compression
                v = p;
                p = pp;
            }

            return v;
        }
    };
};