Alice and Bob have an undirected graph of n nodes and three types of edges:


	Type 1: Can be traversed by Alice only.
	Type 2: Can be traversed by Bob only.
	Type 3: Can be traversed by both Alice and Bob.


Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

&nbsp;
Example 1:



Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.


Example 2:



Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.


Example 3:



Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

&nbsp;

&nbsp;
Constraints:


	1 &lt;= n &lt;= 105
	1 &lt;= edges.length &lt;= min(105, 3 * n * (n - 1) / 2)
	edges[i].length == 3
	1 &lt;= typei &lt;= 3
	1 &lt;= ui &lt; vi &lt;= n
	All tuples (typei, ui, vi) are distinct.


class DSUF:
    def __init__(self, n):
        self.arr = [-1] * n
    def find(self, node):
        p = self.arr[node]
        if p == -1:
            return node
        self.arr[node] = self.find(p)
        return self.arr[node]
    def union(self, a, b):
        aP = self.find(a)
        bP = self.find(b)
        if aP == bP:
            return 0
        self.arr[aP] = bP
        return 1
    def countParents(self):
        count = 0
        for i in self.arr:
            if i == -1:
                count += 1
        return count

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        # Solution - DSU
        # Time - O(ElogV)
        # Space - O(V)
        
        aliceSet = DSUF(n)
        bobSet = DSUF(n)
        
        bothEdges = []
        bobEdges = []
        aliceEdges= []
        for i in range(len(edges)):
            if edges[i][0] == 3:
                bothEdges.append(edges[i])
            elif edges[i][0] == 1:
                aliceEdges.append(edges[i])
            else:
                bobEdges.append(edges[i])
        
        usedEdgeCount = 0
        
        # connect both edges
        for edge in bothEdges:
            aReq = aliceSet.union(edge[1]-1, edge[2]-1)
            bReq = bobSet.union(edge[1]-1, edge[2]-1)
            if aReq and bReq:
                usedEdgeCount += 1
        
        # connect individual edges
        for edge in aliceEdges:
            usedEdgeCount += aliceSet.union(edge[1]-1, edge[2]-1)
        
        for edge in bobEdges:
            usedEdgeCount += bobSet.union(edge[1]-1, edge[2]-1)
        
        if aliceSet.countParents() == 1 and bobSet.countParents() == 1:
            return len(edges) - usedEdgeCount
        
        return -1
class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) 
    {
        Arrays.sort(edges, (a, b)->{
            return b[0]-a[0];
        });//giving the priority to third type of edge or the edge which Bob and Alice both can access
        
        //1-based indexing of nodes 
        int []parentAlice= new int[n+1];//Graph 1 for Alice connectedness
        int []parentBob= new int[n+1];//Graph 2 for Bob connectedness
        
        for(int i= 0; i< n+1; i++){//every node is pointing to itself, at first no connection is considered all sets are independent(no dependency) 
            parentAlice[i]= i;
            parentBob[i]= i;
        }
        
        //number of merged unique node for Alice and Bob that are required to maintain the connectedness of Alice and Bob graph nodes//intialised with one because merging happens in pair 
        int mergeAlice= 1;
        int mergeBob= 1;
        
        //number of cyclic or the non dependent node, that are not required for the connectedness of Alice and Bob nodes  
        int removeEdge= 0;
        
        for(int []edge: edges)
        {
            int cat= edge[0];//category of edge 1)edge Alice can only access 2)edge Bob can only access 3)edge both Alice and Bob can access
            int u= edge[1];
            int v= edge[2];
            
            if(cat == 3){//edge both Alice and Bob an access
                
                //creating dependency of nodes in graph 1 and 2 
                boolean tempAlice= union(u, v, parentAlice);
                boolean tempBob= union(u, v, parentBob);
                
                if(tempAlice == true)
                    mergeAlice+= 1;
                
                if(tempBob == true)
                    mergeBob+= 1;
                
                if(tempAlice == false && tempBob == false)//retundant or the cyclic non-dependent edge//both Alice and Bob don't rquire it connection is already there between these pair of nodes
                    removeEdge+= 1;
            }
            else if(cat == 2){//edge Bob can only access 
                
                //creating dependency of nodes in graph 2
                boolean tempBob= union(u, v, parentBob);
                
                if(tempBob == true)
                    mergeBob+= 1;
                else//no merging of set is done, that means that this edge is not required because it will form cycle or the dependency 
                    removeEdge+= 1;
            }
            else{//edge Alice can only access 
                
                //creating dependency of nodes in graph 1
                boolean tempAlice= union(u, v, parentAlice);
                
                if(tempAlice == true)
                    mergeAlice+= 1; 
                else//no merging of set is done, that means that this edge is not required because it will form cycle or the dependency 
                    removeEdge+= 1;
            }
        }
        if(mergeAlice != n || mergeBob != n)//all node are not connected, connectedness is not maintained 
            return -1;
        return removeEdge;//number of edge removed by maintaining the connectedness 
    }
    
    public int find(int x, int[] parent)
    {
        if(parent[x] == x)//when we found the absolute root or the leader of the set 
            return x;
        
        int temp= find(parent[x], parent);
        
        parent[x]= temp;//Path Compression//child pointing to the absolute root or the leader of the set, while backtracking
        
        return temp;//returning the absolute root 
    }
    
    public boolean union(int x, int y, int[] parent)
    {
        int lx= find(x, parent);//leader of set x or the absolute root
        int ly= find(y, parent);//leader of set y or the absolute root
        
        if(lx != ly){//belong to different set merging 
            
            //Rank Compression is not done, but you can do it 
            parent[lx]= ly;
            
            return true;//union done, dependency created
        }
        else
            return false;//no union done cycle is due to this edge 
    }//Please do Upvote, it helps a lot 
}
class Solution {
public:
    vector < int > Ar , Ap , Br , Bp; // alice and bob parent and rank arrays
    static bool cmp(vector < int > & a , vector < int > & b){
      return a[0] > b[0];
    }
    // lets create the alice graph first
    // find function for finding the parent nodes
    int find1(int x){
     if(x == Ap[x]) return x;
         return Ap[x] = find1(Ap[x]);
    }
    // if nodes are already connected return 1 else make the connection and return 0
    bool union1( int x , int y){
      int parX = find1(x);
    int parY = find1(y);
        if(parX == parY) return 1;
        if(Ar[parX] > Ar[parY]){
          Ap[parY] = parX;
        }
         else if(Ar[parX] < Ar[parY]){
          Ap[parX] = parY;
        }
        else {
           Ap[parY] = parX;
            Ar[parX]++;
        }
        return 0;
    }
    // same thing do for bob graph
     int find2(int x){
     if(x == Bp[x]) return x;
         return Bp[x] = find2(Bp[x]);
    }

    bool union2( int x , int y){
      int parX = find2(x);
    int parY = find2(y);
        if(parX == parY) return 1;
        if(Br[parX] > Br[parY]){
          Bp[parY] = parX;
        }
         else if(Br[parX] < Br[parY]){
          Bp[parX] = parY;
        }
        else {
           Bp[parY] = parX;
            Br[parX]++;
        }
        return 0;
    }

    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
       Ar.resize(n , 1); Ap.resize(n , 1); Br.resize(n , 1); Bp.resize(n , 1);

        for(int i = 0; i<n ; i++){
         Ap[i] = i;
            Bp[i] = i;
        }

        sort(edges.begin() , edges.end() , cmp);
        int ans = 0;
        // give priority to 3rd type of vertices
        for(auto a : edges){
         if(a[0] != 3) continue;
            if(union1(a[1]-1 , a[2]-1))ans++;

           union2(a[1] -1, a[2]-1);

        }
        // now try the edges one by one and check if it the given nodes are already connected in respective alice and bob graph or not
        for(auto a : edges){
        if(a[0] == 3) continue;
            if(a[0] == 1) {
             if(union1(a[1]-1 , a[2]-1))ans++; }

            else {
              if(union2(a[1]-1 , a[2]-1))ans++;}
        }
        int cnt1 = 0, cnt2 = 0;
        for(int i = 0; i< n ; i++){
          if(Ap[i] == i) cnt1++;
            if(Bp[i] == i) cnt2++;
        }
        if(cnt1 >1 | cnt2 >1) return -1;

        return ans;

    }
};
// A common disjoint set class
function DS(n) {
    var root = [...new Array(n + 1).keys()];
    var rank = new Array(n + 1).fill(0);
    this.find = function(v) {
        if (root[v] !== v) root[v] = this.find(root[v]);
        return root[v];
    }
    this.union = function (i, j) {
        var [a, b] = [this.find(i), this.find(j)];
        if (a === b) return false;
        if (rank[a] > rank[b]) root[b] = a;
        else if (rank[a] < rank[b]) root[a] = b;
        else  root[a] = b, rank[b]++;
        return true;
    }
	// check if the nodes 1-n is in the same set
    this.canFullyTraverse = function() {
        var key = this.find(1);
        for (var i = 2; i <= n; i++) {
            if (this.find(i) !== key) return false;
        }
        return true;
    }
}

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var maxNumEdgesToRemove = function(n, edges) {
	// two persons disjoint set
    var ds1 = new DS(n);
    var ds2 = new DS(n);
	// sort edges by type, to make sure we can handle type 3 first
    edges.sort((a, b) => b[0] - a[0]);
    var result = 0;
    edges.forEach(([type, u, v]) => {
		// when edge type is 3, union u, v for both person's ds
		// if they are already in the same set, this edge can be remove, result++
        if (type === 3) {
            var [r1, r2] = [ds1.union(u, v), ds2.union(u, v)];
            if (!r1 && !r2) {
                result++;
            }
		// for specific person
        } else if (type === 1) {
            if (!ds1.union(u, v)) {
                result++;
            }
        } else {
            if (!ds2.union(u, v)) {
                result++;
            }
        }
    });
	// if one person cannot fully traverse, return -1
	// otherwise, return result
    if (ds1.canFullyTraverse() && ds2.canFullyTraverse()) {
        return result;
    }
    return -1;
};
Remove Max Number of Edges to Keep Graph Fully Traversable