Problem Description

There are $n$ cities numbered $1, 2, \ldots, n$. These cities are connected by $n - 1$ undirected roads, each connecting two cities, ensuring that any two cities are connected. Thus, these $n$ cities form a tree.

Each city contains a treasure, which can be either a key or a chest. In a city, there is either a key or a chest. Keys and chests have different colors, and a key of color $i$ can only open a chest of color $i$. Upon opening a chest, one earns a coin, and the key is then damaged.

Due to a special reason, there are at most $\bm{5}$ keys of the same color (the number of chests of the same color is unlimited).

Now, Xiao R plans $m$ trips, with the $i$-th trip starting at $s_i$ and ending at $e_i$. Xiao R travels along the shortest path from $s_i$ to $e_i$. When he reaches a city with a key, he can put the key in his backpack. When he reaches a city with a chest, if he has a key of the corresponding color, he will open the chest and earn a coin; if he does not have the corresponding key, he does nothing (chests cannot be taken away). The question is how many coins can be earned during each trip.

Note: Trips are independent, meaning that after each trip, all keys and chests return to their initial states.

Input Format

The first line contains two positive integers $n, m$, representing the number of cities and the number of trips, respectively.

The next $n$ lines each contain two positive integers $t_i, c_i$. $t_i=1$ indicates that the $i$-th city has a key, and $t_i=2$ indicates that it has a chest. $c_i$ represents the color of the key or chest in the $i$-th city. It is guaranteed that there are no more than $5$ keys of the same color.

The next $n - 1$ lines each contain two positive integers $u_i, v_i$, indicating an undirected road connecting $u_i$ and $v_i$.

The next $m$ lines each contain two positive integers $s_i, e_i$, representing the start and end points of a trip.

Output Format

Output $m$ lines, each containing an integer representing the number of coins earned during the $i$-th trip.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
1
1

Input Sample #2

See the attached file keys/keys2.in

Output Sample #2

See the attached file keys/keys2.ans

Input Sample #3

See the attached file keys/keys3.in

Output Sample #3

See the attached file keys/keys3.ans

Notes/Hints

[Sample #4]

See the attached files keys/keys4.in and keys/keys4.ans.

This sample satisfies $n, m \le {10}^5$ and special property A.

[Data Range]

For $100\%$ of the data, $1 \le n \le 5 \times {10}^5$, $1 \le m \le {10}^6$, $1 \le t_i \le 2$, $1 \le c_i, u_i, v_i, s_i, e_i \le n$, and there are no more than $5$ keys of the same color.

Special Property A: For each color that appears, there is exactly one key and one chest of that color.

[Hint]

The input and output data are large, so please use a fast input and output method.

见题面 Input 部分

见题面 Output 部分