Java Solution, Beats 96.64%
Intuition\n\nThe problem involves ensuring that Alice and Bob can both fully traverse the graph using the provided edges. The key insight is to maximize the num
# Intuition\n\nThe problem involves ensuring that Alice and Bob can both fully traverse the graph using the provided edges. The key insight is to maximize the number of edges that can be removed while ensuring that both Alice and Bob can still traverse the entire graph. This can be achieved by using a Union-Find data structure to manage the connectivity of the nodes for Alice and Bob separately.\n\n# Approach\n\n1. **Union-Find Data Structure**: \n    - Use two separate Union-Find structures, one for Alice and one for Bob.\n    - A Union-Find (also known as Disjoint Set Union, DSU) is used to manage the connected components of a graph efficiently.\n\n2. **Processing Edges**:\n    - First, process all type 3 edges (shared by both Alice and Bob) and attempt to add them to both Alice\u2019s and Bob\u2019s graphs. These edges are essential for ensuring the connectivity of both graphs.\n    - Then, process type 2 edges (only for Bob) and add them to Bob\u2019s graph.\n    - Finally, process type 1 edges (only for Alice) and add them to Alice\u2019s graph.\n\n3. **Count Necessary Edges**:\n    - Keep a count of all edges that are necessary for maintaining connectivity. This count will help in calculating the number of removable edges.\n\n4. **Check Full Connectivity**:\n    - After processing all edges, check if both Alice\u2019s and Bob\u2019s graphs are fully connected.\n    - If they are, the number of removable edges is the total number of edges minus the number of necessary edges.\n    - If either graph is not fully connected, return -1 indicating it is impossible for both to fully traverse the graph.\n\n# Complexity\n\n## Time Complexity\n- The time complexity for processing edges is \\(O(N + E)\\), where \\(N\\) is the number of nodes and \\(E\\) is the number of edges. This is because the union-find operations are nearly constant time due to path compression and union by rank, making the total complexity linear in the number of nodes and edges.\n\n## Space Complexity\n- The space complexity is \\(O(N)\\), which is used for storing the representative and component size arrays in the Union-Find data structure.\n\n# Code\n```\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        UnionFind alice = new UnionFind(n);\n        UnionFind bob = new UnionFind(n);\n\n        int edgesRequired = 0;\n        // First process type 3 edges\n        for (int[] edge : edges) {\n            if (edge[0] == 3) {\n                edgesRequired += (alice.preformUnion(edge[1], edge[2]) | bob.preformUnion(edge[1], edge[2]));\n            }\n        }\n\n        // Process type 2 and type 1 edges\n        for (int[] edge : edges) {\n            if (edge[0] == 2) {\n                edgesRequired += bob.preformUnion(edge[1], edge[2]);\n            } else if (edge[0] == 1) {\n                edgesRequired += alice.preformUnion(edge[1], edge[2]);\n            }\n        }\n\n        // Check if both Alice\'s and Bob\'s graphs are fully connected\n        if (alice.isConnected() && bob.isConnected()) {\n            return edges.length - edgesRequired;\n        }\n\n        return -1;\n    }\n\n    class UnionFind {\n        int[] representative;\n        int[] componentSize;\n        int components;\n\n        UnionFind(int n) {\n            components = n;\n            representative = new int[n + 1];\n            componentSize = new int[n + 1];\n\n            for (int i = 0; i <= n; i++) {\n                representative[i] = i;\n                componentSize[i] = 1;\n            }\n        }\n\n        int findRepresentative(int x) {\n            if (representative[x] == x) {\n                return x;\n            }\n            return representative[x] = findRepresentative(representative[x]);\n        }\n\n        int preformUnion(int x, int y) {\n            x = findRepresentative(x);\n            y = findRepresentative(y);\n\n            if (x == y) {\n                return 0;\n            }\n\n            if (componentSize[x] > componentSize[y]) {\n                componentSize[x] += componentSize[y];\n                representative[y] = x;\n            } else {\n                componentSize[y] += componentSize[x];\n                representative[x] = y;\n            }\n\n            components--;\n            return 1;\n        }\n\n        boolean isConnected() {\n            return components == 1;\n        }\n    }\n}\n```
['Java']