Megalopolis

Byteotia has $n$ villages, numbered from $1$ to $n$. Long ago they were joined by $n - 1$ bidirectional dirt roads, called country roads, so that village $1$ (named Bitburg) could be reached from every other village in exactly one way. On that unique route from a village toward Bitburg, every village along the way had a number less than or equal to the village it started from, and each road joined exactly two distinct villages.

As time passed, the country roads were rebuilt into motorways one after another, until not a single dirt road remained. Byteasar the postman remembers the exact moment each road was rebuilt. He also recalls his deliveries: every trip began at Bitburg (village $1$) and ended at some village, and he now wonders how many country roads he walked along on each trip.

You are given the road network and a chronological list of events. Each event is either a road being turned into a motorway or one of Byteasar's trips. For every trip, report how many country roads lay on the path from village $1$ to the destination village at that moment.

The first line contains an integer $n$ ($1 \le n \le 250000$), the number of villages.

Each of the next $n - 1$ lines contains two integers $a$ and $b$ ($1 \le a < b \le n$), meaning that a country road joins villages $a$ and $b$.

The next line contains an integer $m$ ($1 \le m \le 250000$), the number of trips.

The following $n + m - 1$ lines describe the events in chronological order, one per line:

• A a b (with $a < b$): the country road between villages $a$ and $b$ is turned into a motorway at this moment.
• W a: Byteasar makes a trip from Bitburg (village $1$) to village $a$.

Print exactly $m$ integers, one per line. The $i$-th line is the number of country roads on the path from village $1$ to the destination of Byteasar's $i$-th trip, counted at the moment that trip is made.

The figure below illustrates the tree of the first example.