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

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

接下來 n ? 1 行，第 i 行包含兩個整數(shù) ui, vi ，用一個空格分隔，表示一條航路將星球 ui 與 vi 相連。接下來 q 行，第 i 行包含兩個整數(shù) si, ti ，用一個空格分隔，表示一個采購方案。

4 2
1 2 3 1
1 2
1 3
2 4
4 3
1 4

3
2

【樣例說明】

第一個方案路線為 {4, 2, 1, 3} ，可以買到第 1, 2, 3 種零食；第二個方案路線為 {1, 2, 4} ，可以買到第 1, 2 種零食。

【評測用例規(guī)模與約定】

對于 20% 的評測用例，1 ≤ n, q ≤ 5000 ；對于所有評測用例，1 ≤ n, q ≤ 10⁵，1 ≤ c_i ≤ 20，1 ≤ u_i, v_i ≤ n，1 ≤ s_i, t_i ≤ n。