题目描述

一只兔子名叫小蓝，它异常狡猾，在土中挖了若干洞窟并且设置了很多出入口来应对紧急情况。它一共有 $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
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$。