class Solution {
public:
    vector<int> par,a;
    int find(int x)
    {
        if(par[x] == x)return x;
        return par[x] = find(par[x]);
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges)
    {
        int n=edges.size();
        par.resize(n+1);
        for(int i=1;i<=n;i++){par[i]=i;}
        for(int i=0;i<n;i++)
        {
            int update1 = find(edges[i][0]);
            int update2 = find(edges[i][1]);
            if(update1 == update2){return edges[i];}
            else par[update1] = update2;
        }
        return a;
    }
};

class Solution {
public:
    vector<int>findRedundantDirectedConnection(vector<vector<int>>& edg)
    {
        int n=edg.size();
        vector<int> par, first_edg, second_edg;
        par.resize(n+1, -1);
        unordered_map<int, int> m;
        for(auto x:edg)
        {
            if(not m.count(x[1]))m[x[1]]=x[0];
            else first_edg={m[x[1]], x[1]}, second_edg=x;
        }
        for(auto x:edg)
        {
            int a=x[0], b=x[1];
            if(par[a]==-1)par[a]=a;
            if(par[b]==-1)par[b]=b;
            if(x==first_edg)continue;
            while(par[a]!=a)
            {
                a=par[a];
                if(a==b)//if b exists in path from a to its top parent
                {
                    if(second_edg.empty())return x;
                    return second_edg;
                }
            }
            par[b]=x[0];
        }
        int a=first_edg[0], b=first_edg[1];
        while(par[a]!=a and a!=b)
        {
            a=par[a];
        }
        if(a==b)return first_edg;
        return second_edg;
    }
};