G. 迟到的色彩刚刚好
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Yvonne 想要画一幅作品，她在为这幅画寻找灵感。

四号谷地有 $$$n$$$ 个颇有特色的地点，且两点之间形成了 $$$n-1$$$ 条路径，经过每条路径都需要消耗 $$$1$$$ 分钟，且恰好形成一棵树，其中有部分地点能够为 Yvnone 提供灵感，我们称之为有价值的地点。

Yvonne 提出了 $$$q$$$ 个方案，你需要回答从 $$$x$$$ 号点到 $$$y$$$ 号点且至少经过一个有价值的地点最少需要多少分钟？

Input

第一行输入一个正整数 $$$T(1\le T\le 10^4)$$$，表示测试组数。

接下来 $$$T$$$ 组测试中：

  • 第一行输入两个正整数 $$$n,q\ (1\le n,q\le 2\times 10^5)$$$，含义见题意。
  • 第二行输入长度为 $$$n$$$ 的 $$$01$$$ 串，表示第 $$$i$$$ 号点是否为有价值的地点，当 $$$s_i$$$ 为 $$$1$$$ 时表示该地点为有价值地点，数据保证至少存在一个有价值的地点。
  • 接下来的 $$$n-1$$$ 行，每行输入一对 $$$u,v\ (1\le u,v\le n,u\neq v)$$$，表示一条连通点 $$$u$$$ 和点 $$$v$$$ 的路径，数据保证给出的边一定是一棵树。
  • 接下来的 $$$q$$$ 行，每行输入一对 $$$x,y\ (1\le x,y\le n)$$$，表示一次询问。

此外，数据保证所有测试点 $$$n$$$ 的总和不超过 $$$2\times 10^5$$$，$$$q$$$ 的总和不超过 $$$2\times 10^5$$$，每个测试点的 $$$01$$$ 串一定存在 $$$1$$$。

Output

对于每组测试，共输出一行 $$$q$$$ 个非负整数，表示每次查询的答案。

Example
Input
3
3 2
001
1 2
2 3
2 1
3 3
5 3
01100
1 2
1 3
3 4
4 5
1 3
3 5
1 1
7 6
1000010
1 2
2 3
3 4
3 5
3 6
4 7
5 7
4 6
1 1
4 7
7 7
1 6
Output
3 0
1 2 2
5 2 0 5 6 3