$N$ 个顶点构成的树（无向无环连通图）已经给出。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。每个顶点都有一个权值。
请编写一个程序执行以下查询：
u v：输出从 $u$ 到 $v$ 的路径上不同顶点权值的个数。
输入格式
第一行包含 $N$（$2 \le N \le 100{,}000$）。
第二行按顺序给出从 $1$ 号顶点开始的每个顶点的权值。
接下来 $N-1$ 行中，第 $i$ 行给出连接第 $i$ 条边的两个顶点编号 $u$ 和 $v$。
下一行给出查询数量 $M$（$1 \le M \le 100{,}000$）。
接下来 $M$ 行中，每行给出一个查询。
顶点的权值均为不超过 $1{,}000{,}000$ 的自然数。
输出格式
将每个查询的结果按顺序每行一个输出。
样例
输入
8 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8 2 2 5 7 8
输出
4 4