#19. 隐藏章节 · 动态森林

内存限制:256 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: xjc

题目描述

有一枚蛋糕可能被lqq赋予了魔法,它在导办门口长成了一棵蛋糕树!lqq希望站到蛋糕树的重心和大家合影,希望你帮忙找到他应该站的位置。

对于树中的任意节点,去掉该节点可使产生的子树的节点数中的最大值最小,则该节点定义为树的重心。

一棵树可能存在多个重心。

举两个例子:

例1

上图中有一个重心:号节点(将其去除后,树分离成三个连通块,大小分别为,最大的一块大小为(如下图)

另一个比较像重心的点是,但将其去除后树分离成大小为的三个连通块,最大一块大小为,所以号节点不是重心(如下图)

例2

上图中有两个重心,号节点和号节点都可以成为重心

现在有一个个节点的树,要求支持动态加边,删边,求出当前森林中的所有重心。

输入格式

行,输入,分别表示树的节点数量和增删边操作的数量。

~行,每行输入两个整数,表示之间存在一条边。

接下来的行中,每行有三个整数

如果,则代表之间新建一条边。

如果,则代表之间的边被删除。

注意,数据不保证新建边的操作一定能成功,也不保证删边时的边一定存在,需要程序自行判断。

输出格式

对于次操作,每次操作输出两行。

如果该次操作是成功的,则首先输出"success",否则首先输出"error"。

然后求出在经过该操作后,新的森林中的所有重心,并以升序顺序输出。(即使该操作失败了也要输出森林中的所有重心)

样例

【样例输入】

9 10
3 4
2 3
1 4
6 1
7 2
8 4
2 9
3 5
1 7 6
1 6 3
2 4 8
2 6 1
2 3 4
2 4 1
2 7 2
2 3 5
2 4 4
2 7 9

【样例输出】

error
3
error
3
success
3 8
success
3 6 8
success
1 2 4 6 8
success
1 2 4 6 8
success
1 2 3 4 6 7 8
success
1 2 4 5 6 7 8
error
1 2 4 5 6 7 8
error
1 2 4 5 6 7 8

解释: 前两个加边操作,由于本来就在一个连通分量中,所以操作失败,森林(此时退化成一棵树)重心保持为

删掉后,重心变成

删掉后,重心变成

删掉后,重心变成

删掉后,重心保持不变

删掉后,重心变成

删掉后,重心变成

之后两个删边操作,因为原边不存在,删除失败

数据范围与提示

通告标题

通告内容

已知晓