当前没有测试数据。

题目描述

小 B 所在的城市是一个 $n$ 个点组成的树形结构。小 B 家在节点 $1$，她有 $m$ 次行程，每次行程从家里出发，到一个节点去游玩。小 B 的城市一开始的所有路都是没有路灯的，随着经济发展，越来越多的路装上了路灯。小 B 很害怕走没有路灯的路，所以要求你计算每次行程要经过多少条没有路灯的路。

输入格式

第一行是一个正整数 $n$。表示节点个数

接下来 $n-1$ 行，每行两个整数，表示节点之间的道路。

接下来一个整数 $m$，表示小 B 的行程次数

接下来 $n+m-1$ 行，按照时间顺序列出事件：

• 如果该行为 A a b，表示 $a$ 和 $b$ 之间的路装上了路灯
• 如果该行为 W a，表示小 B 想去 $a$ 节点玩

输出格式

$m$ 行整数，表示每次行程的答案。

5
1 2
1 3
1 4
4 5
4
W 5
A 4 5
W 5
A 1 4
W 5
W 2
A 1 3
A 1 2

2
1
0
1

数据范围

对于 $100\%$ 的数据，$n \le 250000, m \le 250000$