USACO

USACO 2022 January Contest, Gold

Problem 2. Farm Updates

Contest has ended.

Log in to allow submissions in analysis mode

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.

INPUT FORMAT (input arrives from the terminal / stdin):

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$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Please output

$N$ lines, each containing an integer in the range

$0\ldots Q$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

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

Farm $1$ is relevant just before $(1,2)$ is removed.
Farm $2$ is relevant just before $(2,4)$ is removed.
Farm $3$ is relevant just before $(2,3)$ is removed.
Farms $4$ and $5$ are still active after all queries. Therefore they both stay relevant, and the output for both should be $Q$ .

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

Contest has ended. No further submissions allowed.