Galactic Snack Adventure

Little Blue is preparing for an interstellar journey and wants to stock up on local snacks before departing his star system. The system consists of \(n\) planets connected by \(n-1\) routes forming a tree (i.e. a connected acyclic graph). The \(i\)-th planet offers a specialty snack of type \(c_i\). Little Blue has \(q\) purchasing plans. For the \(i\)-th plan, he starts at planet \(s_i\) and ends at planet \(t_i\). In each plan, he travels along the unique shortest path from \(s_i\) to \(t_i\) and is allowed to purchase snacks on every planet he passes (including both \(s_i\) and \(t_i\)). Your task is to determine, for each plan, the maximum number of different snack types Little Blue can possibly buy.

Input Format:

• The first line contains two integers \(n\) and \(q\) separated by a space.
• The second line contains \(n\) integers \(c_1, c_2, ..., c_n\) where \(c_i\) represents the snack type sold at the \(i\)-th planet.
• The next \(n-1\) lines each contain two integers \(u\) and \(v\), denoting a bidirectional route between planets \(u\) and \(v\).
• The following \(q\) lines each contain two integers \(s_i\) and \(t_i\), representing a purchasing plan.

Output Format:

For each query, output a single integer denoting the number of distinct snack types available along the chosen path.

Note: It is guaranteed that the planets form a tree, and therefore there exists a unique shortest path between any two planets.

inputFormat

The first line of the input contains two integers \(n\) and \(q\) separated by a space.

The second line contains \(n\) integers \(c_1, c_2, \ldots, c_n\), where each \(c_i\) denotes the type of snack available at the \(i\)-th planet.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing a route between planets \(u\) and \(v\).

The following \(q\) lines each contain two integers \(s_i\) and \(t_i\), indicating a query from planet \(s_i\) to planet \(t_i\).

outputFormat

For each query, output a single integer on a new line: the count of different snack types that can be bought along the unique shortest path from the start planet to the end planet.

sample

3 2
1 2 3
1 2
2 3
1 3
2 3

3
2