题目描述

原题来自：SDOI 2011 给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作共两类。 1、将节点 $a$ 到节点 $b$ 路径上的所有节点都染上颜色； 2、询问节点 $a$ 到节点 $b$ 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 $112221$ 由三段组成：$11$ 、 $222$、$1$。 请你写一个程序依次完成操作。

输入

第一行包括两个整数 $n,m$，表示节点数和操作数； 第二行包含 $n$ 个正整数表示 $n$ 个节点的初始颜色； 接下来若干行包含两个整数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间有一条无向边； 接下来若干行每行描述一个操作： 1、$C\;a\;b\;c$ 表示这是一个染色操作，把节点 $a$ 到节点 $b$ 路径上所有点（包括 $a$ 和 $b$）染上颜色； 2、$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

提示

数据范围与提示： 对于 100% 的数据，$N,M≤10^5$ ， 所有颜色 $C$ 为整数且在 [$0,10^9$]之间。

评测数据说明

本题使用经输入域与独立答案完整核验的第三方公开训练数据，并补充自编边界及公开样例，共10个测试点，非原站或官方原始数据。总分100分。公开训练数据来自HEEKDragonOne/ACM固定提交，逐点来源与SHA256保存在教师复核材料。