题目描述

卡卡的房子外面有一棵苹果树。每年秋天，树上都会结出许多苹果。卡卡非常喜欢苹果，因此他一直精心照料着这棵大苹果树。

这棵树有$N$个分叉，由树枝连接。卡卡将这些分叉编号为$1$到$N$，其中根节点始终编号为$1$。苹果会生长在分叉上，且每个分叉上最多只会有一个苹果。卡卡想要知道某个子树中有多少个苹果，以便研究这棵苹果树的产量。

麻烦的是，有时一个新的苹果可能会在空的分叉上长出，而卡卡也可能会从树上摘下一个苹果作为甜点。你能帮助卡卡吗？

输入格式

• 第一行包含一个整数$N$（$N \leq 100,000$），表示树中分叉的数量。
• 接下来的$N-1$行每行包含两个整数$u$和$v$，表示分叉$u$和分叉$v$由一根树枝连接。
• 下一行包含一个整数$M$（$M \leq 100,000$）。
• 接下来的$M$行每行包含一条消息，可能是以下两种之一：
  • C x：表示分叉$x$上的苹果状态发生了变化。即，如果该分叉上有苹果，则卡卡会摘掉它；否则，一个新的苹果会在该空分叉上长出。
  • Q x：表示询问分叉$x$的子树中的苹果数量（包括分叉$x$上的苹果，如果存在的话）。

注意：初始时树上所有的分叉都结有苹果。

输出格式

对于每个询问，输出对应的答案，每个答案占一行。

输入样例1

3
1 2
1 3
3
Q 1
C 2
Q 1

输出样例1

3
2

题目来源

POJ Monthly--2007.08.05, Huang, Jinsong