SP30734 ADAORANG - Ada and Orange Tree

瓢虫 $Ada$ 住在一棵橘子树下。相比于读书，她更喜欢调查树上的橘子。橘子们有至多 $250$ 种颜色，它们由枝条连接着。橘子的数量比枝条多，但是任何两个橘子都可以互相到达。另外，这棵树有根节点。 $Ada$ 很关心她的橘子们，她希望你告诉她：从给定的橘子 $A$ 到给定的橘子 $B$ 的最短路径上，经过的所有节点的子树中橘子颜色的种类数。

第一行包含一个整数，表示数据组数。 每组数据的第一行包含三个整数，分别表示橘子的总数 $N$ ，询问数 $Q$ 和根节点的编号。（橘子的编号从 $0$ 到 $N-1$） 接下来的一行包含 $N$ 个整数，第 $i$ 个整数表示编号为 $i-1$ 的橘子的颜色。 接下来的 $N-1$ 行每行包含两个整数，表示一根枝条所连接的两个橘子的编号。 接下来的 $Q$ 行每行包含两个整数，表示一组询问中两个橘子的编号。

对于每个询问，输出一行一个整数表示所求答案。

$\sum{N}\leq10^6$，$\sum{Q}\leq10^6$。