#USACOC2222B. Farm Updates

Farm Updates

No testdata at current.

题目描述

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

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

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

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

  • 1N1051\le N\le 10^5
  • 0Q21050\le Q\le 2\cdot 10^5
  • 0iQ0\le i\le Q

输入格式

输入的第一行包含 NNQQ。以下 QQ 行每行包含如下格式之一的一次更新操作:

D x
A x y
R e

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

输出格式

输出 QQ 行,每行包含一个 0Q0\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 满足 N103N\le 10^3Q2103Q\le 2\cdot 10^3
  • 测试点 6-20 没有额外限制。

题目提供者

供题:Benjamin Qi