题目描述

给定一棵包含 $n$ 个顶点的有根树。每个顶点都有一个颜色。假设树的顶点编号为 $1$ 到 $n$，顶点 $v$ 的颜色用 $c_{v}$ 表示。树的根是编号为 $1$ 的顶点。

在此问题中，你需要回答 $m$ 个查询。每个查询由两个整数 $v_{j}$ 和 $k_{j}$ 描述。对于查询 $v_{j}$, $k_{j}$，其答案为满足以下条件的颜色 $x$ 的数量：在顶点 $v_{j}$ 的子树中，颜色 $x$ 的出现次数至少为 $k_{j}$ 次。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^{5}$; $1 \le m \le 10^{5}$）。

第二行包含一个整数序列 $c_{1}, c_{2}, ..., c_{n}$ （$1 \le c_{i} \le 10^{5}$）。

接下来 $n - 1$ 行描述树的边。第 $i$ 行包含两个整数 $a_{i}, b_{i}$（$1 \le a_{i}, b_{i} \le n$; $a_{i} \ne b_{i}$），表示树中一条连接顶点 $a_{i}$ 和 $b_{i}$ 的边。

接下来 $m$ 行包含查询。第 $j$ 行包含两个整数 $v_{j}, k_{j}$（$1 \le v_{j} \le n$; $1 \le k_{j} \le 10^{5}$）。

输出格式

输出 $m$ 个整数，按输入中查询出现的顺序依次输出每个查询的答案。

样例

8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3

2
2
1
0
1

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

4

样例1解释

在有根树（根节点为 $r$）中，顶点 $v$ 的子树是指满足条件 $dist(r,\ v) + dist(v,\ u) = dist(r,\ u)$ 的所有顶点 $u$ 的集合。其中 $dist(x,\ y)$ 表示顶点 $x$ 与 $y$ 之间最短路径的边数。