#USACOC2222B. Farm Updates
Farm Updates
No testdata at current.
题目描述
Farmer John 经营着总共 个农场,编号为 。最初,这些农场之间没有道路连接,并且每个农场都在活跃地生产牛奶。
由于经济的动态性,Farmer John 需要根据 次更新操作对他的农场进行改造。更新操作有三种可能的形式:
- (D x) 停用一个活跃的农场 ,使其不再生产牛奶。
- (A x y) 在两个活跃的农场 和 之间添加一条道路。
- (R e) 删除之前添加的第 条道路( 是添加的第一条道路)。
一个农场 如果正在活跃地生产牛奶,或者可以通过一系列道路到达另一个活跃的农场,则称之为一个「有关的」农场。对于每个农场 ,计算最大的 ,使得农场 在第 次更新后是有关的。
输入格式
输入的第一行包含 和 。以下 行每行包含如下格式之一的一次更新操作:
D x
A x y
R e
输入保证对于 R 类更新, 不超过已经添加的道路的数量,并且没有两次 R 类更新具有相等的 值。
输出格式
输出 行,每行包含一个 范围内的整数。
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 满足 ,。
- 测试点 6-20 没有额外限制。
题目提供者
供题:Benjamin Qi