class Solution {
    void dfs(vector<vector<int>>& edges, vector<bool>& visited, int root, int parent, vector<int>& parents, int& cyclo) {
        visited[root] = true;
        for(int vertex : edges[root]) {
            if (vertex != parent) {
                parents[vertex] = root;
                if (visited[vertex]) {
                    cyclo = vertex;
                }
                else {
                    dfs(edges, visited, vertex, root, parents, cyclo);
                }
            }
        }
    }

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<bool> visited(edges.size() + 1, false);
        vector<int> parents(edges.size() + 1, 0);
        vector<vector<int>> good_edges(edges.size() + 1, vector<int>());
        for (int i = 0; i < edges.size(); i++) {
            good_edges[edges[i][0]].push_back(edges[i][1]);
            good_edges[edges[i][1]].push_back(edges[i][0]);
        }
        int cyclo = 0;
        dfs(good_edges, visited, 1, 0, parents, cyclo);
        for (int i : parents) {
            cout << i << ' ';
        }
        set<vector<int>> ribs;
        int curr = cyclo;
        int next = 0;
        while (next != cyclo) {
            next = parents[curr];
            int f = curr;
            int s = next;
            ribs.insert({min(f, s), max(f, s)});
            curr = next;
        }
        for (int i = edges.size() - 1; i >= 0; i--) {
            if (ribs.count(edges[i]) > 0) {
                return edges[i];
            }
        }
        return {};
    }
};