背景

题目来源：【HT-129-Div.1】核桃省选模拟赛

题目描述

有一棵 $n$ 个点的树，每个点上写着点权 $a_i$。称 $u$ 到 $v$ 的简单路径是好的，当且仅当这条简单路径上的点权两两不同。有 $q$ 次询问，每次给定两个点 $u,v$，求 $u$ 到 $v$ 的路径中有多少子路径是好的。

输入格式

第一行两个正整数 $n,q$ 表示树的点数和询问次数。

接下来一行 $n$ 个正整数表示 $a_1,a_2,\cdots,a_n$。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示树上的一条无向边 $u,v$。

接下来 $q$ 行，每行两个正整数 $u,v$ 表示询问的路径。

输出格式

输出 $q$ 行，每行输出一个整数表示答案。

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

3
4

提示

本题采用子任务捆绑测试。

对于 $100\%$ 的数据，保证 $1 \leq n,q \leq 10^5$，$1 \leq a_i \leq n$。