CF1137F.Matches Are Not a Child's Play

Lena is playing with matches. The natural question arising in the head of any child playing with matches is whether it's possible to set a tree on fire with a matches, or not.

Let's say, that the tree is a connected graph without cycles and the vertices are labeled with integers $1, 2, \ldots, n$. Also every vertex $v$ has some integer priority $p_v$ associated with it. All priorities are distinct.

It turns out, that if you set a tree on fire, it will burn to nothing. However, this process doesn't happen instantly. At the beginning, burns out the leaf (a vertex is called to be a leaf if it has only one adjacent vertex) of the tree of the minimum priority. Then burns out the leaf of the minimal priority of the remaining tree, and so on. This way, the vertices turn into the leaves and burn out until only one vertex remains. Then this vertex burns out as well.

Lena has prepared a tree of $n$ vertices and every vertex in it has a priority $p_v = v$. Lena is very curious about burning out this tree. However, she understands, that if she will burn the tree now, then it will disappear completely. Lena is a kind girl and she will feel bad for the burned tree, so she wants to study the process of burning the tree only in her mind. Lena wants to process $q$ queries, each of them is one of three following types:

• "up $v$", assign the vertex $v$ priority $1 + \max{p_1, p_2, \ldots, p_n}$;
• "when $v$", find the step at which the vertex $v$ will burn out, if the tree would be set on fire now;
• "compare $v$ $u$", find out which of the vertices $v$ and $u$ will burn out first, if the tree would be set on fire now.

Notice, that if all priorities would be distinct, then after the "up" query they will stay distinct as well. Initially all priorities are distinct, hence during any (purely hypothetical of course) burning of the tree, all leafs would have distinct priorities.

莉娜正在玩火柴。任何一个玩火柴的孩子脑海中自然会浮现的问题是：能否用火柴点燃一棵树？

我们定义，树是一个无环的连通图，其顶点被标记为整数 $1, 2, \ldots, n$。此外，每个顶点 $v$ 都关联一个整数优先级 $p_v$，且所有优先级互不相同。

事实证明，若将一棵树点燃，它最终会完全烧尽。然而，这一过程并非瞬间完成：初始时，树中优先级最小的叶子节点（即仅与一个相邻顶点相连的顶点）首先燃烧；接着，在剩余的树中，优先级最小的叶子节点继续燃烧；依此类推。在此过程中，不断有顶点变为叶子并被烧毁，直至仅剩一个顶点；最后，该顶点也被烧毁。

莉娜已准备了一棵含 $n$ 个顶点的树，其中每个顶点 $v$ 的初始优先级为 $p_v = v$。莉娜对这棵树的燃烧过程非常好奇。但她意识到，若此时真的点燃这棵树，它将彻底消失。莉娜是个善良的女孩，她会为被烧毁的树感到难过，因此她只想在脑海中模拟整个燃烧过程。为此，莉娜需要处理 $q$ 个查询，每个查询属于以下三种类型之一：

• “up $v$”：将顶点 $v$ 的优先级设为 $1 + \max{p_1, p_2, \ldots, p_n}$；
• “when $v$”：若此时点燃该树，求顶点 $v$ 在第几步被烧毁；
• “compare $v$ $u$”：若此时点燃该树，判断顶点 $v$ 和 $u$ 中哪一个先被烧毁。

注意：若所有优先级原本互不相同，则执行 “up” 查询后它们仍将保持互异。初始时所有优先级互不相同，因此在任何（当然纯属假设的）燃烧过程中，所有叶子节点的优先级也始终互不相同。

The first line contains two integers $n$ and $q$ ($2 \le n \le 200\,000$, $1 \le q \le 200\,000$) — the number of vertices in the tree and the number of queries.

The $i$-th of the following $n - 1$ lines contains two integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$), denoting the endpoints of the $i$-th edge.

Each of the remaining $q$ lines contains a query of one of the following three types:

• "up $v$" ($1 \le v \le n$) — change the priority of vertex $v$;
• "when $v$" ($1 \le v \le n$) — determine the step at which the vertex $v$ will burn out;
• "compare $v$ $u$" ($1 \le v, u \le n$, $v \ne u$) — determine which of vertices $v$ and $u$ will burn out earlier in the current tree.

It's guaranteed, that there is at least one query of type "when" or "compare".

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 200\,000$，$1 \le q \le 200\,000$）—— 分别表示树中顶点的数量和查询的数量。

接下来的 $n - 1$ 行中，第 $i$ 行包含两个整数 $v_i$、$u_i$（$1 \le v_i, u_i \le n$），表示第 $i$ 条边的两个端点。

剩余的 $q$ 行中，每行包含以下三种类型之一的查询：

• “up $v$”（$1 \le v \le n$）—— 修改顶点 $v$ 的优先级；
• “when $v$”（$1 \le v \le n$）—— 确定顶点 $v$ 在当前树中燃烧殆尽的步骤；
• “compare $v$ $u$”（$1 \le v, u \le n$，且 $v \ne u$）—— 确定在当前树中，顶点 $v$ 和 $u$ 中哪一个会更早燃烧殆尽。

保证至少存在一个类型为 “when” 或 “compare” 的查询。

For every query of type "when" print one integer in range from $1$ to $n$ — the step at which the vertex $v$ will burn out.

For every query of type "compare" print either $v$ or $u$, depending on which one will burn out earlier.

对于每个类型为“when”的查询，输出一个在 $1$ 到 $n$ 范围内的整数——即顶点 $v$ 燃尽的步数。

对于每个类型为“compare”的查询，输出 $v$ 或 $u$ 中较早燃尽的那个顶点。

In the first example, the process of burning of the tree is illustrated on the following picture:

In particular, the vertices of the tree will burn out in the following order: $[2, 4, 3, 1, 5]$.

In the second example, after applying the "up" operation, the order of vertices will change to: $[2, 4, 3, 5, 1]$.

在第一个例子中，树的燃烧过程如下图所示：

具体而言，树的顶点将按如下顺序烧尽：$[2, 4, 3, 1, 5]$。

在第二个例子中，应用“上移”操作后，顶点的顺序将变为：$[2, 4, 3, 5, 1]$。