The first line of the input contains an integer $T(1\leq T\leq 10)$, denoting the number of test cases.
In each test case, there are two integers $n,m(1\leq n\leq 2000,1\leq m\leq 10^6)$ in the first line, denoting the number of vertices and the upper bound.
In the second line, there are $n$ integers $w_1,w_2,\dots,w_n(1\leq w_i\leq m)$, denoting the value of each vertex.
Each of the following $n-1$ lines contains two integers $u_i,v_i(1\leq u_i,v_i\leq n,u_i\neq v_i)$, denoting an bidirectional edge between vertices $u_i$ and $v_i$.