/**
1. 建图的时候, 每次判断下要加入的边两点直接是否连通即可
2. 判断图连通的方法 -> 1. dfs(O(n*m)) 2. 并查集 O(m)
*/

class Solution {

    class UnionFindSet{
        int[] pre;

        public UnionFindSet(int n){
            pre = new int[n];
            for (int i = 0 ; i < n; i++) pre[i] = i;
        }

        public int find(int x){
            if (x != pre[x]) pre[x] = find(pre[x]);  
            return pre[x]; 
        }

        public boolean union(int x, int y){
            int fx = find(x), fy = find(y);
            if (fx == fy) return false;
            pre[fx] = fy;
            return true;
        }
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFindSet ufs = new UnionFindSet(n+1);
        for (int i = 0 ; i < n ; i++){
            int[] edge = edges[i];
            if (!ufs.union(edge[0], edge[1])) return edge;
        }
        return null;
    }
}