Farmer John 经营着总共 N 个农场（1≤N≤10$^5$），编号为 1…N。最初，这些农场之间没有道路连接，并且每个农场都在活跃地生产牛奶。由于经济的动态性，Farmer John 需要根据 Q 次更新操作（0≤Q≤2⋅10$^5$）对他的农场进行改造。更新操作有三种可能的形式：

• (D x) 停用一个活跃的农场 x，使其不再生产牛奶。
• (A x y) 在两个活跃的农场 x 和 y 之间添加一条道路。
• (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⋅10$^3$。
• 测试点 6-20 没有额外限制。