시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 170 | 63 | 55 | 35.256% |
Farmer John operates a collection of $N$ farms ($1\le N\le 10^5$), conveniently numbered $1\ldots N$. Initially, there are no roads connecting these farms to each-other, and each farm is actively producing milk.
Due to the dynamic nature of the economy, Farmer John needs to make changes to his farms according to a series of $Q$ update operations ($0\le Q\le 2\cdot 10^5$). Update operations come in three possible forms:
A farm $x$ that is actively producing milk, or that can reach another active farm via a series of roads, is called a "relevant" farm. For each farm $x$, please calculate the maximum $i$ ($0\le i\le Q$) such that $x$ is relevant after the $i$-th update.
The first line of input contains $N$ and $Q$. The next $Q$ lines each contain an update of one of the following forms:
D x A x y R e
It is guaranteed that for updates of type R, $e$ is at most the number of roads that have been added so far, and no two updates of type R have the same value of $e$.
Please output $N$ lines, each containing an integer in the range $0\ldots Q$.
5 9 A 1 2 A 2 3 D 1 D 3 A 2 4 D 2 R 2 R 1 R 3
7 8 6 9 9
In this example, roads are removed in the order $(2,3), (1,2), (2,4)$.