Bob has a rooted tree with $n$ nodes, where node $1$ is the root. Bob has colored each node, and the colors of all nodes are initially distinct.

The weight of a path is defined as the number of distinct colors on the nodes along the path (including the start and end nodes).

Bob will perform $m$ operations: $1\ x$: Paint all nodes on the path from $x$ to the root with a new color that has not been used before. $2\ x\ y$: Query the weight of the path between $x$ and $y$. * $3\ x$: In the subtree rooted at $x$, choose a node such that the weight of the path from this node to the root is maximized. Find this maximum weight.

Bob will perform $m$ operations in total.

Input

The first line contains two integers $n, m$. The next $n-1$ lines each contain two integers $a, b$, representing an edge between $a$ and $b$. The next $m$ lines describe the operations, as defined in the problem statement.

Output

For each operation of type 2 or 3, output one line. If the operation is type 2, output a single integer representing the weight of the path. If the operation is type 3, output a single integer representing the maximum weight.

Examples

Input 1

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

Output 1

3
4
2
2

Constraints

There are 10 test cases. Test case 1: $1 \le n, m \le 1000$ Test case 2, 3: No type 2 operations Test case 4, 5: No type 3 operations Test case 6: The tree is generated such that for $2 \le i \le n$, the parent of $i$ is chosen randomly from $1$ to $i-1$. Test case 7: $1 \le n, m \le 50000$ Test case 8: $1 \le n \le 50000$ Test case 9, 10: No special constraints For all data: $1 \le n \le 10^5, 1 \le m \le 10^5$