Farm Updates

문제

Farmer John operates a collection of $NN$ farms ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$), conveniently numbered $1\dots N1\backslash 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 $QQ$ update operations ($0\le Q\le 2\cdot {10}^{5}0\backslash le\; Q\backslash le\; 2\backslash cdot\; 10^5$). Update operations come in three possible forms:

• (D x) Deactivate an active farm $xx$, so it no longer produces milk.
• (A x y) Add a road between two active farms $xx$ and $yy$.
• (R e) Remove the $ee$th road that was previously added ($e=1e\; =\; 1$ is the first road that was added).

A farm $xx$ 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 $xx$, please calculate the maximum $ii$ ($0\le i\le Q0\backslash le\; i\backslash le\; Q$) such that $xx$ is relevant after the $ii$-th update.

입력

The first line of input contains $NN$ and $QQ$. The next $QQ$ 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, $ee$ 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 $ee$.

출력

Please output $NN$ lines, each containing an integer in the range $0\dots Q0\backslash ldots\; Q$.

힌트

In this example, roads are removed in the order $(2,3),(1,2),(2,4)(2,3),\; (1,2),\; (2,4)$.

• Farm $11$ is relevant just before $(1,2)(1,2)$ is removed.
• Farm $22$ is relevant just before $(2,4)(2,4)$ is removed.
• Farm $33$ is relevant just before $(2,3)(2,3)$ is removed.
• Farms $44$ and $55$ are still active after all queries. Therefore they both stay relevant, and the output for both should be $QQ$.

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