You are the commander of a small militia fighting in a war-torn country. The country can be represented as $N$ cities numbered $1$ through $N$ connected by $N-1$ bidirectional roads. It is possible to reach any city from any other city by going along the roads. Your force, while elite, is small. In order to not spread them out too thin, you are only concerned with choke points in the country. A road is a choke point if it is the only way to travel between any pair of cities. In graph theory, this is called a bridge or a cut edge.

You have just received intel that the enemy is mobilizing its forces to launch a surprise attack, as well as orders to eliminate them at all costs. Unfortunately, you do not know the location of the enemy, nor the location that they plan to attack. What's worse, your scouts are constantly discovering secret routes throughout the country that the enemy may use.

As the commander, you are holding an emergency strategy meeting. $Q$ events will occur throughout the session, each of which is either type 1 or type 2.

• Type 1: A scout runs in reporting that they have discovered a new direct secret route between cities $A$ and $B$.

• Type 2: You consider the following query: if the enemy is currently located at city $A$, what is the expected number of choke points that they will have to pass through assuming that their target could be any of the $N$ cities (including $A$) with equal probability and that the enemy army never traverses the same road or route twice? Please read the output specification on the details of what to output for this query.

Input Specification

The first line of input will contain an integer $N$.

The next $N-1$ lines will each contain a description of a road in the form u v, denoting a bidirectional road between city $u$ and $v$. $(1\le u,v\le N)$

The next line will contain $Q$.

The next $Q$ lines will each describe an event, where type 1 events will be in the form 1 A B and type 2 events will be in the form 2 A. $(1\le A,B\le N)$

Output Specification

For each event of type 2, output $N$ times the answer to the query on a separate line. That is, if the expected number of choke points is $E$, you should output $E\times N$. It is guaranteed this will be an integer value.

Constraints

For all subtasks:

$2\le N\le {10}^5$

$1\le Q\le {10}^5$

There will be at least one type-2 event, so the output will not be empty.

Subtask 1 [15%]

$N\le 500$

$Q\le 500$

Subtask 2 [20%]

There will be no type-1 events.

Subtask 3 [10%]

There will be no more than $10$ type-1 events.

Subtask 4 [55%]

No additional constraints.

Sample Input

5
1 2
2 3
2 4
4 5
3
2 2
1 5 3
2 2

Sample Output

5
1

Explanation of Output for Sample Input

After the type-1 event, the only road that is still a choke point is the road between cities 1 and 2.