Problem: first_time_ch1 (2022 round3)

**Note: The only difference between this and [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-3/problems/D2/) is that here, you only need to find the answer for a single \(K\).**

Boss Rob ain’t Som Tawyer, but he can paint a fence alright.

Rob's fence is made of \(N\) wooden stakes, numbered \(1\) to \(N\) from left to right. Initially (at time \(0\)), the \(i\)th stake is of color \(i\). There is a fencepost before stake \(1\) and after stake \(N\), as well as after every \(K\)th stake starting from the left.

Rob has a simple and joyful plan to repaint his fence, consisting of \(M\) moments in time. At time \(i\), he'll repaint all stakes which are color \(A_i\) to color \(B_i\). Doing so, when would be the *first time* that all pairs of stakes not separated by a fencepost have the same color? If it will never occur, consider the answer to be \(-1\).


# Constraints

\(1 \le T \le 40\)
\(1 \le N, M \le 600{,}000\)
\(1 \le K \le N\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)

The sum of \(N\) across all test cases is at most \(4{,}000{,}000\).
The sum of \(M\) across all test cases is at most \(4{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. For the \(i\)th test case, there is first a line containing three space-separated integers \(N\), \(M\), and \(K\). Then, \(M\) lines follow, the \(i\)th of which contains two space-separated integers \(A_i\) and \(B_i\).


# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the first time that the condition is satisfied, or \(-1\) if will never be.

# Sample Explanation

The progressions of fences for the first two sample cases are depicted below:

{{PHOTO_ID:1207042806525380|WIDTH:700}}

In the first case, all stakes between fenceposts will have the same color after time \(2\).

In the second case, all stakes between fenceposts will have the same color after time \(3\).

In the third case, the fence progresses as follows:

{{PHOTO_ID:1173386423530703|WIDTH:700}}

At no point in time will all stakes between pairs of fenceposts have the same color.



Sample input:
3
5 4 2
2 1
3 4
1 4
5 4
3 4 3
1 2
2 1
1 3
3 1
8 6 3
1 4
2 3
4 3
8 7
6 5
7 5


Sample output:
Case #1: 2
Case #2: 3
Case #3: -1


Solution: We can use a disjoint set union (DSU) data structure to maintain the colors of all stakes. We'll keep track of the color of a component by updating the color of that set's representation (a.k.a its root or parent), and also the inverse. The repaint function will look something like this:

```
  void repaint(int c1, int c2) {
    int p1 = parent_of_color[c1];
    if (p1 == -1) {
      return;
    }
    int p2 = parent_of_color[c2];
    if (p2 == -1) {
      color_of_parent[p1] = c2;
      parent_of_color[c1] = -1;
      parent_of_color[c2] = p1;
      return;
    }
    unite_sets(p1, p2);
    color_of_parent[p1] = color_of_parent[p2] = c2;
    parent_of_color[c1] = -1;
    parent_of_color[c2] = parent[p2];
  }
```
We also need to set \(\text{color\_of\_parent}[i] = \text{color\_of\_parent}[j]\) when updating \(\text{parent}[i] = j\) elsewhere in the DSU.

For this problem, there are \(B = \lceil N/K \rceil\) different "bins", for which we'd like to see if the colors are uniform for all of the bins after each repainting.

One possible idea is to maintain \(B\) hash tables \(H_{1..B}\), one for each bin, where \(H_{b}[r]\) stores the number of balls with DSU representative \(r\) in bin \(b\). If \(H_b[r]\) drops to zero, we delete the key \(r\) it so that the number of keys in \(H_b\) is alway equal to the number of distinct representatives in bin \(b\). Note that if there is only \(1\) key in \(H_b\), then bin \(b\) is uniformly colored. We increment \(H_{\text{bin}(i)}[j]\) whenever we update \(\text{parent}[i] = j\) in the DSU (and decrement the old parent's count).

We can also maintain another hash set \(S\) of the bin numbers which are currently uniform. Check if the size of \(H_b\) changed from \(2\) to \(1\) after every update (if so, add \(b\) to \(S\)) or if the size \(H_b\) changed from \(1\) to \(2\) (then delete \(b\) from S). The first time that \(|S| = B\) is the answer.

The only catch is that using the classic path compression DSU implementation, the \(\text{parent}[]\) array is lazily updated when \(\text{find\_parent}()\) is called (and might not be consistent for all nodes after every \(\text{unite\_sets}()\) call). Instead, we can [store the DSU explicitly in a set list](https://cp-algorithms.com/data_structures/disjoint_set_union.html#storing-the-dsu-explicitly-in-a-set-list-applications-of-this-idea-when-merging-various-data-structures), which guarantees consistency after each union. The running time across \(N\) elements and \(M\) union operations is \(\mathcal{O}(M + N \log N)\) for this variant of DSU, where \(\mathcal{O}(N \log N)\) is the max number times an element will have to be transferred from one set to another. Each such move requires updating \(H\) and \(S\) in \(\mathcal{O}(1)\) time. Thus the overall time complexity is \(\mathcal{O}(M + N \log N)\).


Code: #include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int N, M, K;
vector<unordered_map<int, int>> C;  // C[b][p] = bin b stakes with DSU parent p
unordered_set<int> S;               // Set of currently uniform bin numbers

void update_parent(int i, int r_old, int r_new) {
  if (r_old == r_new) {
    return;
  }
  auto &bin = C[i / K];
  if (--bin[r_old] == 0) {
    bin.erase(r_old);
  }
  bin[r_new]++;
  if (bin.size() == 1) {
    S.insert(i / K);
  } else {
    S.erase(i / K);
  }
}

struct disjoint_sets {
  vector<vector<int>> values;
  vector<int> parent, color_of_parent, parent_of_color;

 public:
  disjoint_sets(int N)
      : values(N), parent(N), color_of_parent(N), parent_of_color(N) {
    for (int i = 0; i < N; i++) {
      values[i] = {i};
      parent[i] = i;
      color_of_parent[i] = i;
      parent_of_color[i] = i;
    }
  }

  // O(M + N log N) across M calls to unite().
  void unite(int a, int b) {
    a = parent[a];
    b = parent[b];
    if (a != b) {
      if (values[a].size() < values[b].size()) {
        swap(a, b);
      }
      while (!values[b].empty()) {
        int v = values[b].back();
        values[b].pop_back();
        update_parent(v, parent[v], a);
        parent[v] = a;
        color_of_parent[v] = color_of_parent[a];
        values[a].push_back(v);
      }
    }
  }

  void repaint(int c1, int c2) {
    int pa = parent_of_color[c1];
    if (pa == -1) {
      return;
    }
    color_of_parent[pa] = c2;
    parent_of_color[c1] = -1;
    int pb = parent_of_color[c2];
    if (pb == -1) {
      parent_of_color[c2] = pa;
      return;
    }
    unite(pa, pb);
    color_of_parent[pb] = c2;
    parent_of_color[c2] = parent[pb];
  }
};

int solve() {
  cin >> N >> M >> K;
  int nbins = (N + K - 1) / K;  // ceil(N / K)
  // Initialize parent counts.
  C.assign(nbins, {});
  for (int i = 0; i < N; i++) {
    C[i / K][i]++;
  }
  S.clear();
  for (int b = 0; b < nbins; b++) {
    if (C[b].size() == 1) {
      S.insert(b);
    }
  }
  int ans = (S.size() == nbins ? 0 : -1);
  disjoint_sets DS(N);
  for (int i = 0, a, b; i < M; i++) {
    cin >> a >> b;
    DS.repaint(--a, --b);
    if (S.size() == nbins && ans < 0) {
      ans = i + 1;
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}