Beats 100%
Intuition\n\n\n\n\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\
# Intuition\n![image.png](https://assets.leetcode.com/users/images/862332e5-6f2d-43e8-b4a8-8176a3868ed1_1719730301.8598757.png)\n\n![image.png](https://assets.leetcode.com/users/images/42790c0c-bca1-4a52-9064-c68931f9e46c_1719729689.2956285.png)\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(E\u22C5\u03B1(n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n+E)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code C++\n```\n#include <bits/stdc++.h>\nusing namespace std;\n\nclass DSU {\npublic:\n    vector<int> parent, rank;\n    \n    DSU(int n) : parent(n+1), rank(n+1, 0) {\n        iota(parent.begin(), parent.end(), 0);\n    }\n\n    int find(int u) {\n        if (u != parent[u])\n            parent[u] = find(parent[u]);\n        return parent[u];\n    }\n\n    bool unite(int u, int v) {\n        int root_u = find(u), root_v = find(v);\n        if (root_u == root_v) return false;\n        if (rank[root_u] > rank[root_v]) {\n            parent[root_v] = root_u;\n        } else if (rank[root_u] < rank[root_v]) {\n            parent[root_u] = root_v;\n        } else {\n            parent[root_v] = root_u;\n            rank[root_u]++;\n        }\n        return true;\n    }\n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        DSU dsuAlice(n), dsuBob(n);\n        int removedEdges = 0;\n        int usedEdgesAlice = 0, usedEdgesBob = 0;\n\n        for (const auto& edge : edges) {\n            if (edge[0] == 3) {\n                bool aliceUnion = dsuAlice.unite(edge[1], edge[2]);\n                bool bobUnion = dsuBob.unite(edge[1], edge[2]);\n                if (!aliceUnion && !bobUnion) {\n                    removedEdges++;\n                } else {\n                    if (aliceUnion) usedEdgesAlice++;\n                    if (bobUnion) usedEdgesBob++;\n                }\n            }\n        }\n\n        for (const auto& edge : edges) {\n            if (edge[0] == 1) {\n                if (dsuAlice.unite(edge[1], edge[2])) {\n                    usedEdgesAlice++;\n                } else {\n                    removedEdges++;\n                }\n            }\n        }\n\n        for (const auto& edge : edges) {\n            if (edge[0] == 2) {\n                if (dsuBob.unite(edge[1], edge[2])) {\n                    usedEdgesBob++;\n                } else {\n                    removedEdges++;\n                }\n            }\n        }\n\n        if (usedEdgesAlice == n-1 && usedEdgesBob == n-1) {\n            return removedEdges;\n        }\n        return -1;\n    }\n}; \n//if you upvote this you will get a good news in 1 hour \n```\n# Code Python3\n```\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        auf = UnionFind(n)\n        buf = UnionFind(n)\n        res = 0\n        for edge in edges:\n            if edge[0] == 3:\n                if auf.union(edge[1], edge[2]) == 1:\n                    buf.union(edge[1], edge[2])\n                    res += 1\n            if auf.is_connected() and buf.is_connected():\n                return len(edges) - res\n        for edge in edges:\n            if edge[0] == 1:\n                res += auf.union(edge[1], edge[2])\n            if edge[0] == 2:\n                res += buf.union(edge[1], edge[2])\n            if auf.is_connected() and buf.is_connected():\n                return len(edges) - res\n        return -1\n\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [0] * (n + 1)\n        self.node_count = n\n    def find(self, x):\n        if self.parent[x] == 0 or self.parent[x] == x:\n            return x\n        self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n    def union(self, x, y):\n        px = self.find(x)\n        py = self.find(y)\n        if px == py:\n            return 0\n        self.parent[py] = px\n        self.node_count -= 1\n        return 1\n    def is_connected(self):\n        return self.node_count == 1\n#if you upvote this you will get a good news in 1 hour \n```\n
['C++', 'Python3']