You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

树上操作

题目背景

题目描述

给定一棵以$1$号结点为根的$n$个结点的有根树，并且给定以下两个操作：

W a：查询根结点到编号为$a$的结点距离，每条边长度视为1。

A a b：将有一条边相连的编号为$a$的结点和编号为$b$的结点合并，即如果$a$是$b$的父亲，把$a$和$b$之间的边删除，将$b$放到原来$a$的位置，然后该结点同时继承原来的两个结点的所有编号（相当于查询$a$和$b$都是查询该结点）。

现保证$A$操作恰好执行$n-1$次，并且每次执行时边都不一样，即最后这棵树会被合并成一个孤立点。要求输出所有$W$操作的答案。

输入格式

第一行一个正整数$n$。

接下来$n-1$行每行两个正整数$a,b$表示一条树边。

接下来一个正整数$m$表示查询操作的次数。

接下来$n-1+m$行每行描述一个操作，包括$n-1$次合并操作和$m$次查询操作，每次操作格式为“$W$ $a$”或“$A$ $a$ $b$”。

输出格式

$m$行，对每次查询操作，输出答案。

样例 #1

样例输入 #1

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

样例输出 #1

2
1
1
0

提示

样例解释1：

原树中，1有两个儿子2和3，2有一个儿子4，3有一个儿子5，故第一次查询时1到5的距离为2。合并1和3之后，1到5的距离就变成了1，故第二次查询为1。合并2和4不影响1到2的距离，第三次查询为1。合并1和2之后查询1到4的距离，因为1和2已合并，2和4已合并，所以1到4的距离为0。

数据范围

对$30\%$的数据，$n≤30,m≤50$。

对$100\%$的数据，$n,m≤250000$，读入树边时$1≤a<b≤n$，查询操作时$1≤a≤n$，合并操作时$1≤a<b≤n$，并且保证合并操作的边都是原来的树边。