Treasure Hunt on the Tree

You are given a tree with \(n\) cities numbered from \(1\) to \(n\) and \(n-1\) undirected roads connecting them such that any two cities are connected by a unique simple path. Each city contains exactly one treasure which is either a key or a treasure chest. Each key and chest has a color denoted by a positive integer. A key of color \(i\) can open a chest of color \(i\), and when opened, you earn one coin and the key is used up.

Note: For any color \(i\), there are at most \(5\) keys of that color throughout the cities (while the number of chests of that color is unlimited).

You are given \(m\) queries. In the \(i\)th query, you are provided with two cities \(s_i\) and \(e_i\). You will travel along the unique shortest path from \(s_i\) to \(e_i\). As you visit each city along this path:

• If the city contains a key, you pick it up.
• If the city contains a chest and you currently have at least one key of the corresponding color, you use up one such key and open the chest to obtain a coin.

Each journey is independent; that is, after each query the treasures are reset to their initial state.

Determine the number of coins you obtain for each query.

inputFormat

The input begins with two integers \(n\) and \(m\) \(\big( 1 \leq n,m \leq 10^5 \text{ (or smaller in test cases)} \big)\), where \(n\) is the number of cities and \(m\) is the number of travel queries.

Then follow \(n\) lines, each containing two integers \(t\) and \(c\). For the \(i\)th city, \(t = 0\) indicates the city has a key, and \(t = 1\) indicates it has a treasure chest. The integer \(c\) \((1 \le c \le 10^9)\) represents its color. It is guaranteed that for any color, the number of keys (i.e. lines with \(t=0\)) is at most 5.

Next, there are \(n-1\) lines, each containing two integers \(u\) and \(v\), representing an undirected road connecting cities \(u\) and \(v\).

Finally, there are \(m\) lines, each containing two integers \(s\) and \(e\) representing a query from city \(s\) to city \(e\).

outputFormat

For each query, output a single integer on a new line, representing the number of coins obtained during that journey.

sample

3 2
0 1
1 1
1 2
1 2
2 3
1 3
3 1

1
0