背景

我该如何迎接希望？我问我自己。

he- he- hello sunshine

bye bye say bye to the night

——洛天依《hello&bye,days》

题目描述

小 Z 得到了一棵树！

这棵树共有 $N$ 个结点，编号为 $1,2,\dots,N$，以 $1$ 号结点为根。根的深度是 $1$，每一个结点的深度定义为该节点到 $1$ 号根节点的简单路径上的边数加 $1$。对于 $1 \le i \le N$，$i$ 号节点有一个权值 $A_i$。令 $D$ 为树的深度。

定义 $F(num_1,num_2)$ 为 $num_1$ 号结点对应的子树中深度为 $num_2$ 的结点权值的可重集合。

需要注意的是，这里深度的定义如第一段所描述，指的是以节点 $1$ 为根的深度，而非以节点 $num_1$ 为根。

特别地，若不存在 $num_1$ 号结点对应的子树中不存在深度 $num_2$，则 $F(num_1,num_2)=\emptyset$。

小 Z 会对你进行 $Q$ 次询问，每次询问给定两个正整数 $x$ 和 $d$，你需要计算有多少组 $(a,b)$ 满足以下条件：

• $1 \le a \le N$，$1 \le b \le D$；
• $(a,b) \neq (x,d)$；
• $F(x,d)=F(a,b)$。

输入格式

第一行包含两个正整数 $N$ 和 $Q$，分别表示树上结点的数量和询问的次数。

第二行包含 $N$ 个非负整数 $A_i$，表示每个结点的权值。

接下来 $N-1$ 行，每行两个正整数 $u$ 和 $v$，表示 $u$ 号结点和 $v$ 号结点之间存在一条边。

接下来 $Q$ 行，每行两个正整数 $x$ 和 $d$，表示询问的内容，含义见题目描述。

输出格式

对于每次询问，包含一行一个非负整数，表示答案。

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

1
0
1
1
11

提示

对于 $100\%$ 的数据，保证 $1 \le N,Q \le 10^5$，$1 \le A_i \le 10^5$，$1 \le u,v \le N$，$1 \le u \le N$，$1 \le d \le D$。