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:

• (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 first road that was added).

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.

Problem credits: Benjamin Qi

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 credits: Benjamin Qi

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\).

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > January > Gold