暂无测试数据。

新年到了，蒜头君要给公司的员工发送新年祝福语～

已知公司有 $n$ 名员工，编号为 $1\sim n$。在公司的体制内，除老板外，其他每名员工有且仅有一个直接上级，每名员工可能有多个直接下级。员工之间的关系可以看成一棵有根树，最初时老板的编号为 $1$ 号。

蒜头君非常有才华，会写出优美的祝福语。员工可以寻求蒜头君帮助定制祝福语模版，然后他会将祝福语发送给他的直接上级和直接下级。当某员工收到祝福语后，需要 $1$ 分钟时间对祝福语进行修改，变为自己专属的祝福语模版，然后会将该祝福语发送给他的直接上级和直接下级。

寻找蒜头君帮忙的员工不需要对祝福语进行修改就可以得到蒜头君的祝福，其他员工得到祝福语后都需要对祝福语进行修改，修改结束后才算作得到了祝福。同时发送祝福语不消耗时间。

人生的精彩在于各种不确定性，蒜头君依次遇到了 $m$ 个突发事件，包括两种类型（具体描述详见输入格式）：

1. 公司老板变更，导致员工之间的上下级关系发生了改变。永久性操作，影响后续的查询操作；
2. 两名同事之间失去联系，不能相互转发祝福语。暂时性查询操作，只对本次查询有效，不影响后面的查询；

现在你需要依次计算出每个突发事件发生后，最少需要多长时间，才能让所有够得到祝福语的员工，得到祝福。

输入格式

第一行输入一个整数 $n$，表示公司内有 $n$ 个人。

接下来 $n-1$ 行，每行两个正整数 $u, v$，表示 $u,v$ 直接互为上下级（需根据树的结构确定上下级）。

接下来一个正整数 $m$，表示突发事件的个数。

接下来 $m$ 行，每行先输入字符 op，表示突发事件的种类：

• 若 op = 'C'，则需要再输入正整数 $x$，则表示现在公司的老板变更为 $x$ 了（不改变员工之间的连接关系）；
• 若 op = 'Q'，则需要再输入两个整数 x y，表示员工 $x$ 寻求蒜头君帮助得到了定制的祝福语模版，并且他的第 $y-1$ 级上级和第 $y$ 级上级之间失去联系（$x$ 的直接上级为他的第 $1$ 级上级），不能相互发送祝福语，如果他没有第 $y$ 级上级，则这条限制无效。

输出格式

输出若干行，依次表示 $m$ 个突发事件中 op = 'Q' 时，由 $x$ 发出祝福语后，所有能过得到祝福所需的最少时间（注意除了 $x$ 外，每个人都需要花费 $1$ 分钟处理祝福语，然后才算得到祝福）。

数据范围

对于 $20\%$ 的数据，$1\leq n, m \leq 3000$；

对于另外 $20\%$ 的数据，保证是一条链；

对于另外 $30\%$ 的数据，老板不会发生变更；

对于 $100\%$ 的数据，$1\leq n, m \leq 2\times 10^5, 1\leq y \leq n$

5
1 3
2 4
3 2
3 5
6
Q 4 1
Q 4 2
Q 4 3
C 2
Q 1 2
Q 1 3

0
1
3
2
3