P9620 歌姬

> 你如此一来就满足了吗？ > > 没有想过去实现它吗? > > 为你而设的 为你而设的 > > 可怜的制度化作温柔的义务

现在 \*26 的头脑中想着 $n$ 件事情，它们形成一棵树．事情有现实和妄想两种状态．初始时所有事情都是妄想．不妨将事情 $1$ 假设成头脑中这棵树的根．那么一个事情 $u$ 的深度指从事情 $1$ 到事情 $u$ 的简单路径上的事情数（包含端点）． 我们称一个事情的集合 $S$ 为现实联通体，当其满足对于树上任意两个现实事情，其在树上简单路径（包括端点）中的事情都属于 $S$．极小现实连通体，即包含事情数最少的现实连通体． 随着时间推移，事情的状态可能发生一些变动．下面 \*26 和您提及了 $m$ 次事情的变动．变动分为以下两种不同的情况： 1. `Real u` 第 $u$ 件事情变成现实． 2. `Want u` 第 $u$ 件事情变成妄想． 每次变动后，\*26 会向您询问：目前至少还需要额外让几个事情变成妄想，才能使最小现实联通体中深度最小的事情的位置发生改变，或使当前头脑中不存在现实事情．

第一行是两个整数 $n, m$ 表示事情个数和变动个数． 接下来 $n - 1$ 行每行两个整数表示树上的一条边． 接下来 $m$ 行形如：`Real u` 或 `Want u`．表示一次思考．其中 $1\le u\le n$．

共 $m$ 行，每行一个整数，表示第 $i$ 次变动后，您向 \*26 提供的答案．

### 样例 #1 说明 举例最后一次变动结束后的情况． 此时树上除了事情 $1,3,7$ 是妄想，其余是现实．那么此时的最小现实联通体就是 $\{1,2,4,5,6\}$． $\{2,4,5,6\}$ 不是最小现实连通体，因为存在两个现实事件如 $2,6$，其简单路径经过 $1$，而 $1$ 不在 $\{2,4,5,6\}$ 这个集合里；$\{1,2,3,4,5,6\}$ 同样不是最小现实联通体，因为存在一个现实联通体 $\{1,2,4,5,6\}$ 的大小小于它． 当我们令事情 $2,4$ 变成妄想后，现实事情仅剩下 $5,6$，这时最小现实连通体为 $\{5,6\}$．其中深度最小的事情由原来的 $1$ 变成了现在的 $5$．可以证明这个策略是最优策略之一． ### 数据点约束 |数据点编号|数据范围| |:-:|:-:| |$1,2$|$1\le n,m \le 20$| |$3,4,5$|$1\le n,m \le 300$| |$6,7,8$|$1\le n,m \le 3000$| |$9,10,11,12$|$1\le n, m \le 39393$| |$13 \sim 20$|$1\le n, m \le 2 \times 10^5$| 对于所有数据，保证在任意一次操作时，变动之前和变动之后事情的状态不一样．