题目描述

一只兔子名叫小蓝，它异常狡猾，在土中挖了若干洞窟并且设置了很多出入口来应对紧急情况。它一共有 $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, \dots , c_n$，相邻整数之间使用一个空格分隔。

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

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

输出格式

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

6 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 \leq n, m, c_i \leq 100$；
• 对于所有评测用例，$1 \leq n, m, c_i \leq 5000$，$1 \leq u_i, v_i, s_i, t_i \leq n$。