Zoo

Jozo started working at a newly built zoo earlier this year. Today he received a special assignment: find the cause of the steady drop in visitors. While watching the enclosures and the paths between them, Jozo suspected that the tours are too boring, that is, that the zoo tours are too uniform.

The zoo has $N$ enclosures numbered from $1$ to $N$ and $N-1$ paths, each connecting two enclosures. There is a path between every pair of enclosures (not necessarily a direct one). Each enclosure holds animals of one species. Enclosure $i$ holds animals of species $v_i$.

Jozo asked you to help him determine the uniformity of a path. The uniformity of a path is the number of occurrences of the most common animal among the enclosures on that path, including the enclosures at both ends. For example, if a path passes through enclosures with animals $2$, $3$, $1$, $2$, $2$, $3$, the uniformity is three, because animal $2$ appears three times.

For each of the $Q$ pairs of enclosures $(a, b)$, find the uniformity of the (shortest) path from enclosure $a$ to enclosure $b$.

The first line contains natural numbers $N$ and $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 10^5$).

The second line contains $N$ natural numbers $v_i$ ($1 \le v_i \le 10^9$), the species of the animals in enclosure $i$.

Each of the next $N-1$ lines contains two natural numbers $x_i$ and $y_i$ ($1 \le x_i, y_i \le N$), the two enclosures connected by the $i$-th path.

Each of the next $Q$ lines contains two natural numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$), describing the path from enclosure $a_i$ to enclosure $b_i$ whose uniformity must be found.

Print $Q$ lines. On the $i$-th line, print the answer to the $i$-th question.

This explains the first sample. Each node shows the enclosure number and the animal species.

Query 1: the enclosures on the path are 1 and 2. Species 1 and 2 each appear once, so the uniformity is $1$.

Query 2: the enclosures on the path are 1, 2, and 4. Species 1 appears twice, so the uniformity is $2$.

Query 3: the enclosures on the path are 4, 2, 1, 3, and 7. Species 1 appears three times, in enclosures 1, 4, and 7.

Query 4: the enclosures on the path are 2, 1, and 3. Species 2 appears twice and species 1 appears once.

Query 5: the enclosures on the path are 5, 2, 1, 3, and 6. Species 2 appears four times and species 1 appears once.