Problem Description

Xiaolan is preparing to travel in space. Before leaving, he wants to buy some snacks in this galaxy. There are $n$ planets in the galaxy, connected by $n - 1$ space routes, forming a connected graph. The $i$-th planet sells the $c_i$-th type of local snack.

Xiaolan comes up with $q$ purchasing plans. In the $i$-th plan, the starting planet is $s_i$ and the destination planet is $t_i$. For each plan, Xiaolan will travel from the start to the destination along the shortest routes, and he can buy all snacks sold on the planets he passes through (including the start and destination). Please compute, for each plan, the maximum number of different snack types he can buy.

Input Format

The first line contains two positive integers $n$ and $q$, separated by a single space.
The second line contains $n$ integers $c_1,c_2,\cdots, c_n$, with a single space between adjacent integers.
The next $n - 1$ lines each contain two integers $u_i,v_i$, separated by a single space, meaning there is a route connecting planet $u_i$ and planet $v_i$.
The next $q$ lines each contain two integers $s_i, t_i$, separated by a single space, representing one purchasing plan.

Output Format

Output $q$ lines. Each line contains one integer, in order, representing the answer for each purchasing plan.

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

3
2

Hint

For the first plan, the route is $\{4, 2, 1, 3\}$, and Xiaolan can buy snack types $1, 2, 3$.
For the second plan, the route is $\{1, 2, 4\}$, and Xiaolan can buy snack types $1, 2$.

For $20\%$ of the testdata, $1 \le n, q \le 5000$.
For all testdata, $1 \le n, q \le 10^5$, $1 \le c_i \le 20$, $1 \le u_i, v_i \le n$, $1 \le s_i, t_i \le n$。

Translated by ChatGPT 5