题目描述

Alice 在成功通过驾照考试后，正准备进行人生中第一次独自驾车旅行。仙境中有 N 个城市，编号为 1 到 N，并且有 N-1 条双向公路，使任意两座城市之间都连通。Alice 为这次旅行挑选了 Q 条可能的路线，其中第 i 条路线是从城市 a_i 到城市 b_i 的最短路径。

仙境中的城市气候是固定的：其中一部分城市是晴天城市，另一部分是阴凉城市。Alice 的汽车有一个“智能”空调，它会对此进行“补偿”——在晴天城市中，空调会让车内温度降低 1°C；在阴凉城市中，空调会让车内温度升高 1°C。问题在于，这辆车隔热效果非常好，因此车内温度的变化完全由这台“智能”空调造成。Alice 担心这会让她在旅行途中感觉太热。

因此，对于这 Q 条路线中的每一条，她都想知道：在她会经过的城市中，有多少个城市会使得车内温度高于出发时的温度。计数时需要把路线的两个端点城市（a_i 和 b_i）也算进去。Alice 还特别说明：车内温度的变化发生在进入每一座城市时，包括出发所在的第一座城市。

输入格式

第一行输入两个整数 N 和 Q。
第二行输入一个长度为 N 的字符串，描述仙境中每座城市的气候：第 i 个字符为：

• "+"：表示进入城市 i 时，“智能”空调会使车内温度升高（阴凉城市）；
• "-"：表示进入城市 i 时，“智能”空调会使车内温度降低（晴天城市）。

接下来 N-1 行，每行输入两个整数 u_i 和 v_i，表示城市 u_i 与城市 v_i 之间有一条直接公路。
最后 Q 行，每行输入两个整数 a_i 和 b_i，分别表示 Alice 第 i 条备选路线的起点与终点城市。

输出格式

输出 Q 行。
第 i 行输出一个整数，表示在第 i 条路线中，车内温度高于出发温度的城市个数。

约束

• 1 ≤ N, Q ≤ 5 × 10^5

注：原题脚注写道：由于仙境中不存在绝对零度，因此那里的温度可以任意低。

子任务

子任务的分数只有在该子任务下的所有测试点全部通过时才能获得。

样例 1

输入

8 5
-+++-++-
1 5
5 6
3 6
4 5
4 7
4 8
1 2
3 8
2 2
1 7
2 7
6 4

输出

5
1
0
2
2

说明

每条路线经过的城市，以及车内的相对温度如下：

3 8：3 -> 6 -> 5 -> 4 -> 8
相对温度：+1, +2, +1, +2, +1

2 2：2
相对温度：+1

1 7：1 -> 5 -> 4 -> 7
相对温度：-1, -2, -1, 0

2 7：2 -> 1 -> 5 -> 4 -> 7
相对温度：+1, 0, -1, 0, +1

6 4：6 -> 5 -> 4
相对温度：+1, 0, +1

样例 2

输入

6 4
+-++--
1 2
2 3
3 4
4 5
5 6
1 6
6 1
5 1
2 4

输出

4
0
2
1

说明

对于这个样例，对所有 i 都有 u_i = i 且 v_i = i + 1。
每条路线经过的城市，以及车内的相对温度如下：

1 6：1 -> 2 -> 3 -> 4 -> 5 -> 6
相对温度：+1, 0, +1, +2, +1, 0

6 1：6 -> 5 -> 4 -> 3 -> 2 -> 1
相对温度：-1, -2, -1, 0, -1, 0

5 1：5 -> 4 -> 3 -> 2 -> 1
相对温度：-1, 0, +1, 0, +1

2 4：2 -> 3 -> 4
相对温度：-1, 0, +1