1
class DSUF:
2
    def __init__(self, n):
3
        self.arr = [-1] * n
4

5
    def find(self, node):
6
        p = self.arr[node]
7
        if p == -1:
8
            return node
9
        self.arr[node] = self.find(p)
10
        return self.arr[node]
11

12
    def union(self, a, b):
13
        aP = self.find(a)
14
        bP = self.find(b)
15
        if aP == bP:
16
            return 0
17
        self.arr[aP] = bP
18
        return 1
19

20
    def countParents(self):
21
        count = 0
22
        for i in self.arr:
23
            if i == -1:
24
                count += 1
25
        return count
26

27

28
class Solution:
29
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
30
        # Solution - DSU
31
        # Time - O(ElogV)
32
        # Space - O(V)
33

34
        aliceSet = DSUF(n)
35
        bobSet = DSUF(n)
36

37
        bothEdges = []
38
        bobEdges = []
39
        aliceEdges = []
40
        for i in range(len(edges)):
41
            if edges[i][0] == 3:
42
                bothEdges.append(edges[i])
43
            elif edges[i][0] == 1:
44
                aliceEdges.append(edges[i])
45
            else:
46
                bobEdges.append(edges[i])
47

48
        usedEdgeCount = 0
49

50
        # connect both edges
51
        for edge in bothEdges:
52
            aReq = aliceSet.union(edge[1] - 1, edge[2] - 1)
53
            bReq = bobSet.union(edge[1] - 1, edge[2] - 1)
54
            if aReq and bReq:
55
                usedEdgeCount += 1
56

57
        # connect individual edges
58
        for edge in aliceEdges:
59
            usedEdgeCount += aliceSet.union(edge[1] - 1, edge[2] - 1)
60

61
        for edge in bobEdges:
62
            usedEdgeCount += bobSet.union(edge[1] - 1, edge[2] - 1)
63

64
        if aliceSet.countParents() == 1 and bobSet.countParents() == 1:
65
            return len(edges) - usedEdgeCount
66

67
        return -1