1579. Remove Max Number of Edges to Keep Graph Fully Traversable

class UnionFind {
    int[] parent;
    int components;

    public UnionFind(int n) {
        parent = new int[n + 1];
        components = n;
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false; // Both nodes are already in the same component
        }
        parent[rootY] = rootX;
        components--;
        return true;
    }

    public int getComponents() {
        return components;
    }
}

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind alice = new UnionFind(n);
        UnionFind bob = new UnionFind(n);
        int removedEdges = 0;

        for (int[] edge : edges) {
            int type = edge[0];
            int u = edge[1];
            int v = edge[2];
            
            if (type == 3) {
                if (!alice.union(u, v)) {
                    removedEdges++;
                } else {
                    bob.union(u, v);
                }
            }
        }

        for (int[] edge : edges) {
            int type = edge[0];
            int u = edge[1];
            int v = edge[2];
            
            if (type == 1) {
                if (!alice.union(u, v)) {
                    removedEdges++;
                }
            } else if (type == 2) {
                if (!bob.union(u, v)) {
                    removedEdges++;
                }
            }
        }

        if (alice.getComponents() != 1 || bob.getComponents() != 1) {
            return -1;
        }

        return removedEdges;
    }
}