该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一只兔子名叫小蓝，它异常狡猾，在土中挖了若干洞窟并且设置了很多出入口来应对紧急情况。它一共有 $n$ 个通往地面的出入口，在地面上这 $n$ 个出入口之间由 $n − 1$ 条长度为 $1$ 的双向通路连成一个连通图。第 $i$ 个出入口属于第 $c_i$ 个洞窟，因此小蓝可以在任意一个属于 $c_i$ 的出入口从地面进入洞窟然后从任意一个属于 $c_i$ 的出入口跑出到达地面。

小蓝提出了 $m$ 个逃跑路线，第 $i$ 个路线希望从出入口 $s_i$ 逃往 $t_i$，它希望在逃跑的过程中在地面上跑动的距离尽可能短，请为每条路线计算逃跑时在地面上跑动的最短距离。

输入格式

输入的第一行包含两个正整数 $n, m$，用一个空格分隔。

第二行包含 $n$ 个正整数 $c_1, c_2, · · · , c_n$，相邻整数之间使用一个空格分隔。

接下来 $n − 1$ 行，第 $i$ 行包含两个整数 $u_i , v_i$，用一个空格分隔，表示地面上的一条通路连接 $u_i$ 和 $v_i$ 。

接下来 $m$ 行，第 $i$ 行包含两个整数 $s_i , t_i$，用一个空格分隔。

输出格式

输出 $m$ 行，每行包含一个整数，依次表示每个询问的答案。

样例

6 3
3 1 3 2 1 2 3 
1 2 
1 3
2 4 
2 5 
3 6 
2 6 
3 2 
4 3

0
1
1

数据范围

• 对于 $20\%$ 的评测用例，$1 ≤ n, m, c_i ≤ 100$；
• 对于所有评测用例，$1 ≤ n, m, c_i ≤ 5000$，$1 ≤ u_i , v_i , s_i , t_i ≤ n$。