Tree Modification and Heavy Edge Query

Little W has a tree with \(n\) nodes. Each edge in the tree can be either a light edge or a heavy edge. Initially, all edges are light. You are then given \(m\) operations. The operations are of two types:

• Update Operation (Type 1): Given two vertices \(a\) and \(b\), first, for every vertex \(x\) on the unique path from \(a\) to \(b\) (including \(a\) and \(b\)), change all edges incident to \(x\) to light. Then, change all edges along the path from \(a\) to \(b\) to heavy.
• Query Operation (Type 2): Given two vertices \(a\) and \(b\), output the number of heavy edges on the unique path from \(a\) to \(b\).

It is guaranteed that the given graph is a tree.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of nodes and the number of operations respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating there is an edge between nodes \(u\) and \(v\).

The following \(m\) lines each represent an operation in one of the following formats:

• 1 a b — Update operation: update the path from \(a\) to \(b\) as described.
• 2 a b — Query operation: output the number of heavy edges on the path from \(a\) to \(b\).

outputFormat

For each query operation (Type 2), output a single line containing the number of heavy edges on the path from \(a\) to \(b\>.

sample

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

3
1
0