题目描述

给定一棵具有 $N$ 个节点的树。树的节点从 $1$ 到 $N$ 编号。每个节点都有一个整数权重。

我们将要求你执行以下操作：

• $u$ $v$：询问从节点 $u$ 到节点 $v$ 的路径上有多少个不同的整数代表节点的权重。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数。第 $i$个整数表示第 $i$ 个节点的权重。

接下来的 $N-1$ 行，每行包含两个整数 $u,v$，描述一条边（$u, v$）。

接下来的 $M$ 行，每行包含两个整数 $u,v$，表示一个询问操作，询问从 $u$ 到 $v$ 的路径上有多少个不同的整数代表节点的权重。

输出格式

对于每个操作，输出其结果。

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

样例分析

节点 $2$ 到节点 $5$ 路径上有 $4$ 种不同权重的节点，节点 $7$ 到节点 $8$ 路径上有 $4$ 种不同权重的节点。

数据范围与提示

对于 $100\%$ 的数据：$1 \le N \le 4 \times 10^4$，$1 \le M \le 10^5$，节点权重是不超过 $2\times 10^9$ 的非负整数。