Escape Route Minimization

A clever rabbit named Xiao Lan has dug several burrows underground with many entrances and exits. There are n surface entrances and n - 1 bidirectional roads connecting them, each of length 1, forming a connected graph (i.e. a tree). The i-th entrance belongs to burrow c_i. Being resourceful, Xiao Lan can enter a burrow from any entrance that belongs to that burrow and exit from any other entrance of the same burrow at no cost on the surface.

Xiao Lan has planned m escape routes. The i-th route requires escaping from entrance s_i to t_i, while minimizing the distance traveled on the surface. When running on the surface, the road distances (each of length 1) are counted, but switching between entrances of the same burrow (i.e. teleports) does not add any distance.

You are to help compute the minimum surface distance for each escape route.

Mathematically, the tree has nodes 1,2,...,n and edges of length 1. For any two nodes u and v that belong to the same burrow (i.e. c_u = c_v), we allow a teleportation with 0 cost. Thus, the effective distance is the minimum sum of weights (where teleports contribute 0) to travel from s_i to t_i.

Note: Any formula must be rendered in \(\LaTeX\). For example, the tree has \(n-1\) roads each of length 1 and the teleportation property is defined for nodes satisfying \(c_u = c_v\).

inputFormat

The first line contains two integers n and m separated by space.

The second line contains n integers \(c_1, c_2, \ldots, c_n\), where \(c_i\) designates the burrow id of the i-th entrance.

The next n - 1 lines each contain two integers \(u\) and \(v\) indicating a bidirectional road between the u-th and v-th entrance on the surface. Each road has a length 1.

The following m lines contain two integers \(s_i\) and \(t_i\) representing a query for an escape route from entrance \(s_i\) to entrance \(t_i\>.

outputFormat

For each query, output a single line containing the minimum surface distance required to escape from the specified start entrance to the target entrance.

sample

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

0
1
2