【题目描述】

Farmer John 经营着总共 N 个农场（1≤N≤10^5），编号为 1…N。最初，这些农场之间没有道路连接，并且每个农场都在活跃地生产牛奶。

由于经济的动态性，Farmer John 需要根据 Q 次更新操作（0≤Q≤2×10^5）对他的农场进行改造。更新操作有三种可能的形式：

1.(D x) 停用一个活跃的农场 x，使其不再生产牛奶。

2.(A x y) 在两个活跃的农场 x 和 y 之间添加一条道路。

3.(R e) 删除之前添加的第 e 条道路（e=1 是添加的第一条道路）。

一个农场 x 如果正在活跃地生产牛奶，或者可以通过一系列道路到达另一个活跃的农场，则称之为一个「有关的」农场。对于每个农场 x，计算最大的 i（0≤i≤Q），使得农场 x 在第 i 次更新后是有关的。

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

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

D x

A x y

R e

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

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

输出 Q 行，每行包含一个 0…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≤10^3，Q≤2⋅103Q≤2×10^3。

测试点 6-20 没有额外限制。