8615: Palindromic Tree

We say two strings $s$ and $t$ are different if their lengths are different or there exists at least one position $i$ satisfying si≠tis_i \neq t_isi=ti. A palindromic string is a string that reads the same forward or backward.

The first line of the input contains an integer $T$ (1≤T≤1041 \leq T \leq 10^41≤T≤104), indicating the number of test cases.
For each test case, the first line contains two integers n,qn, qn,q (1≤n,q≤1051 \leq n, q \leq 10^51≤n,q≤105), indicating the number of nodes and the number of queries.
The second line contains a string of length $n$ consisting of $\text{0}$ or $\text{1}$, indicating the characters written on nodes from $1$ to $n$.
Each of the following $n-1$ lines contains two integers u,vu, vu,v (1≤u,v≤n1 \leq u, v \leq n1≤u,v≤n), indicating an edge connecting nodes $u$ and $v$. It is guaranteed that these edges form a tree.
Each of the following $q$ lines contains two integers u,vu, vu,v (1≤u,v≤n1 \leq u, v \leq n1≤u,v≤n), indicating a query with nodes $u$ and $v$.
It is guaranteed that ∑n≤105\sum n \leq 10^5∑n≤105 and ∑q≤105\sum q \leq 10^5∑q≤105 over all test cases.

For each query, output the answer in a single line.