P8339 [AHOI2022] Keys.

There are $n$ cities, numbered $1, 2, \ldots, n$. These cities are connected by $n - 1$ undirected roads, each road connects two cities, and it is guaranteed that any two cities are connected. That is, the $n$ cities form a tree. Each city has one treasure. Treasures are of two types: keys and chests. In a city, there is either a key or a chest. Keys and chests have different colors: a key of color $i$ can only open a chest of color $i$. After opening a chest, you can obtain one gold coin, and the key will break. **Due to some special reason, for the same type (same color), there are at most $\bm{5}$ keys (the number of chests of the same color is unlimited).** Now Xiao R plans $m$ trips. For the $i$-th trip, the start is $s_i$ and the end is $e_i$. Xiao R walks from $s_i$ to $e_i$ along the shortest path. When he arrives at a city with a key, he may put the key into his backpack. When he arrives at a city with a chest, if he has a key of the corresponding color, he will open the chest and get one gold coin; if he does not have the corresponding key, he does nothing (the chest cannot be taken away). Ask how many gold coins can be obtained in each trip. **Note: Trips are independent. After one trip ends, all keys and chests will be restored to their initial state.**

The first line contains two positive integers $n, m$, representing the number of cities and the number of trips. In the next $n$ lines, each line contains two positive integers $t_i, c_i$. $t_i = 1$ means there is a key in city $i$, and $t_i = 2$ means there is a chest. $c_i$ is the color of the key or chest in city $i$. The testdata guarantees that for each color, there are no more than $5$ keys. In the next $n - 1$ lines, each line contains two positive integers $u_i, v_i$, indicating an undirected road connecting $u_i$ and $v_i$. In the next $m$ lines, each line contains two positive integers $s_i, e_i$, representing one trip's start and end.

Output $m$ lines. Each line contains one integer, representing the number of gold coins obtainable in the $i$-th trip.

**[Sample #4]** See `keys/keys4.in` and `keys/keys4.ans` in the attachment. This sample satisfies $n, m \le {10}^5$ and Special Property A. **[Constraints]** For $100\%$ of the testdata, $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 for each color, there are at most $5$ keys. | Test Point ID | $n \le$ | $m \le$ | Special Property | |:-:|:-:|:-:|:-:| | $1$ | $100$ | $100$ | None | | $2 \sim 3$ | $5000$ | $5000$ | None | | $4 \sim 5$ | ${10}^5$ | ${10}^5$ | None | | $6 \sim 8$ | $5 \times {10}^5$ | ${10}^6$ | A | | $9 \sim 10$ | $5 \times {10}^5$ | ${10}^6$ | None | 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 faster I/O method. Translated by ChatGPT 5