class Solution {
    int parent[];
    int size[];
    int ans[] ;

    public int findparent(int u){
        if(parent[u] == u)
        return u;

        return parent[u] = findparent(parent[u]);
    }

    public void union(int x , int y ){
        int lx = findparent(x);
        int ly = findparent(y);

        if(lx != ly){
            if(size[lx] > size[ly]){
                parent[ly] = lx;
            }
            else{
                parent[lx] = ly;

                if(size[lx] == size[ly])
                size[lx]++;
            }
        }

        /* if already parents are equal means there already exist a path between nodes
        that means this edge is generating a cycle in the graph
        */
        else{
            ans[0] = x;
            ans[1] = y;
        }
        
    }
    public int[] findRedundantConnection(int[][] edges) {
        /* Q37 graph playlist , the extra edge is creating a cycle therefore we find 
        the last edge which is creating a cycle using DSU 

        1) we merge nodes 
        2) if parents of 2 nodes to merged are equal in union means they are creating a 
        cycle so update answer , 

        */
        int m = edges.length , n = edges[0].length ;

        ans = new int[2];
        parent = new int[m+1];
        size = new int[m+1];

        //initialising DSU 
        for(int i = 0 ; i < m ; i++){
            parent[i] = i;
            size[i] = 1;
        }

        //merging
        for(int edge[] : edges){
            int a = edge[0] , b = edge[1];
            
            union(a , b);
        }

        return ans;
    }
}