题目描述

给定一棵包含 $n$ 个顶点的树。每个顶点 $i$ 有一个颜色 $c_i$。

树上两个顶点 $u,v$ 的距离定义为它们之间最短路径所包含的边数。

你需要回答 $q$ 个询问。每个询问给出一个顶点 $v$ 和一种颜色 $c$：

• 求从 $v$ 出发，到任意一个颜色为 $c$ 的顶点的最大距离；
• 如果整棵树中不存在颜色为 $c$ 的顶点，输出 -1。

输入格式

第一行两个整数 $n,q$，满足 $1\le n,q\le5\times10^5$。

第二行 $n$ 个整数 $c_1,c_2,\ldots,c_n$，其中 $1\le c_i\le5\times10^5$。

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

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

输出格式

对于每个询问输出一行：

• 若存在颜色为 $c$ 的顶点，输出从 $v$ 到这些顶点的最大距离；
• 否则输出 -1。

样例

10 15
2 6 5 99 500000 6 5 3 5 5
1 2
2 10
1 3
3 5
3 6
6 7
1 4
4 8
4 9
3 5
4 5
2 5
6 5
8 500000
5 500000
5 1000
6 6
8 6
5 99
3 6
3 100
9 5
7 5
3 3

3
4
4
4
4
0
-1
3
4
3
2
-1
5
5
3

子任务