A region has n towns numbered 0 .. n-1 and two-way roads roads[i] = [a, b]. Road works will close roads one after another: closures is a list of distinct road indices, and closures[k] is the k-th road to close. Closed roads never reopen.
A district is a maximal group of towns that are still mutually reachable over open roads. Return a list whose k-th entry is the number of districts right after the first k + 1 closures.
Examples
Input: n = 4, roads = [[0, 1], [1, 2], [2, 3], [3, 0]], closures = [0, 2]
Output: [1, 2]
Explanation: closing [0, 1] leaves the path 1-2-3-0; closing [2, 3] as well leaves {1, 2} and {3, 0}.
Input: n = 3, roads = [[0, 1], [0, 1], [1, 2]], closures = [1, 0, 2]
Output: [1, 2, 3]
Explanation: road 1 duplicates road 0, so closing it first changes nothing.
Constraints
1 <= n <= 10**4,0 <= len(roads) <= 2 * 10**4,0 <= len(closures) <= len(roads),0 <= a, b < n- Target: O((n + R) * alpha(n)) time. Recomputing the districts from scratch after every closure is too slow.
Goals
- Turn a sequence of deletions into a sequence of insertions by reversing time
- Record answers in reverse and flip them at the end
- Explain why union-find cannot delete edges directly