#3306. 树

内存限制:256 MiB 时间限制:10 Sec

题目描述

给定一棵大小为 n 的有根点权树,支持以下操作:
  • 换根
  • 修改点权 
     • 查询子树最小值

输入格式

  第一行两个整数 n, Q ,分别表示树的大小和操作数。
  接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如 果f = 0,那么i为根。输入数据保证只有i = 1时,f = 0。
  接下来 m 行,为以下格式中的一种:
  • V x y表示把点x的权改为y
  • E x 表示把有根树的根改为点 x
  • Q x 表示查询点 x 的子树最小值

输出格式

  对于每个 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% 的数据:n, Q ≤ 10^5。