Description

Bob has a rooted tree with $n$ nodes, where node $1$ is the root. Bob painted each node with a color, and all nodes have pairwise distinct colors.

Define the weight of a path as the number of distinct colors among the nodes on this path (including both endpoints).

Bob may perform the following operations:

• 1 x Recolor all nodes on the path from $x$ to the root with a brand-new color that has never been used before.
• 2 x y Query the weight of the path from $x$ to $y$.
• 3 x Within the subtree rooted at $x$, choose a node so that the weight of its path to the root is maximized; output that maximum weight.

Bob will perform $m$ operations in total.

Input Format

The first line contains two integers $n, m$.

The next $n-1$ lines each contain two integers $a, b$, indicating an edge between $a$ and $b$.

The next $m$ lines describe the operations, in the format given in the statement.

Output Format

For each operation of type 2 or 3, output one line.

For type 2, output one integer: the weight of the path.

For type 3, output one integer: the maximum weight.

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
4
2
2

Hint

There are 10 test points.

Test point 1: $1 \leq n, m \leq 1000$.

Test points 2 and 3: no type 2 operations.

Test points 4 and 5: no type 3 operations.

Test point 6: the tree is generated as follows — for $i$ ($2 \leq i \leq n$), randomly choose a node from $1$ to $i-1$ as the parent of $i$.

Test point 7: $1 \leq n, m \leq 5 \times 10^4$.

Test point 8: $1 \leq n \leq 5 \times 10^4$.

Test points 9 and 10: no special restrictions.

For all testdata: $1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$.

Translated by ChatGPT 5