问题描述

AtCoder市共有 $N$ 个编号从 $1$ 到 $N$ 的城镇，它们通过 $N-1$ 条双向通行的距离为 $1$ 的道路相连。从任意一个城镇都可以通过若干条路径到达其他城镇。

AtCoder市有 $Q$ 个高桥先生，第 $i$ 个高桥先生想要从城镇 $s_i$ 去往城镇 $t_i$。

AtCoder市的某些城镇有炸鱼球摊。所有的高桥先生以每秒 $2$ 的速度行走距离为 $1$ 的路程，但在吃过炸鱼球之后，行走速度会变为每秒 $1$ 的速度。此外，所有的高桥先生都很能吃，不会吃多次炸鱼球。当然，他们也可以不去炸鱼球摊而直接到达城镇 $t_i$。

给定AtCoder市的城镇连接关系，请对于所有的 $Q$ 个高桥先生，求出从城镇 $s_i$ 到城镇 $t_i$ 的最短时间。由于所有的高桥先生都是炸鱼球专业户，所以忽略吃炸鱼球所花费的时间。

输入

输入以以下格式从标准输入给出。

$N$ $Q$ $A_1$ $B_1$ . . . $A_{N-1}$ $B_{N-1}$ $S$ $s_1$ $t_1$ . . . $s_Q$ $t_Q$

• 第 $1$ 行包含两个整数 $N(1≤N≤100000)$ 和 $Q(1≤Q≤100000)$，以一个空格分隔。
• 接下来的 $N-1$ 行，每行包含两个整数 $A_i, B_i(1≤A_i≤N, 1≤B_i≤N, A_i≠B_i)$，表示城镇 $A_i$ 和城镇 $B_i$ 之间有一条道路连接。
• 接下来的一行，包含长度为 $N$ 的只包含 $0$ 和 $1$ 的字符串。当第 $i$ 个字符为 $0$ 时，表示城镇 $i$ 没有炸鱼球摊，为 $1$ 时，表示城镇 $i$ 有炸鱼球摊。
• 接下来的 $Q$ 行中，每行包含两个整数 $s_i, t_i(1≤s_i≤N, 1≤t_i≤N)$，表示第 $i$ 个高桥先生的起始点和目的地。

输出

输出由 $Q$ 行组成。

第 $i$ 行输出第 $i$ 个高桥先生在最优行动下所需的最短时间。

请注意最后输出时要包含一个换行符。

示例1

7 4
1 2
2 3
2 4
4 5
5 6
6 7
0010000
1 5
1 7
6 1
3 3

输出示例1

6
9
8
0

在第一个查询中，按照顺序游览城镇 $1,2,4,5$ 是最优的。在第二个查询中，按照顺序游览城镇 $1,2,3,2,4,5,6,7$ 并在途中的城镇 $3$ 吃炸鱼球是最优的。

示例2

5 2
3 2
2 4
1 4
2 5
00000
1 5
2 3

输出示例2

6
2

示例3

12 10
1 2
2 3
2 4
10 12
1 5
3 11
5 6
9 10
5 7
3 9
8 7
000100100010
1 2
1 4
8 3
6 12
12 8
8 12
6 8
8 6
1 12
5 12

输出示例3

2
4
6
11
14
9
5
4
9
9