题目描述

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

有 $q$ 次操作分别如下：

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

输入格式

第一行输入两个整数 $n,q$

接下来 $n$ 行每行两个整数 $f_i,v_i$。其中 $1$ 的父亲为 $0$。

接下来 $q$ 行，每行一个操作。

输出格式

针对操作 $3$，输出一个整数代表答案。

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

提示

$1\leq n,q\leq 10^5$，$0\leq f_i\leq n$，$0\leq v_i\leq 10^4$。