Problem Description

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.

Input Format

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 Format

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

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

1
1
1

见附件中的 keys/keys2.in

见附件中的 keys/keys2.ans

见附件中的 keys/keys3.in

见附件中的 keys/keys3.ans

Hint

[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.

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