Union-Find with Rollback — Offline Dynamic

Deque history = new ArrayDeque<>(); // {node, oldParent, oldRank}
void union(int x, int y) {
  int px = find(x), py = find(y); // NO path compression
  if (px == py) { history.push(new int[]{-1, -1, -1}); return; }
  if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
  history.push(new int[]{py, parent[py], rank[px]});
  parent[py] = px;
  if (rank[px] == rank[py]) rank[px]++;
}
void rollback() {
  int[] u = history.pop();
  if (u[0] == -1) return;
  parent[u[0]] = u[1];
  rank[parent[u[0]]] = u[2];
}