1class DSU:
2    def __init__(self, n):
3        self.parent = list(range(n))
4        self.rank = [1] * n
5
6    def find(self, x):
7        if self.parent[x] != x:
8            self.parent[x] = self.find(self.parent[x])
9        return self.parent[x]
10
11    def union(self, x, y):
12        rootX, rootY = self.find(x), self.find(y)
13        if rootX != rootY:
14            if self.rank[rootX] > self.rank[rootY]:
15                self.parent[rootY] = rootX
16            elif self.rank[rootX] < self.rank[rootY]:
17                self.parent[rootX] = rootY
18            else:
19                self.parent[rootY] = rootX
20                self.rank[rootX] += 1
21            return True
22        return False
23
24    def is_connected(self):
25        roots = set(self.find(x) for x in range(len(self.parent)))
26        return len(roots) == 1
27
28class Solution:
29    def maxNumEdgesToRemove(self, n: int, edges: list[list[int]]) -> int:
30        dsu_alice = DSU(n)
31        dsu_bob = DSU(n)
32        saved_edges = 0
33        
34        for t, u, v in edges:
35            if t == 3:
36                alice_united = dsu_alice.union(u - 1, v - 1)
37                bob_united = dsu_bob.union(u - 1, v - 1)
38                if not alice_united or not bob_united:
39                    saved_edges += 1
40        
41        for t, u, v in edges:
42            if t == 1:
43                if not dsu_alice.union(u - 1, v - 1):
44                    saved_edges += 1
45            elif t == 2:
46                if not dsu_bob.union(u - 1, v - 1):
47                    saved_edges += 1
48        
49        if not dsu_alice.is_connected() or not dsu_bob.is_connected():
50            return -1
51
52        return saved_edges
53

Practice on LeetCode

Solve with full IDE support and test cases