CF1137F Matches Are Not a Child's Play

现在有一棵 $n$ 个节点的无根树，每个节点有权重 $p_i$，初始 $p_i=i$。 我们定义一棵树的删除序列为：每一次将树中权重最小的叶子删掉，将该节点编号加入到当前序列的最末端，最后只剩下一个节点时将该节点的编号加入到结尾。  例如对于上图中的树，它的删除序列为：`2 4 3 1 5`。 现在给出一棵 $n$ 个节点的树，有 $m$ 次操作： `up v`：将 $v$ 号节点的权重 $p_v$ 变为 $\max_{1\le i\le n}p_i + 1$； `when v`：查询 $v$ 在当前树的删除序列中是第几号元素； `compare u v`：查询 $u$ 和 $v$ 在当前树的删除序列中谁更靠前。

第一行两个正整数 $n,q(1 \leq n , q \leq 200000)$ 表示树的点数和操作数。 接下来 $n-1$ 行每行 $2$ 个正整数 $u,v(1 \leq u,v \leq n)$ 表示树上的一条边。 接下来 $q$ 行每行描述一个操作。

每一个询问输出一行。 对于 `when v` 询问，输出一个正整数表示 $v$ 是当前删除序列的哪一个元素。 对于 `compare u v` 询问，如果 $u$ 在删除序列中更靠前则输出 $u$，否则输出 $v$。

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] $ .