LLC “Logistics Routes” and LLC “Route Logistics” — are two competing companies. They operate in a country with N cities (all cities are numbered from 1 to N), and some pairs of cities are connected by railway tracks; moreover, any city can be reached from any other city by a unique sequence of these tracks.

Each city can enter into and terminate contracts with the companies. If one of the companies serves some set of cities, then its trains travel only between these cities and nowhere else. Let us call all cities through which the trains of a company pass its logistics network. For example, if a company serves two cities, then all cities on the path between them are included in the logistics network. It is quite obvious that if some city enters into or terminates a contract, then the logistics network changes immediately.

Over the course of Q years, many changes occurred, because that was exactly when LLC “Logistics Routes” and LLC “Route Logistics” were founded, and exactly when they began attracting clients. In one year, one of five important events for these companies could occur:

Next year, a new company, LLC “Logistics Routes and Route Logistics”, wants to enter the market. They hired you as an analyst and want to reconstruct the history of the two competitors. You easily found all information about the contracts, but you will have to calculate the distances yourself.

The first line contains an integer N — the number of cities in the country (2 ≤ N ≤ 10⁵).

The next N−1 lines contain two integers u_i and v_i — the numbers of the cities connected by the i-th railway track (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i). It is guaranteed that any pair of cities is connected by at most one railway track.

The next line contains an integer Q — the number of years (3 ≤ Q ≤ 10⁵). In year zero, the companies had no contracts.

The next Q lines describe events in one of 5 formats:

For each event, the inequality 1 ≤ v ≤ N holds.

For each year when the contracts did not change, output the distance between the logistics networks of LLC “Logistics Routes” and LLC “Route Logistics”.