Solution using Prim's Minimum Spanning Tree
Intuition\nSince we need to find minimum edges with which graph is fully traversal for both alice and bob, it means we need to find MST possible for both alice 
# Intuition\nSince we need to find minimum edges with which graph is fully traversal for both alice and bob, it means we need to find MST possible for both alice and bob\n\n# Approach\n- We will apply prims algorithm to find minimum spanning tree for alice and bob \n- while picking edges we will give higher priority to edge with type 3\n- we will find MST for alice and bob separately and union their edges. This count is count of minimum edges we need to have graph fully travererable by both alice and bob\n- in priority queue, we will define sorting order first by type, then by src, and then by dest, because we can have mulitple type 3 edges to choose for same nodes, in such case we want to construct same mst for alice and bob both\n\n# Complexity\n- Time complexity:\nMST takes O(V*ElogV)\n\n# Code\n```\nclass Solution {\n        static class Edge implements Comparable<Edge> {\n            int s;\n            int d;\n            int t;\n\n            Edge(int src, int dst, int type) {\n                s = src;\n                d = dst;\n                t = type;\n            }\n\n            @Override\n            public int compareTo(Edge e) {\n                if(e.t != this.t)\n                    return e.t - this.t;\n\n                if(e.s != this.s)\n                    return e.s - this.s;\n\n                return e.d - this.d;\n            }\n\n            @Override\n            public boolean equals(Object o) {\n                Edge e = ((Edge)o);\n                return e.t == this.t &&\n                        (\n                                (e.s == this.s && e.d == this.d) ||\n                                        (e.s == this.d && e.d == this.s)\n                        );\n            }\n\n            @Override\n            public int hashCode() {\n                return 31 * t * s * d;\n            }\n        }\n\n        private Set<Edge> getMST(List<Edge> adj[], int n, int type) {\n            Set<Edge> out = new HashSet();\n            PriorityQueue<Edge> q = new PriorityQueue();\n            q.add(new Edge(0, 0, -1));\n\n            boolean vis[] = new boolean[n];\n\n            while(!q.isEmpty()) {\n                Edge r = q.poll();\n\n                if(vis[r.d])\n                    continue;\n\n                vis[r.d] = true;\n\n                if(r.t != -1)\n                    out.add(r);\n\n                for(Edge e: adj[r.d]) {\n                    if(!vis[e.d] && (e.t == 3 || e.t == type)) {\n                        q.add(e);\n                    }\n                }\n\n            }\n\n            for(int i=0;i<n;i++) {\n                if(!vis[i])\n                    return Collections.emptySet();\n            }\n\n            return out;\n        }\n\n        public int maxNumEdgesToRemove(int n, int[][] edges) {\n\n            List<Edge> adj[] = new List[n];\n            for(int i=0;i<n;i++)\n                adj[i] = new ArrayList();\n\n            for(int i=0;i<edges.length;i++) {\n                adj[edges[i][1]-1].add(new Edge(edges[i][1]-1, edges[i][2]-1, edges[i][0]));\n                adj[edges[i][2]-1].add(new Edge(edges[i][2]-1, edges[i][1]-1, edges[i][0]));\n            }\n\n            Set<Edge> aliceMST = getMST(adj, n, 1);\n            Set<Edge> bobMST = getMST(adj, n, 2);\n\n            if(aliceMST.isEmpty() || bobMST.isEmpty())\n                return -1;\n\n            aliceMST.addAll(bobMST);\n\n            return edges.length - aliceMST.size();\n        }\n    }\n```
['Minimum Spanning Tree', 'Java']