题目描述

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

由于经济的动态性，Farmer John 需要根据 $Q$ 次更新操作对他的农场进行改造。更新操作有三种可能的形式：

• (D x) 停用一个活跃的农场 $x$，使其不再生产牛奶。
• (A x y) 在两个活跃的农场 $x$ 和 $y$ 之间添加一条道路。
• (R e) 删除之前添加的第 $e$ 条道路（$e = 1$ 是添加的第一条道路）。

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

• $1\le N\le 10^5$
• $0\le Q\le 2\cdot 10^5$
• $0\le i\le Q$

输入格式

输入的第一行包含 $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

5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3

测试点性质

• 测试点 2-5 满足 $N\le 10^3$，$Q\le 2\cdot 10^3$。
• 测试点 6-20 没有额外限制。

题目提供者

供题：Benjamin Qi