Description

Farmer John operates a collection of $N$ farms, convenientlynumbered $1\ldots N$. Initially, there are no roads connecting these farms toeach-other, and each farm is actively producing milk.

Due to the dynamic nature of the economy, Farmer John needs to make changes tohis farms according to a series of $Q$ update operations. Update operations come in three possible forms:

• (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 previously added ($e = 1$ is the firstroad that was added).

A farm $x$ that is actively producing milk, or that can reach another activefarm via a series of roads, is called a "relevant" farm. For each farm $x$,please calculate the maximum $i$ such that $x$ is relevantafter the $i$-th update.

• $1\le N\le 10^5$
• $0\le Q\le 2\cdot 10^5$
• $0\le i\le Q$

Input Format

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 roadsthat have been added so far, and no two updates of type R have the same value of$e$.

Output Format

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

5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3

Scoring

• Tests 2 through 5 satisfy $N\le 10^3$, $Q\le 2\cdot 10^3$
• Test cases 6 through 20 satisfy no additional constraints.

Problem Credit

Problem credits: Benjamin Qi