[Java] Union Find O(N)
Let\nc1: number of connected components using type 1 edges only\nc2: number of connected components using type 1  and type 2 edges \nc3: number of connected com
Let\nc1: number of connected components using type 1 edges only\nc2: number of connected components using type 1  and type 2 edges \nc3: number of connected components using type 1  and type 3 edges \n=>\ncase 1: The graph is not connected for Alice or Bob, return -1\ncase 2: The graph is connected for Alice and Bob, return **number of edges - ((number of vertices - c3) + (c3 -1) + (c3 -1))**\n```\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        DSU dsu3 = new DSU(n);\n        DSU dsu2 = new DSU(n);\n        DSU dsu1 = new DSU(n);\n        for(int[] e : edges){\n            int type = e[0];\n            if(type==3){\n                dsu3.union(e[1]-1, e[2]-1);\n                dsu2.union(e[1]-1, e[2]-1);\n                dsu1.union(e[1]-1, e[2]-1);\n            }\n            else if(type==2){\n                dsu2.union(e[1]-1, e[2]-1);\n            }\n            else{\n                dsu1.union(e[1]-1, e[2]-1);\n            }\n        }\n        int c1 = dsu1.components;\n        int c2 = dsu2.components;\n        if(c1!=1 || c2!=1){\n            return -1;\n        }\n        int c3 = dsu3.components;\n        int need = n-c3 + c3-1 + c3-1;\n        return edges.length-need;\n    }\n    \n    class DSU{\n        int[] parent;\n        int[] size;\n        int components;\n\n        public DSU(int N){\n            components = N;\n            parent = new int[N];\n            size = new int[N];\n            for(int i=0; i<parent.length; i++){\n                parent[i] = i;\n                size[i] = 1;\n            }\n        }\n\n        public int find(int x){\n            if(parent[x]!=x){\n                parent[x] = find(parent[x]);\n            }\n            return parent[x];\n        }\n\n        public int union(int x, int y){\n            int xParent = find(x);\n            int yParent = find(y);\n            if(xParent==yParent) return size[xParent];\n            components--;\n            if(size[xParent]<=size[yParent]){\n                parent[xParent] = yParent;\n                size[yParent]+=size[xParent];\n                return size[yParent];\n            }\n            else{\n                parent[yParent] = xParent;\n                size[xParent] += size[yParent];\n                return size[xParent];\n            }\n        }\n    }\n}\n```
[]