Distinct Fruit Types in a Tree Path

You are given a tree with n nodes. Each node is assigned a fruit type represented by an integer. The tree is provided as a set of n-1 edges, and you are asked to answer q queries. In each query, you are provided two nodes X and Y, and your task is to determine the total number of distinct fruit types present on the unique simple path from node X to node Y.

Input Format:

• The first line contains two integers, n (number of nodes) and q (number of queries).
• The second line contains n integers, where the i-th integer represents the fruit type of the i-th node.
• The next n-1 lines each contain two integers u and v representing an undirected edge between nodes u and v.
• The next q lines each contain two integers X and Y representing a query asking for the number of distinct fruit types on the path from node X to node Y.

Output Format:

• For each query, output a single integer on a new line representing the number of distinct fruit types.

The problem requires an efficient method to retrieve the unique path between two nodes in a tree and then determine the count of distinct fruit types along that path. A common approach is to perform a breadth-first search (BFS) to determine the path between the queried nodes.

inputFormat

The input is given via standard input (stdin) and has the following format:

n q
f1 f2 ... fn
u1 v1
u2 v2
...
un-1 vn-1
X1 Y1
X2 Y2
...
Xq Yq

Here, n is the number of nodes and q is the number of queries. The second line provides the fruit type (an integer) for each of the n nodes. The following n-1 lines specify the edges of the tree. Finally, the next q lines each contain a query with two integers, representing the start node X and the end node Y.

outputFormat

For each query, output a single integer on a new line which is the number of distinct fruit types encountered on the path from node X to node Y.

## sample

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

3
3

</p>