#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
#define INF 1e9
using namespace std;
struct node{int y,next;}e[MAXN<<1];
int n,m,dfs_clock,len,root,v[MAXN],L[MAXN],R[MAXN],f[MAXN],Link[MAXN],deep[MAXN],anc[MAXN][25],tr[MAXN<<2];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
void dfs(int x){
	L[x]=++dfs_clock;  anc[x][0]=f[x];
	for(int i=1;i<=20;++i)  anc[x][i]=anc[anc[x][i-1]][i-1];
	for(int i=Link[x];i;i=e[i].next)if(e[i].y!=f[x]){
		deep[e[i].y]=deep[x]+1;  dfs(e[i].y);
	}
	R[x]=dfs_clock;
}
void change(int p,int l,int r,int x,int v){
	if(l==r)  {tr[p]=v; return;}
	int mid=(l+r)>>1;
	if(x<=mid)  change(p<<1,l,mid,x,v);
	else change(p<<1|1,mid+1,r,x,v);
	tr[p]=min(tr[p<<1],tr[p<<1|1]);
}
int query(int p,int l,int r,int x,int y){
	if(x>r||y<l)  return INF;
	if(x<=l&&y>=r)  return tr[p];
	int mid=(l+r)>>1;
	return min(query(p<<1,l,mid,x,y),query(p<<1|1,mid+1,r,x,y));
}
int getans(int x){
	if(x==root)  return query(1,1,n,1,n);
	else if(L[x]<=L[root]&&R[x]>=R[root]){
		int y=root;
		for(int i=20;i>=0;--i)if(deep[anc[y][i]]>deep[x])  y=anc[y][i];
		return min(query(1,1,n,1,L[y]-1),query(1,1,n,R[y]+1,n));
	}
	else return query(1,1,n,L[x],R[x]);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  deep[1]=1;
	for(int i=1;i<=n;++i){
		f[i]=read();  v[i]=read();
		insert(i,f[i]);  insert(f[i],i);
	}
	dfs(1);	 root=1;
	for(int i=1;i<=n;++i) change(1,1,n,L[i],v[i]);
	for(int i=1;i<=m;++i){
		char ch[5]; scanf("%s",ch); int x,y;
		switch(ch[0]){
			case 'V':x=read(),y=read();change(1,1,n,L[x],y);break;
			case 'E':x=read(),root=x;break;
			case 'Q':x=read();printf("%d\n",getans(x));break;
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
struct node{int y,next;}e[MAXN<<1];
int n,m,len,Link[MAXN],f[MAXN],v[MAXN],tag[MAXN],mn[MAXN],sta[MAXN],son[MAXN][2];
multiset<int>S[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
namespace Link_Cut_Tree{
	bool get(int x) {return son[f[x]][1]==x;}
	bool isroot(int x){return (son[f[x]][0]!=x&&son[f[x]][1]!=x);}
	void updata(int x){
		mn[x]=(*S[x].begin());
		if(son[x][0])  cmin(mn[x],mn[son[x][0]]);
		if(son[x][1])  cmin(mn[x],mn[son[x][1]]);
	}
	void pushdown(int x){
		if(tag[x]){
			swap(son[x][0],son[x][1]);
			tag[son[x][0]]^=1;  tag[son[x][1]]^=1;
			tag[x]=0;
		}
	}
	void rotate(int x){
		int y=f[x],z=f[y],which=get(x);
		if(!isroot(y))  son[z][son[z][1]==y]=x;
		son[y][which]=son[x][which^1];  f[son[y][which]]=y;
		son[x][which^1]=y;  f[y]=x;  f[x]=z;
		updata(y);  updata(x);
	}
	void splay(int x){
		int top(0);  sta[++top]=x;
		for(int i=x;!isroot(i);i=f[i])sta[++top]=f[i];
		for(int i=top;i;--i)  pushdown(sta[i]);
		for(int y=f[x];!isroot(x);rotate(x),y=f[x])
			if(!isroot(y))  rotate(get(x)==get(y)?y:x);
	}
	void access(int x){
		for(int temp=0;x;temp=x,x=f[x]){
			splay(x);
			if(son[x][1])  S[x].insert(mn[son[x][1]]);
			if(temp)  S[x].erase(S[x].find(mn[temp]));
			son[x][1]=temp;
			updata(x);
		}
	}
	void reverse(int x){access(x);splay(x);tag[x]^=1;}
}using namespace Link_Cut_Tree;
void dfs(int x){
	for(int i=Link[x];i;i=e[i].next)if(e[i].y!=f[x]){
		dfs(e[i].y);
		S[x].insert(mn[e[i].y]);
	}
	updata(x);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();
	for(int i=1;i<=n;++i){
		f[i]=read();  v[i]=read();  S[i].insert(v[i]);
		insert(f[i],i);  insert(i,f[i]);
	}
	dfs(1);  char ch[5];
	for(int i=1;i<=m;++i){
		scanf("%s",ch);
		if(ch[0]=='V'){
			int x=read(),value=read();
			access(x);  splay(x);  
			S[x].erase(S[x].find(v[x]));
			S[x].insert(value);  v[x]=value;
			updata(x);
		}
		else if(ch[0]=='E'){int x=read(); reverse(x);}
		else{
			int x=read();
			access(x);  splay(x);
			printf("%d\n",(*S[x].begin()));
		}
	}
	return 0;
}