P6971: 农场关系
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
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
没有额外限制。