treepainting

Tree Vertex Painting

Bob has a tree with \(n\) vertices numbered \(1\) to \(n\), and the tree is rooted at vertex \(1\). Bob has painted the tree, and initially, every vertex has a unique colour.

The weight of a path on Bob's tree is defined as the number of distinct colours occuring over the vertices of the path.

Bob wants to perform \(m\) actions on the tree, each of which will take on one of the following forms:

• \(1\) \(x\): Retrieve a paint bucket of a new, previously unused colour, and paint all vertices on the path from vertex \(1\) to vertex \(x\) inclusive with that colour.
• \(2\) \(x\) \(y\): Find the weight of the path from vertex \(x\) to vertex \(y\).
• \(3\) \(x\): Find the maximum weight out of all paths starting from vertex \(1\) and ending on a vertex in \(x\)'s subtree.

Determine the consequences of Bob's actions.

Input format

The first line of input consists of two integers, \(n\) and \(m\).
\(n - 1\) lines of input follow. Each line contains 2 integers \(a\) and \(b\), denoting that an edge exists between vertices \(a\) and \(b\).
\(m\) lines of input follow. Each line denotes an action taken by Bob on the tree, and will follow one of the three formats described above.

Output format

Output one line for every action taken of type 2 or 3. Each line should contain a single integer, the weight of the queried path for type 2 actions, or the maximum weight of a valid path for type 3 actions.

Limits

\(1 \leq n, m \leq 10^5\).

Subtask #	Score	Constraints
1	10	\(1 \leq n, m \leq 1000\)
2	20	No actions of type 2 will occur.
3	20	No actions of type 3 will occur.
4	10	The parent of every vertex \(i\) is randomly chosen from vertices \([1, i - 1]\).
5	40	No additional constraints

Samples

Sample Input 1	Sample Output 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 4 2 2