Problem Description

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.

Input Format

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 Format

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

Hint

[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