题目描述

小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 $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$ 行，每行包含一个整数，依次表示每个采购方案的答案。

4 2
1 2 3 1
1 2
1 3
2 4
4 3
1 4

3
2

提示

第一个方案路线为 $\{4, 2, 1, 3\}$，可以买到第 $1, 2, 3$ 种零食；
第二个方案路线为 $\{1, 2, 4\}$，可以买到第 $1, 2$ 种零食。

对于 20% 的评测用例，$1 ≤ n, q ≤ 5000$；
对于所有评测用例，$1 ≤ n, q ≤ 10^5，1 ≤ c_i ≤ 20，1 ≤ u_i , v_i ≤ n，1 ≤ s_i , t_i ≤ n$。