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:
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 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.
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 
Sample Input 1  Sample Output 1 
5 6

3

Subtask  Score 

1  10 
2  20 
3  20 
4  10 
5  40 