Problem Description

In the city of AtCoder, there are $N$ towns numbered from $1$ to $N$, connected by $N-1$ bidirectional roads of distance $1$. Any town can be reached from any other town by traversing some roads.

There are $Q$ people named Takahashi in the city of AtCoder, and the $i$-th Takahashi wants to travel from town $s_i$ to town $t_i$.

Some towns in the city of AtCoder have takoyaki shops. All Takahashi's walk at a speed of $1$ distance per $2$ seconds, but after eating takoyaki in a town with a takoyaki shop, their walking speed becomes $1$ distance per second. Also, they are all light eaters and will not eat takoyaki more than once. Of course, it is possible to pass through a town with a takoyaki shop without eating takoyaki. It is also acceptable to arrive at town $t_i$ without eating takoyaki.

Given the connectivity of the towns in the city of AtCoder, for all $Q$ Takahashi's, find the minimum time required to travel from town $s_i$ to town $t_i$ when acting optimally. The time to eat takoyaki is negligible, as they are all professionals.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains integers $N(1 ≦ N ≦ 100000)$ and $Q(1 ≦ Q ≦ 100000)$ separated by a space.
• The following $N-1$ lines contain integers $A_i, B_i(1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i ≠ B_i)$ separated by a space, representing the road connecting town $A_i$ and town $B_i$.
• The next line contains a string of length $N$ consisting only of $0$ and $1$. The $i$-th character being $0$ means there is no takoyaki shop in town $i$, and $1$ means there is a takoyaki shop in town $i$.
• The following $Q$ lines contain integers $s_i, t_i(1 ≦ s_i ≦ N, 1 ≦ t_i ≦ N)$, representing the starting and destination towns for the $i$-th Takahashi.

Output Format

The output consists of $Q$ lines.

The $i$-th line should contain the minimum time required for the $i$-th Takahashi to travel when acting optimally.

Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

6
9
8
0

Sample Input #2

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

Sample Output #2

6
2

Sample Input #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

Sample Output #3

2
4
6
11
14
9
5
4
9
9

Notes/Hints

Sample Explanation 1

In the first query, the best case is to visit towns $1, 2, 4, 5$ in order. In the second query, the best case is to visit towns $1, 2, 3, 2, 4, 5, 6, 7$ in order, stopping at the takoyaki shop in town $3$.

见题面 Input 部分

见题面 Output 部分