{"problem":{"name":"歌姬","description":{"content":"现在 \\*26 的头脑中想着 $n$ 件事情，它们形成一棵树．事情有现实和妄想两种状态．初始时所有事情都是妄想．不妨将事情 $1$ 假设成头脑中这棵树的根．那么一个事情 $u$ 的深度指从事情 $1$ 到事情 $u$ 的简单路径上的事情数（包含端点）． 我们称一个事情的集合 $S$ 为现实联通体，当其满足对于树上任意两个现实事情，其在树上简单路径（包括端点）中的事情都属于 $S$．极小现实连通体","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9620"},"statements":[{"statement_type":"Markdown","content":"现在 \\*26 的头脑中想着 $n$ 件事情，它们形成一棵树．事情有现实和妄想两种状态．初始时所有事情都是妄想．不妨将事情 $1$ 假设成头脑中这棵树的根．那么一个事情 $u$ 的深度指从事情 $1$ 到事情 $u$ 的简单路径上的事情数（包含端点）．\n\n我们称一个事情的集合 $S$ 为现实联通体，当其满足对于树上任意两个现实事情，其在树上简单路径（包括端点）中的事情都属于 $S$．极小现实连通体，即包含事情数最少的现实连通体．\n\n随着时间推移，事情的状态可能发生一些变动．下面 \\*26 和您提及了 $m$ 次事情的变动．变动分为以下两种不同的情况：\n\n1. `Real u` 第 $u$ 件事情变成现实．\n2. `Want u` 第 $u$ 件事情变成妄想．\n\n每次变动后，\\*26 会向您询问：目前至少还需要额外让几个事情变成妄想，才能使最小现实联通体中深度最小的事情的位置发生改变，或使当前头脑中不存在现实事情．\n\n## Input\n\n第一行是两个整数 $n, m$ 表示事情个数和变动个数．\n\n接下来 $n - 1$ 行每行两个整数表示树上的一条边．\n\n接下来 $m$ 行形如：`Real u` 或 `Want u`．表示一次思考．其中 $1\\le u\\le n$．\n\n## Output\n\n共 $m$ 行，每行一个整数，表示第 $i$ 次变动后，您向 \\*26 提供的答案．\n\n[samples]\n\n## Background\n\n> 你如此一来就满足了吗？\n>\n> 没有想过去实现它吗?\n>\n> 为你而设的 为你而设的\n>\n> 可怜的制度化作温柔的义务\n\n## Note\n\n### 样例 #1 说明\n举例最后一次变动结束后的情况．\n\n此时树上除了事情 $1,3,7$ 是妄想，其余是现实．那么此时的最小现实联通体就是 $\\{1,2,4,5,6\\}$．\n\n$\\{2,4,5,6\\}$ 不是最小现实连通体，因为存在两个现实事件如 $2,6$，其简单路径经过 $1$，而 $1$ 不在 $\\{2,4,5,6\\}$ 这个集合里；$\\{1,2,3,4,5,6\\}$ 同样不是最小现实联通体，因为存在一个现实联通体 $\\{1,2,4,5,6\\}$ 的大小小于它．\n\n当我们令事情 $2,4$ 变成妄想后，现实事情仅剩下 $5,6$，这时最小现实连通体为 $\\{5,6\\}$．其中深度最小的事情由原来的 $1$ 变成了现在的 $5$．可以证明这个策略是最优策略之一．\n\n### 数据点约束\n|数据点编号|数据范围|\n|:-:|:-:|\n|$1,2$|$1\\le n,m \\le 20$|\n|$3,4,5$|$1\\le n,m \\le 300$|\n|$6,7,8$|$1\\le n,m \\le 3000$|\n|$9,10,11,12$|$1\\le n, m \\le 39393$|\n|$13 \\sim 20$|$1\\le n, m \\le 2 \\times 10^5$|\n\n对于所有数据，保证在任意一次操作时，变动之前和变动之后事情的状态不一样．","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9620","tags":[],"sample_group":[["7 8\n1 2\n1 5\n2 3\n2 4\n5 6\n5 7\nReal 3\nReal 4\nReal 6\nReal 7\nWant 7\nReal 2\nReal 5\nWant 3\n","1\n1\n1\n2\n1\n1\n2\n2\n"]],"created_at":"2026-03-03 11:09:25"}}