Tree Path Painting and Query

You are given an unrooted tree with \(n\) nodes and \(m\) operations. Initially, every node is painted with color 1.

There are two types of operations:

1. Update Operation: Given three integers \(a\), \(b\), and \(c\). Paint all the nodes on the simple (unique) path between node \(a\) and node \(b\) (both inclusive) with color \(c\).
2. Query Operation: Given two integers \(a\) and \(b\). Report the number of contiguous color segments along the path from node \(a\) to node \(b\).

A contiguous color segment is defined as a maximal sequence of consecutive nodes (along the path) having the same color. For example, the color sequence 1 1 2 2 2 1 has three segments: 1 1, 2 2 2, and 1.

Note: The tree is given with \(n-1\) edges ensuring connectivity and no cycles.

inputFormat

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

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

The following \(m\) lines each describe an operation. An operation is in one of the following formats:

• 1 a b c — Update operation: paint the path from node \(a\) to node \(b\) with color \(c\).
• 2 a b — Query operation: output the number of contiguous color segments on the path from node \(a\) to node \(b\).

It is guaranteed that the given edges form a tree and that every operation is valid. Initially, every node's color is 1.

outputFormat

For each Query operation (i.e. operations of type 2), output a single integer on a new line which is the number of contiguous color segments on the path between the specified nodes.

sample

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

1
2
3