小蓝准备去星际旅行，出发前想在本星系采购一些零食，星系内有 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, 3}，可以买到第 1, 2, 3 种零食；
第二个方案路线为 {1, 2, 4}，可以买到第 1, 2 种零食。

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