class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = 0;
        for (const auto& edge : edges)
            N = max({N, edge[0], edge[1]});

        UF uf(N);
        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);
        }

        void Connect(int v, int u) {
            auto [p1, w1] = GetParentAndWeight(v);
            auto [p2, w2] = GetParentAndWeight(u);

            if (w1 > w2) {
                data_[p2] = p1;
                data_[p1] += w2;
            } else {
                data_[p1] = p2;
                data_[p2] += w1;
            }
        }

        bool IsConnected(int v, int u) {
            return GetParentAndWeight(v).first == GetParentAndWeight(u).first;
        }
    private:
        vector<int> data_;

        pair<int, int> GetParentAndWeight(int v) {
            int p = data_[v];

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

            return {v, p};
        }
    };
};