class Solution {
public:
    int n=0;
    int find(int u , vector<int> &father)
    {
        if(u == father[u]) return father[u];
        father[u] = find(father[u],father);
        return father[u];
    }
    void join(int u , int v , vector<int> &father )
    {
        u = find(u,father);
        v = find(v,father);
        if(u == v) return;
        father[v] = u; 
    }
    bool same(int u , int v , vector<int> &father)
    {
        u = find(u,father);
        v = find(v,father);
        return u == v;
    }
    bool tree_remove_edga(vector<vector<int>>& edges , int delete_edge , vector<int> &father)
    {
        for(int i=0 ; i<n ;i++)
        {
            if(i == delete_edge) continue;
            if(same(edges[i][0] , edges[i][1] , father) == true) return false;
            join(edges[i][0] , edges[i][1] , father);
        }
        return true;
    }
    vector<int> get_remove_edge(vector<vector<int>>& edges , vector<int> &father)
    {
        for(int i=0 ; i<n ;i++)
        {
            if(same(edges[i][0] , edges[i][1] , father) == true) return edges[i];
            join(edges[i][0] , edges[i][1] , father);
        }
        return {};
    }
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        n = edges.size();
        vector<int> father(n+1,0);
        vector<int> inDegree(n+1,0);
        for(int i=0 ; i<n ;i++)
        {
            father[i] = i;
            inDegree[edges[i][1]] += 1;
        }
        father[n] = n;
        vector<int> inDeg_2;
        for(int i=n-1 ; i>=0 ;i--)
            if(inDegree[edges[i][1]] >= 2) inDeg_2.push_back(i);
        if(inDeg_2.size() > 0)
        {
            if(tree_remove_edga(edges,inDeg_2[0] , father) == true) return edges[inDeg_2[0]];
            else return edges[inDeg_2[1]];
        }
        return get_remove_edge(edges,father);
    }
};