Province Capture

Deadpool has decided to get back at the Canadian government. He cannot manage it alone, so he will carry out his plan together with the inimitable Copycat.

Deadpool has decided to capture all of Canada. Then he will let it go, just for fun. Canada is divided into several administrative units, which we will simply call provinces. Some provinces are connected by two-way roads. Canada has $n$ provinces and $n-1$ roads in total. There is exactly one simple path between any two provinces, so Canada is a tree.

As the plan unfolds, Deadpool captures some provinces and releases others. After each action, the provinces under his control are those that belong to the minimal connected subgraph containing all captured provinces. Every captured province is under his control, but not every province under his control is captured.

At certain moments, emergency medical trips take place from one province to another. A trip is more dangerous the more provinces under Deadpool's control it passes through.

For each trip, determine how many provinces under Deadpool's control lie on its path. Initially, all provinces are free. If one or both endpoints of a trip are under Deadpool's control, they are counted too.

The first line contains a natural number $n$ ($1 \le n \le 10^5$), the number of provinces. Each of the next $n-1$ lines contains two natural numbers $u$, $v$ ($1 \le u, v \le n, u \neq v$), the provinces connected by a two-way road. The given graph is guaranteed to be a tree.

The next line contains a natural number $m$ ($1 \le m \le 10^5$), the number of events. Each of the next $m$ lines describes an event in chronological order. First comes a natural number $t$ ($1 \le t \le 2$), the type of the query.

If $t = 1$, one natural number $x$ ($1 \le x \le n$) follows, the province on which Deadpool acts. He captures it if it was free before, and releases it if it was captured before.

If $t = 2$, two natural numbers $x$, $y$ ($1 \le x, y \le n$) follow, the provinces between which the trip is made.

For each trip, print how many provinces under Deadpool's control lie on its path.