Description

Given an unrooted tree with $n$ nodes, there are $m$ operations of two types:

1. Color all nodes on the path from node $a$ to node $b$ (including $a$ and $b$) with color $c$.
2. Query the number of color segments on the path from node $a$ to node $b$.

A color segment is defined as a maximal consecutive run of the same color. For example, 112221 consists of three segments: 11, 222, 1.

Input Format

The first line contains two integers separated by a space, representing the number of nodes $n$ and the number of operations $m$.

The second line contains $n$ integers separated by spaces. The $i$-th integer $w_i$ represents the initial color of node $i$.

Lines $3$ through $(n + 1)$ each contain two integers $u, v$ separated by a space, indicating that there is an edge between nodes $u$ and $v$ in the tree.

Lines $(n + 2)$ through $(n + m + 1)$ each describe an operation in the following format:

Each line starts with a character $op$, indicating the type of operation.

• If $op$ is C, it denotes a coloring operation. After a space, there are three integers $a, b, c$ separated by spaces, meaning that all nodes on the path from $a$ to $b$ are colored with color $c$.
• If $op$ is Q, it denotes a query operation. After a space, there are two integers $a, b$ separated by a space, indicating a query for the number of color segments on the path from $a$ to $b$.

Output Format

For each query operation, output a single line containing one integer representing the answer.

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

3
1
2

Hint

Constraints

For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $1 \leq w_i, c \leq 10^9$, $1 \leq a, b, u, v \leq n$, $op$ is guaranteed to be C or Q, and the given graph is a tree.

In addition to the original testdata, there exists a non-scoring set of hack testdata.

Translated by ChatGPT 5