Migrated from Lutece 2751 喜多川的颜色

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一棵树有$N$个节点，这棵树的节点编号从 $1$ 到 $N$。每个节点都有一个颜色。
要求你得到以下操作的答案：
$U$ $V$ : 询问从 $U$ 到 $V$ 的路径上有多少个不同的颜色。

Input

第一行有两个整数 $N$ 和 $M$。
第二行有 $N$ 个整数。第 $i$ 个整数表示第 $i$ 个节点的颜色。
接下来的 $N - 1$ 行中，每行包含两个整数 $U$ $V$，表示树中一条边 $(U, V)$.
接下来的 $M$ 行为询问操作，每行包含两个整数 $U$ $V$，表示询问操作的两个整数。

Output

$M$ 行，第 $i$ 行表示第 $i$ 次的询问操作结果。

Samples

8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
7 8

4
4

Constraints

$1\leq n\leq 4 \times 10 ^ 4, 1 \leq m \leq 10 ^ 5$
颜色为不会超过 $2 \times 10 ^ 9$ 的非负整数

Resources

2022 UESTC ICPC Training for Data Structures