1 const int maxn = 5e4 + 5;
  2 //静态链表前向星保存图
  3 struct Edge{
  4     int to, next;
  5     int val;
  6 };
  7 int head[maxn], tot;
  8 Edge edges[maxn];
  9 //dfs 时间戳 - st 表示开始时间， ed 表示结束时间， cnt 总的节点个数
 10 int st[maxn], ed[maxn], cnt;
 11 int tree[maxn * 4], ass[maxn * 4], vis[maxn];//tree 线段树节点值， ass 区间更新延迟标记， vis 查找根节点用
 12 int n, m;
 13 
 14 void init(){
 15     memset(head, -1, sizeof(head));
 16     memset(tree, -1, sizeof(tree));
 17     memset(ass, -1, sizeof(ass));
 18     memset(vis, 0, sizeof(vis));
 19     tot = 0;
 20     cnt = 0;
 21 }
 22 void addEdge(int u, int v, int w){
 23     edges[tot].to = v;
 24     edges[tot].val = w;
 25     edges[tot].next = head[u];
 26     head[u] = tot++;
 27 }
 28 //深度优先搜索为每个节点设置时间戳
 29 //画个图很容易看到对应区间关系，父节点区间总是包含子节点的区间
 30 //在线段树的节点中，叶子节点对应的标号是每个节点的起始时间st[u]
 31 void dfs(int u){
 32     cnt++;
 33     //起始时间
 34     st[u] = cnt;
 35     for(int i = head[u]; i != -1; i = edges[i].next){
 36         //对子节点深搜
 37         dfs(edges[i].to);
 38     }
 39     //结束时间
 40     ed[u] = cnt;
 41 }
 42 void build(int l, int r, int k){
 43     if(l == r) {
 44         ass[k] = tree[k] = -1;
 45         return;
 46     }
 47     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1;
 48     build(l, mid, lc);
 49     build(mid + 1, r,rc);
 50 }
 51 //延迟标记ass，初始为-1，每次update或者query时要pushdown到子节点
 52 void update(int ul, int ur, int x, int l, int r, int k){
 53     if(ul == l && ur == r){
 54         ass[k] = x;
 55         return;
 56     }
 57     if(ul > r || ur < l) return;
 58     if(l == r){
 59         tree[k] = x;
 60         ass[k] = -1;
 61         return;
 62     }
 63     
 64     int lc = k << 1, rc = k << 1 | 1;
 65     if(ass[k] != -1){
 66         tree[k] = ass[k];
 67         ass[lc] = ass[k];
 68         ass[rc] = ass[k];
 69         ass[k] = -1;
 70     }
 71     
 72     int mid = (l + r) >> 1;
 73     update(ul, ur, x, l, mid, lc);
 74     update(ul, ur, x, mid + 1, r, rc);
 75 }
 76 
 77 int query(int qu, int l, int r, int k){
 78     if(l == qu && r == qu){
 79         if(ass[k] != -1){
 80             tree[k] = ass[k];
 81             return ass[k];
 82         }
 83         return tree[k];
 84     }
 85     int lc = k << 1, rc = k << 1 | 1;
 86     if(ass[k] != -1){
 87         tree[k] = ass[k];
 88         ass[lc] = ass[k];
 89         ass[rc] = ass[k];
 90         ass[k] = -1;
 91     }
 92     
 93     
 94     int mid = (l + r) >> 1;
 95     if(qu <= mid) return query(qu, l, mid, lc);
 96     else return query(qu, mid + 1, r, rc);
 97 }
 98 
 99 int main(){
100     int T;
101     scanf("%d", &T);
102     for(int t = 1; t <= T; t++){
103         printf("Case #%d:\n", t);
104         init();
105         scanf("%d", &n);
106         for(int i = 2; i <= n; i++){
107             int u, v;
108             scanf("%d %d", &u, &v);
109             addEdge(v, u, 1);
110             vis[u]++;
111         }
112         for(int i = 1; i <= n; i++){
113             //从原树根深搜
114             if(vis[i] == 0){
115                 dfs(i);
116                 break;
117             }
118         }
119         build(1, cnt, 1);
120         scanf("%d", &m);
121         while(m--){
122             char ch;
123             scanf(" %c", &ch);
124             if(ch == ‘C‘){
125                 int x;
126                 scanf("%d", &x);
127                 //st[x]为原树x节点对应线段树中的节点编号
128                 printf("%d\n", query(st[x], 1, cnt, 1));
129             }
130             else{
131                 int x, y;
132                 scanf("%d %d", &x, &y);
133                 //更新时[st[], ed[]]包含了原树上x节点以及其所有子节点
134                 update(st[x], ed[x], y, 1, cnt, 1);
135             }
136         }
137     }
138 }