P8097 [USACO22JAN] Farm Updates G

Farmer John runs a total of $N$ farms ($1\le N\le 10^5$), numbered $1\ldots N$. Initially, there are no roads connecting these farms, and every farm is actively producing milk. Because the economy is always changing, Farmer John needs to modify his farms according to $Q$ update operations ($0\le Q\le 2\cdot 10^5$). There are three possible types of updates: - `(D x)` Deactivate an active farm $x$, so it no longer produces milk. - `(A x y)` Add a road between two active farms $x$ and $y$. - `(R e)` Remove the $e$-th road that was added earlier ($e = 1$ is the first road that was added). A farm $x$ is called a "relevant" farm if it is actively producing milk, or it can reach another active farm through a sequence of roads. For each farm $x$, compute the largest $i$ ($0\le i\le Q$) such that farm $x$ is relevant after the $i$-th update.

The first line of input contains $N$ and $Q$. The following $Q$ lines each contain one update operation in one of the following formats: ``` D x A x y R e ``` The input guarantees that for updates of type `R`, $e$ does not exceed the number of roads that have already been added, and no two updates of type `R` have the same value of $e$.

Output $N$ lines, each containing an integer in the range $0\ldots Q$.

[Sample Explanation] In this example, the roads $(2,3)$, $(1,2)$, and $(2,4)$ are removed in this order. - Farm $1$ is relevant before the road $(1,2)$ is removed. - Farm $2$ is relevant before the road $(2,4)$ is removed. - Farm $3$ is relevant before the road $(2,3)$ is removed. - Farms $4$ and $5$ are still active after all updates are finished. So they remain relevant all the time, and both of their outputs should be $Q$. [Constraints] - Test cases 2-5 satisfy $N\le 10^3$ and $Q\le 2\cdot 10^3$. - Test cases 6-20 have no additional constraints. Translated by ChatGPT 5