You are given a tree with N nodes. A tree is a connected graph that doesn't contain any cycles.

Initially, all nodes are colored black. At any time, a node can have either color black or white.

You need to handle Q queries on this tree. Queries are of 2 types. Type 1 query is an update operation where you are given an integer X. This means you need to switch the color of node X, that is, if the node X is colored white, color it black and vice versa.

In a type 2 query, you are given 2 integers X and Y, you need to find the number of white nodes on the path from X to Y.

Input:

First line of input contains a single integer N denoting the number of nodes in the tree. Each of the next $N-1$ lines contains 2 integers A and B, meaning that node A and B are connected by an edge.

Next line contains an integer Q, denoting the number of queries. Each of the next Q lines contains 2 or 3 integers. The first integer is T. If T is equal to 1, then it is a type 1 query and next integer is X. If T is equal to 2, then it is a type 2 query and the next 2 integers are X and Y. X and Y are defined as in the problem statement.

Output:

For each query of type 2, print the answer in a new line.

Constraints:

$1 \le N, Q \le 2 \cdot 10^5$

$T = 1$ or 2

$1 \le X, Y, A, B \le N$