Problem 2. Farm Updates

USACO 2022 January Contest, Gold

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$ 次更新后是有关的。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$ 和 $Q$。以下 $Q$ 行每行包含如下格式之一的一次更新操作：

D x A x y R e

输入保证对于 R 类更新，$e$ 不超过已经添加的道路的数量，并且没有两次 R 类更新具有相等的 $e$ 值。

输出格式（输出至终端 / 标准输出）：

输出 $Q$ 行，每行包含一个 $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

输出样例：

7
8
6
9
9

在这个例子中，道路以顺序 $(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 没有额外限制。

供题：Benjamin Qi