#include <algorithm>

 #include <iostream>

 #include <cstdio>

 using namespace std;

 const int N(1e6+);

 int n,q,u,v;

 int mark[N],dad[N];

 int Get_grandfa(int x,int y)

 {

     for(;!mark[x];)

         x=dad[x];

     return x;

 }

 int main()

 {

     freopen("heoi2016_tree.in","r",stdin);

     freopen("heoi2016_tree.out","w",stdout);

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

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

         scanf("%d%d",&u,&v),dad[v]=u;

     mark[]=;

     for(char op;q--;)

     {

         cin>>op>>v;

         if(op=='C') mark[v]=;

         else printf("%d\n",Get_grandfa(v,));

     }

     return ;

 }