Description

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

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

2、询问节点 a 到节点 b 路径上的颜色段数量（连续相同颜色被认为是同一段），如"12221"由 3 段组成："11"、"222"和"1"。 

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

Input Format

第一行包含 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）路径上的颜色段数量。

Output Format

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

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

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

Source

套题 my01