Description

Byteotia 最终也被全球化浪潮席卷，邮递员 Byteasar 也不例外。他曾经漫步在宁静的乡间小村中，如今却飞驰在高速公路上。但往昔那些悠闲的漫步，仍让他带着一丝温柔怀念。

过去，$n$ 个 Byteotia 村庄（编号 $1$ 至 $n$）通过双向泥土路相连，其结构满足：

从任意村庄出发到村庄 $1$（称为 Bitburg）存在唯一路径。

该路径仅经过编号小于等于起点村庄的村庄。

每条路直接连接两个不同村庄且不经过其他村庄。

道路不在村庄外交叉（但可能存在隧道或高架桥）。

岁月流转，乡间道路相继被改造成高速公路。Byteasar 清晰地记得每条路消失的时刻。如今，Byteotia 已无乡间小路——它们全被高速公路取代，将村庄连成了 Byteotia 大都市。

Byteasar 回想起他去各村送信的旅程。每次他从 Bitburg 出发，前往某个特定村庄。请你计算：对于每次发生在特定时刻、从 Bitburg 到指定村庄的旅程，他途经了多少条乡间道路。

任务

编写程序实现：

1. 输入：

• 初始道路连接描述

• 按时间顺序的事件序列（Byteasar 的旅程和道路改造事件）

2. 输出：

• 对每次旅程，计算 Byteasar 经过的乡间道路数量

Input Format

第一行：整数 $n$（$1 \le n \le 250,000$），表示村庄数。

接下来 $n-1$ 行：每行两个整数 $a, b$（$1 \le a < b \le n$），表示一条连接村庄 $a$ 和 $b$ 的初始道路。

下一行：整数 $m$（$1 \le m \le 250,000$），表示旅程次数。

接下来 $n+m-1$ 行：按时间顺序描述事件：

• A a b（$a < b$）：村庄 $a$ 和 $b$ 间的道路被改造为高速公路。

• W a：Byteasar 从 Bitburg 出发到村庄 $a$ 的旅程查询。

Output Format

输出 $m$ 行，每行一个整数，表示每次旅程中经过的乡间道路数量。

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

2
1
0
1

Hint

翻译：DeepSeek-R1