Everything changed. At that terrible moment. We knew that home was a tree with $N$ nodes, and carrots were food.

The Land of the Carrot Trees was once a peaceful land, with $N$ cities connected with $N-1$ roads. This all changed one day, when Mimi the carrot-loving cat invaded, and forced the Carrot King into exile!

The Carrot King is constantly on the run. Every day, for the next $Q$ days, one of two types of events happens:

1. His spies tell him that city $u_j$ has either become a safe haven where he can hide, or if it was safe, that it has been completely overrun. Initially, no city is safe.
2. He asks how safe it is to travel from city $u_j$ to city $v_j$. This value is equal to the number of distinct safe cities $c_j$ such that $c_j$ is either on the path from $u_j$ to $v_j$, or there exists a city $d_j$ such that $d_j$ is on the path from $u_j$ to $v_j$, and there exists an edge between $c_j$ and $d_j$.

As the royal adviser, it is up to you to implement a program that answers the king's queries. Can you save the king?

Constraints

$1\le N,Q\le 2\times {10}^5$

Subtask 1 [10%]

$1\le N,Q\le 2\times {10}^3$

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains $2$ space-separated integers $N$ and $Q$.

The next $N-1$ lines each contain $2$ space-separated integers $a_i$ and $b_i$, indicating there is an edge from $a_i$ to $b_i$.

The next $Q$ lines first contain an integer $t_j\in \{1,2\}$, indicating the type of the event:

• If $t_j=1$, then a single integer $u_j$ $(1\le u_j\le N)$ follows.
• If $t_j=2$, then $2$ integers $u_j$ and $v_j$ $(1\le u_j,v_j\le N)$ follow.

Output Specification

For each type 2 event, output the answer on a new line.

Sample Input

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

Sample Output

1
1
0