The input includes several test cases.
The first line of the input contains one integer $T(1 \leq T \leq 20)$, denoting the number of test cases.
For each test case, the first line contains two space-separated integers $N(1 \leq N \leq 50000)$, $k(1 \leq k \leq 100000)$, and a digit string $S(|S|=N)$. Denoting the number of vertex and the special number, and the decimal digits on every vertex. The decimal digit on the i-th vertex is the i-th character of $S$.
For each of the next $N-1$ lines, there are two space-separated integer $u,v$, denoting a road connecting two vertex in the dragon forest.