### 问题描述 小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 $n$ 颗星球，由 $n - 1$ 条航路连接为连通图，第 $i$ 颗星球卖第 $c_{i}$ 种零食特产。小蓝想出了 $q$ 个采购方案，第 $i$ 个方案的起点为星球 $s_{i}$，终点为星球 $t_{i}$，对于每种采购方案，小蓝将从起点走最短的航路到终点，并且可以购买所有经过的星球上的零食（包括起点终点），请计算每种采购方案最多能买多少种不同的零食。 ### 输入格式 输入的第一行包含两个正整数 $n, q$，用一个空格分隔。 第二行包含 $n$ 个整数 $c_{1},c_{2},\cdots ,c_{n}$，相邻整数之间使用一个空格分隔。 接下来 $n - 1$ 行，第 $i$ 行包含两个整数 $u_{i},v_{i}$，用一个空格分隔，表示一条航路将星球 $u_{i}$ 与 $v_{i}$ 相连。 接下来 $q$ 行，第 $i$ 行包含两个整数 $s_{i},t_{i}$，用一个空格分隔，表示一个采购方案。 ### 输出格式 输出 $q$ 行,每行包含一个整数,依次表示每个采购方案的答案。 ### 样例输入 ```text 4 2 1 2 3 1 1 2 1 3 2 4 4 3 1 4 ``` ### 样例输出 ```text 3 2 ``` ### 样例说明 第一个方案路线为 $\lbrace 4,2,1,3\rbrace$，可以买到第 $1,2,3$ 种零食; 第二个方案路线为 $\lbrace 1,2,4\rbrace$，可以买到第 $1,2$ 种零食。 ### 评测用例规模与约定 对于 ${20}\\%$ 的评测用例，$1 \leq n, q \leq {5000}$； 对于所有评测用例，$1 \leq n, q \leq 10^{5},1 \leq c_{i} \leq 20,1 \leq u_{i},v_{i} \leq n,1 \leq s_{i},t_{i} \leq n$。