In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

&nbsp;
Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]


Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]


&nbsp;
Constraints:


	n == edges.length
	3 &lt;= n &lt;= 1000
	edges[i].length == 2
	1 &lt;= ai &lt; bi &lt;= edges.length
	ai != bi
	There are no repeated edges.
	The given graph is connected.


class UnionFind:
    
    def __init__(self, size):
        
        self.parent = [-1 for _ in range(size)]
        self.rank = [-1 for _ in range(size)]
        
    def find(self, i):
        
        if self.parent[i] == -1:
            return i
        
        k = self.find(self.parent[i])
        self.parent[i] = k
        return k
    
    def union(self, x, y):
        
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return -1
        else:
            
            if self.rank[x] > self.rank[y]:
                self.parent[y] = x
            
            elif self.rank[x] < self.rank[y]:
                self.parent[x] = y
                
            else:
                self.rank[x] += 1
                self.parent[y] = x

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
   
        vertex_set = set()
    
        for edge in edges:
            vertex_set.add(edge[0])
            vertex_set.add(edge[1])
        
        
        union_find = UnionFind(len(vertex_set))
        
        for edge in edges:
            
            new_edge = [edge[0]-1, edge[1]-1]
            
            if union_find.union(new_edge[0], new_edge[1]) == -1:
                return edge
        
        return []
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind(edges.length);
        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) {
                return new int[]{edge[0], edge[1]};
            }
        }
        return null;
    }

    private class UnionFind {
        int[] rank;
        int[] root;

        UnionFind(int n) {
            rank = new int[n + 1];
            root = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        int find(int x) {
            if (x == root[x]) {
                return x;
            }
            return root[x] = find(root[x]);
        }

        boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    root[rootY] = root[rootX];
                } else if (rank[rootY] > rank[rootX]) {
                    root[rootX] = root[rootY];
                } else {
                    root[rootY] = root[rootX];
                    rank[rootX]++;
                }
                return true;
            }
            return false;
        }
    }
}
class UnionFind {
    public:

    int* parent;
    int* rank;

    UnionFind(int n){
        rank = new int[n];
        parent = new int[n];

        for(int i=0; i<n; i++){
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // collapsing find
    int Find(int node){
        // if parent of node is itself
        if(parent[node] == node){
            return node;
        }
        return parent[node] = Find(parent[node]);
    }

    // union by rank
    void Union(int u, int v){
        // find the parent nodes of u and v
        u = Find(u);
        v = Find(v);

        // if u and v don't belong to the same set
        if(u != v){
            if(rank[u]<rank[v]){
                swap(u,v);
            }

            // attaching the lower rank tree with the higher rank one
            parent[v] = u;

            // if ranks are equal increase the rank of u
            if(rank[u]==rank[v]){
                rank[u]++;
            }
        }
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionFind UF = UnionFind(1001);

        for(vector<int>& edge : edges){
            int u = edge[0];
            int v = edge[1];

            // if adding this edge creates a cycle
            if(UF.Find(u) == UF.Find(v)){
                return {u,v};
            }

            // add u and v to the same set
            UF.Union(u,v);
        }

        // if no cycle was found
        return {-1};
    }
};
var findRedundantConnection = function(edges) {
    const root = [];
    const find = (index) => {
        const next = root[index];
        return next ? find(next) : index;
    };

    for (const [a, b] of edges) {
        const x = find(a);
        const y = find(b);

        if (x === y) return [a, b];
        root[x] = y;
    }
};
Redundant Connection