P8097 [USACO22JAN] Farm Updates G

Farmer John 经营着总共 $N$ 个农场（$1\le N\le 10^5$），编号为 $1\ldots N$。最初，这些农场之间没有道路连接，并且每个农场都在活跃地生产牛奶。 由于经济的动态性，Farmer John 需要根据 $Q$ 次更新操作（$0\le Q\le 2\cdot 10^5$）对他的农场进行改造。更新操作有三种可能的形式： - `(D x)` 停用一个活跃的农场 $x$，使其不再生产牛奶。 - `(A x y)` 在两个活跃的农场 $x$ 和 $y$ 之间添加一条道路。 - `(R e)` 删除之前添加的第 $e$ 条道路（$e = 1$ 是添加的第一条道路）。 一个农场 $x$ 如果正在活跃地生产牛奶，或者可以通过一系列道路到达另一个活跃的农场，则称之为一个「有关的」农场。对于每个农场 $x$，计算最大的 $i$（$0\le i\le Q$），使得农场 $x$ 在第 $i$ 次更新后是有关的。

无

无

【样例解释】 在这个例子中，道路以顺序 $(2,3), (1,2), (2,4)$ 被删除。 - 农场 $1$ 在道路 $(1,2)$ 被删除之前是有关的。 - 农场 $2$ 在道路 $(2,4)$ 被删除之前是有关的。 - 农场 $3$ 在道路 $(2,3)$ 被删除之前是有关的。 - 农场 $4$ 和 $5$ 在所有更新结束后仍然是活跃的。所以它们一直保持为有关的，两者的输出均应为 $Q$。 【数据范围】 - 测试点 2-5 满足 $N\le 10^3$，$Q\le 2\cdot 10^3$。 - 测试点 6-20 没有额外限制。