1
// A common disjoint set class
2
function DS(n) {
3
  var root = [...new Array(n + 1).keys()];
4
  var rank = new Array(n + 1).fill(0);
5
  this.find = function (v) {
6
    if (root[v] !== v) root[v] = this.find(root[v]);
7
    return root[v];
8
  };
9
  this.union = function (i, j) {
10
    var [a, b] = [this.find(i), this.find(j)];
11
    if (a === b) return false;
12
    if (rank[a] > rank[b]) root[b] = a;
13
    else if (rank[a] < rank[b]) root[a] = b;
14
    else (root[a] = b), rank[b]++;
15
    return true;
16
  };
17
  // check if the nodes 1-n is in the same set
18
  this.canFullyTraverse = function () {
19
    var key = this.find(1);
20
    for (var i = 2; i <= n; i++) {
21
      if (this.find(i) !== key) return false;
22
    }
23
    return true;
24
  };
25
}
26

27
/**
28
 * @param {number} n
29
 * @param {number[][]} edges
30
 * @return {number}
31
 */
32
var maxNumEdgesToRemove = function (n, edges) {
33
  // two persons disjoint set
34
  var ds1 = new DS(n);
35
  var ds2 = new DS(n);
36
  // sort edges by type, to make sure we can handle type 3 first
37
  edges.sort((a, b) => b[0] - a[0]);
38
  var result = 0;
39
  edges.forEach(([type, u, v]) => {
40
    // when edge type is 3, union u, v for both person's ds
41
    // if they are already in the same set, this edge can be remove, result++
42
    if (type === 3) {
43
      var [r1, r2] = [ds1.union(u, v), ds2.union(u, v)];
44
      if (!r1 && !r2) {
45
        result++;
46
      }
47
      // for specific person
48
    } else if (type === 1) {
49
      if (!ds1.union(u, v)) {
50
        result++;
51
      }
52
    } else {
53
      if (!ds2.union(u, v)) {
54
        result++;
55
      }
56
    }
57
  });
58
  // if one person cannot fully traverse, return -1
59
  // otherwise, return result
60
  if (ds1.canFullyTraverse() && ds2.canFullyTraverse()) {
61
    return result;
62
  }
63
  return -1;
64
};