一只兔子名叫小藍(lán)，它異常狡猾，在土中挖了若干洞窟并且設(shè)置了很多出入口來應(yīng)對緊急情況。它一共有 n 個通往地面的出入口，在地面上這 n 個出入口之間由 n ? 1 條長度為 1 的雙向通路連成一個連通圖。第 i 個出入口屬于第 ci個洞窟，因此小藍(lán)可以在任意一個屬于 ci 的出入口從地面進(jìn)入洞窟然后從任意一個屬于 ci 的出入口跑出到達(dá)地面。

小藍(lán)提出了 m 個逃跑路線，第 i 個路線希望從出入口 si 逃往 ti ，它希望在逃跑的過程中在地面上跑動的距離盡可能短，請為每條路線計(jì)算逃跑時在地面上跑動的最短距離。

輸入的第一行包含兩個正整數(shù) n, m ，用一個空格分隔。

第二行包含 n 個正整數(shù) c1, c2, · · · , cn ，相鄰整數(shù)之間使用一個空格分隔。

接下來 n ? 1 行，第 i 行包含兩個整數(shù) ui, vi ，用一個空格分隔，表示地面上的一條通路連接 ui 和 vi 。

接下來 m 行，第 i 行包含兩個整數(shù) si, ti ，用一個空格分隔。

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, ci ≤ 100 ；

對于所有評測用例，1 ≤ n, m, c_i ≤ 5000 ，1 ≤ u_i, v_i, s_i, t_i ≤ n 。