#include<bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)

#define maxn 100002

#define inf 100000000

#define isrt(x) (!(ch[f[x]][0]==x||ch[f[x]][1]==x))

#define get(x) (ch[f[x]][1]==x)

#define lson ch[x][0]

#define rson ch[x][1]

using namespace std;

int n,Q;

multiset<int>S[maxn];

int ch[maxn][2],f[maxn],rev[maxn],sta[maxn],minv[maxn],mintot[maxn],minson[maxn],val[maxn];

void mark(int x)

{

    if(!x) return;

    swap(lson,rson),rev[x]^=1;

}

void pushup(int x)

{

    if(!x) return;

    minv[x]=mintot[x]=val[x],minson[x]=inf;

    minv[x]=min(minv[x],min(minv[lson],minv[rson]));

    minson[x]=min(min(minson[lson],minson[rson]),*S[x].begin());

    mintot[x]=min(minv[x], minson[x]);

}

void pushdown(int x)

{

    if(!x||!rev[x]) return;

    mark(lson),mark(rson),rev[x]^=1;

}

void rotate(int x)

{

    int old=f[x],fold=f[old],which=get(x);

    if(!isrt(old)) ch[fold][ch[fold][1]==old]=x;

    ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;

    ch[x][which^1]=old,f[old]=x,f[x]=fold;

    pushup(old),pushup(x);

}

void splay(int x)

{

    int v=0,u=x,fa;

    for(sta[++v]=u;!isrt(u);u=f[u]) sta[++v]=f[u];

    while(v) pushdown(sta[v--]);

    for(u=f[u];(fa=f[x])!=u;rotate(x))

        if(f[fa]!=u)

            rotate(get(x)==get(fa)?fa:x);

}

void Access(int x)

{

    int t=0;

    while(x)

    {

        splay(x);

        if(rson) S[x].insert(mintot[rson]);

        if(t) S[x].erase(S[x].lower_bound(mintot[t]));

        rson=t,t=x,x=f[x];

    }

}

void makert(int x)

{

    Access(x),splay(x),mark(x);

}

void link(int x,int y)

{

    makert(x), f[x]=y, S[y].insert(mintot[x]);

}

int main()

{

    int i,j,root=0;

    //         setIO("input");

    scanf("%d%d",&n,&Q);

    mintot[0]=minv[0]=minson[0]=val[0]=inf;

    for(i=0;i<=n;++i) S[i].insert(inf);

    for(i=1;i<=n;++i)

    {

        int a;

        scanf("%d%d",&a,&val[i]);

        if(a==0) { root=i; makert(i); pushup(i); }

        else link(a,i);

    }

    makert(root);

    while(Q--)

    {

        char opt[3];

        int x,y;

        scanf("%s",opt);

        if(opt[0]=='V')

        {

            scanf("%d%d",&x,&y);

            Access(x), splay(x), val[x]=y, pushup(x);

        }

        if(opt[0]=='E')

        {

            scanf("%d",&root);

            makert(root);

        }

        if(opt[0]=='Q')

        {

            scanf("%d",&x);

            Access(x), splay(x);

            printf("%d\n",min(val[x], *S[x].begin()));

        }

    }

    return 0;

}