题目描述

一棵有根点权树有 $n$ 个结点，编号为 $1$ 的结点是根节点，第 $i$ 个结点的父亲结点为 $f_i$，权值为 $v_i$。

接着进行 $Q$ 次以下操作：

• $\texttt{V }x\ \ y$ 表示将点 $x$ 的权修改为 $y$；
• $\texttt{E }x$ 表示把有根树的根改为点 $x$；
• $\texttt{Q }x$ 表示查询点 $x$ 的子树最小值。

输入格式

第一行两个整数 $n,Q$。

接下来 $n$ 行，每行两个整数 $f_i,v_i$。

接下来 $Q$ 行，每行一次操作。

输出格式

对于每次 $\texttt{Q}$ 操作，输出子树最小值。

3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1

1
2
3
4

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,Q\leq 10^5$，$0\leq f_i\leq n$，当且仅当 $i=1$ 时 $f_i=0$，$0\leq v_i\leq 10^4$。