题目描述

有一棵节点数为 $n$ 的树，给定 $m + n - 1$ 组询问，每组询问有两种操作。

1. A x y，将 $x$ 节点和 $y$ 节点间的边权改为 $0$，每条边会被修改恰好一次。

2. W x，求 $1$ 号点到 $x$ 号点路径上的边权和。

初始所有边权值都为 $1$。

输入格式

In the first line of the standard input there is a single integer $n$ ($1\le n\le 250\ 000$),denoting the number of villages in Byteotia. The following $n-1$ lines contain descriptions of the roads, in the form of two integers $a$,$b$ ($1\le a\lt b \le n$) separated by a single space, denoting the numbers of villages connected with a road. Inthe next line there is a single integer $m$($1\le m\le 250\ 000$),denoting the number of trips Byteasar has made.

The following $n+m-1$ lines contain descriptions of the events, in chronological order:

A description of the form "A $a$ $b$"(for $a\lt b$) denotes a country road between villages $a$ and $b$ beingtransformed into a motorway in that particular moment.

A description of the from "W $a$" denotes Byteasar's trip from Bitburg to village $a$.

输出格式

Your programme should write out exactly $m$ integers to the standard output, one a line, denoting the numberof country roads Byteasar has travelled during his successive trips.

样例

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