There are $n$ cities, numbered $1, 2, \dots, n$. These cities are connected by $n-1$ undirected roads, and it is guaranteed that any two cities are connected. That is, these $n$ cities form a tree.
Each city contains one treasure. Treasures are of two types: keys and treasure chests. In each city, there is either a key or a treasure chest. Keys and treasure chests have different colors; a key of color $i$ can only open a treasure chest of color $i$. Opening a treasure chest grants one gold coin, and the key used is destroyed.
Due to some special reason, there are at most 5 keys of any single color (the number of treasure chests of any single color is unlimited).
Now, Little R has planned $m$ trips. The $i$-th trip starts at $s_i$ and ends at $e_i$. Little R travels from $s_i$ to $e_i$ along the shortest path. When he reaches a city with a key, he can put the key into his backpack. When he reaches a city with a treasure chest, if he has a key of the corresponding color, he will open the chest and obtain one gold coin; if he does not have a key of the corresponding color, he does nothing (the treasure chest cannot be taken). Determine how many gold coins can be obtained in each trip.
Note: Trips are independent, meaning that after each trip, all keys and treasure chests are restored to their initial state.
Input
The first line contains two positive integers $n, m$, representing the number of cities and the number of trips.
The next $n$ lines each contain two positive integers $t_i, c_i$. If $t_i = 1$, it means there is a key in the $i$-th city; if $t_i = 2$, it means there is a treasure chest. $c_i$ represents the color of the key or treasure chest in the $i$-th city. It is guaranteed that there are no more than 5 keys of any color.
The next $n-1$ lines each contain two positive integers $u_i, v_i$, representing 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
Output $m$ lines, each containing an integer representing the number of gold coins obtained in the $i$-th trip.
Constraints
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 at most 5 keys of any color.
| Test Case ID | $n \le$ | $m \le$ | Special Property |
|---|---|---|---|
| 1 | 100 | 100 | None |
| 2 ~ 3 | 5000 | 5000 | None |
| 4 ~ 5 | $10^5$ | $10^5$ | None |
| 6 ~ 8 | $5 \times 10^5$ | $10^6$ | A |
| 9 ~ 10 | $5 \times 10^5$ | $10^6$ | None |
Special Property A: For every color that appears, there is exactly one key and one treasure chest corresponding to that color.
Examples
Input 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 1
1 1 1
Examples 2
See keys/keys2.in and keys/keys2.ans in the contestant directory.
Examples 3
See keys/keys3.in and keys/keys3.ans in the contestant directory.
Examples 4
See keys/keys4.in and keys/keys4.ans in the contestant directory.
This set of examples satisfies $n, m \le 10^5$ and Special Property A.
Note
The input and output data are large; please use efficient input and output methods.