Union Find Solution || optimal
\n# Approach\n Describe your approach to solving the problem. \n1. Firstly, make two disjointSet one for alice and one for bob.\n2. We will keep 3 counter, for 
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Firstly, make two disjointSet one for alice and one for bob.\n2. We will keep 3 counter, for - alice, bob and both\n3. Now, first check for all the type 3 edges which is common for both alice and bob.\n4. If parents of nodes for Both alice and bob are already same so we will consider to remove it (both++).\n5. Else we will make there parents same.\n6. Now, similar step we will follow again for type 1 and type 2 edges.\n7. As we know, type 1 is for alice and type 2 is for bob\n8. so, if type 1 edge is there and the parent of nodes are already same so we can consider it to remove (alice++).else we will make there parent to be same.\n9. if type 2 edge is there and the parent of nodes are already same so we can consider it to remove (bob++).else we will make there parent to be same.\n10. Finally, before returning your you should check whether all nodes are connected or not (by checking if there parent is same or not) for both alice and bob.\n11. if all the nodes are connected for both of them. then, return ans as alice+bob+both. else return -1\n\n\n# Complexity\n- Time complexity: O(m \u03B1(n)), where m=no. of edges & n=no. of nodes\n \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass disjointSet{\n    vector<int>parent,size;\n    public:\n        disjointSet(int n){\n            parent.resize(n+1);\n            size.resize(n+1,1);\n            for(int i=0; i<=n; i++){\n                parent[i]=i;\n            }\n        }\n        int findParent(int node){\n            if(node==parent[node]){\n                return node;\n            }\n            return parent[node]=findParent(parent[node]);\n        }\n        void unionBySize(int u,int v){\n            int parentOfU=findParent(u);\n            int parentOfV=findParent(v);\n            if(parentOfU==parentOfV) return;\n            if(size[parentOfU] < size[parentOfV]){\n                parent[parentOfU]=parentOfV;\n                size[parentOfV]+=size[parentOfU];\n            }\n            else{\n                parent[parentOfV]=parentOfU;\n                size[parentOfU]+=size[parentOfV];\n            }\n        }\n        bool check(int first,int second){\n            if(findParent(first)==findParent(second)) \n                return true;\n            return false;\n        }\n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        disjointSet ds1(n);\n        disjointSet ds2(n);\n        int alice=0,bob=0,both=0;\n        for(auto it:edges){\n            int type=it[0];\n            int node1=it[1];\n            int node2=it[2];\n            if(type==1 || type==2)continue;\n            if(ds1.check(node1,node2) && ds2.check(node1,node2)){\n                both++;\n            }\n            else{\n                ds1.unionBySize(node1,node2);\n                ds2.unionBySize(node1,node2);\n            }\n        }\n        for(auto it:edges){\n            int type=it[0];\n            int node1=it[1];\n            int node2=it[2];\n            if(type==1){\n                if(ds1.check(node1,node2))alice++;\n                else ds1.unionBySize(node1,node2);\n            }\n            else if(type==2){\n                if(ds2.check(node1,node2))bob++;\n                else ds2.unionBySize(node1,node2);\n            }\n        }\n        unordered_set<int>st1;\n        unordered_set<int>st2;\n        for(int i=1; i<=n; i++){\n            st1.insert(ds1.findParent(i));\n            if(st1.size()>1)break;\n        }\n        for(int i=1; i<=n; i++){\n            st2.insert(ds2.findParent(i));\n            if(st2.size()>1)break;\n        }\n\n        if(st1.size()==1 && st2.size()==1)\n        return alice+bob+both;\n        return -1;\n    }\n};\n\n```
['Union Find', 'Graph', 'C++']