class Solution { public: vector <int> d1; vector <int> d2; vector <int> s1; vector <int> s2; int parent(int x, vector <int> &dsu){ if(x == dsu[x]){ return x; }else{ dsu[x] = parent(dsu[x], dsu); } return dsu[x]; } int add(int a, int b, vector <int> &dsu, vector <int> &s){ int p1 = parent(a, dsu); int p2 = parent(b, dsu); if(p1 == p2){ return 1; }else{ dsu[p1] = p2; s[p2] += s[p1]; return 0; } } int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) { d1 = vector <int> (n+1, 0); d2 = vector <int> (n+1, 0); s1= vector <int>(n+1, 1); s2 = vector <int> (n+1, 1); for(int i =0 ; i <= n; ++i){ d1[i] = i; d2[i] = i; } sort(edges.rbegin(), edges.rend()); int ans = 0; for(auto &data: edges){ if(data[0] == 3){ ans += add(data[1], data[2], d1, s1); add(data[1], data[2], d2, s2); }else if(data[0] == 2){ ans += add(data[1], data[2], d1, s1); }else if(data[0] == 1){ ans += add(data[1], data[2], d2, s2); } } if(s1[parent(1, d1)] == n and s2[parent(1, d2)] == n){ return ans; }else{ return -1; } } };