#2243. [SDOI2011]染色

题目描述

给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），

如"112221"由3段组成："11"、"222"和"1"。

请你写一个程序依次完成这m个操作。

输入格式

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面 行每行描述一个操作：

"C a b c"表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

"Q a b"表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

输出格式

对于每个询问操作，输出一行答案。

样例

样例输入

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

数据范围与提示

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。