• 输入：mine.in
• 输出：mine.out
• 时间限制：1.0 s
• 内存限制：512 MiB

题目描述

尼克斯星系中有一棵 $n$ 个结点的树，第 $i$ 个点上的矿石种类为 $c_i$。

宇宙无敌霸王龙帝国会派出 $q$ 艘采矿船。每次给定两个点 $s,t$，考虑树上从 $s$ 到 $t$ 的简单路径，求这条路径上能采集多少种不同的矿石。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $c_1,c_2,...,c_n$。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$，表示树上的一条边。

接下来 $q$ 行，每行两个整数 $s_i,t_i$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数表示对应询问的答案。

样例1输入

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

样例1输出

3
2

数据范围

对于所有测试数据，保证：$1 <= n,q <= 10^5$，$1 <= c_i <= 20$。