class UnionFind {
  constructor() {
    this.weight = new Map();
  }

  find(node) {
    if (!this.weight.has(node)) {
      this.weight.set(node, {
        key: node,
        value: 1,
      });
    }

    const entry = this.weight.get(node);
    if (entry.key !== node) {
      const newEntry = this.find(entry.key);
      this.weight.set(node, {
        key: newEntry.key,
        value: newEntry.value * entry.value,
      });
    }

    return this.weight.get(node);
  }

  union(dividend, divisor, value) {
    const dividendEntry = this.find(dividend);
    const divisorEntry = this.find(divisor);

    const dividendGid = dividendEntry.key;
    const divisorGid = divisorEntry.key;
    const dividendWeight = dividendEntry.value;
    const divisorWeight = divisorEntry.value;

    if (dividendGid !== divisorGid) {
      const newWeight = (divisorWeight * value) / dividendWeight;
      for (const [key, entry] of this.weight.entries()) {
        if (entry.key === dividendGid) {
          this.weight.set(key, {
            key: divisorGid,
            value: entry.value * newWeight,
          });
        }
      }
      this.weight.set(dividendGid, {
        key: divisorGid,
        value: newWeight,
      });
    }
  }
}

find(node) {
  if (!this.weight.has(node)) {
    this.weight.set(node, {
      key: node,
      value: 1,
    });
  }

  const entry = this.weight.get(node);
  if (entry.key !== node) {
    const newEntry = this.find(entry.key);
    this.weight.set(node, {
      key: newEntry.key,
      value: newEntry.value * entry.value,
    });
  }

  return this.weight.get(node);
}