메갈로폴리스

비테오티아(Byteotia)에는 $1$번부터 $n$번까지 번호가 매겨진 마을이 $n$개 있다. 아주 오래전, 이 마을들은 $n - 1$개의 양방향 흙길(시골길)로 연결되어 있었고, 그 덕분에 다른 어떤 마을에서 출발하더라도 $1$번 마을(비트버그, Bitburg)까지 가는 경로가 정확히 하나뿐이었다. 어떤 마을에서 비트버그까지 가는 이 유일한 경로 위의 모든 마을은 출발한 마을보다 번호가 작거나 같았으며, 각 도로는 서로 다른 두 마을만을 직접 잇는다.

세월이 흐르면서 시골길은 하나씩 고속도로로 바뀌었고, 결국 흙길은 하나도 남지 않게 되었다. 우체부 바이테아사르(Byteasar)는 각 도로가 언제 고속도로로 바뀌었는지 정확히 기억한다. 또한 그는 자신의 배달 여정도 기억하는데, 모든 여정은 비트버그($1$번 마을)에서 시작해 어떤 마을에서 끝났다. 그는 각 여정에서 시골길을 몇 개나 걸어서 지났는지 알고 싶어 한다.

도로망과 사건들이 시간 순서대로 주어진다. 각 사건은 어떤 도로가 고속도로로 바뀌는 일이거나, 바이테아사르의 여정 중 하나이다. 각 여정마다, 그 시점에 $1$번 마을에서 목적지 마을까지의 경로 위에 남아 있던 시골길의 개수를 구하여라.

첫째 줄에 마을의 수를 나타내는 정수 $n$ ($1 \le n \le 250000$)이 주어진다.

이어지는 $n - 1$개의 줄에는 각각 두 정수 $a$, $b$ ($1 \le a < b \le n$)가 주어지며, 이는 마을 $a$와 마을 $b$를 잇는 시골길이 있음을 뜻한다.

그다음 줄에는 여정의 수를 나타내는 정수 $m$ ($1 \le m \le 250000$)이 주어진다.

이어지는 $n + m - 1$개의 줄에는 사건들이 시간 순서대로 한 줄에 하나씩 주어진다.

• A a b ($a < b$): 이 시점에 마을 $a$와 마을 $b$ 사이의 시골길이 고속도로로 바뀐다.
• W a: 바이테아사르가 비트버그($1$번 마을)에서 마을 $a$까지 여정을 떠난다.

정확히 $m$개의 정수를 한 줄에 하나씩 출력한다. $i$번째 줄에는 바이테아사르의 $i$번째 여정을 떠난 시점을 기준으로, $1$번 마을에서 그 여정의 목적지까지의 경로 위에 남아 있던 시골길의 개수를 출력한다.

아래 그림은 첫 번째 예제의 트리를 나타낸 것이다.