题目描述

设 $T$ 为一棵有根树，我们做如下的定义：

• 设 $a$ 和 $b$ 为 $T$ 中的两个不同结点。如果 $a$ 是 $b$ 的祖先，那么称『$a$ 比 $b$ 不知道高明到哪里去了』。
• 设 $a$ 和 $b$ 为 $T$ 中的两个不同结点。如果 $a$ 与 $b$ 在树上的距离不超过某个给定常数 $x$，那么称『$a$ 与 $b$ 谈笑风生』。

给定一棵 $n$ 个结点的有根树 $T$，结点的编号为 $1$ 到 $n$，根结点为 $1$ 号结点。你需要回答 $q$ 个询问，询问给定两个整数 $p$ 和 $k$，问有多少个有序三元组 $(a,b,c)$ 满足：

1. $a,b,c$ 为 $T$ 中三个不同的点，且 $a$ 为 $p$ 号结点；
2. $a$ 和 $b$ 都比 $c$ 不知道高明到哪里去了；
3. $a$ 和 $b$ 谈笑风生。这里谈笑风生中的常数为给定的 $k$。

输入格式

输入文件的第一行含有两个正整数 $n$ 和 $q$，分别代表有根树的点数与询问的个数。接下来 $n-1$ 行，每行描述一条树上的边。每行含有两个整数 $u$ 和 $v$，代表在结点 $u$ 和 $v$ 之间有一条边。

接下来 $q$ 行，每行描述一个操作。第 $i$ 行含有两个整数，分别表示第 $i$ 个询问的 $p$ 和 $k$。

输出格式

输出 $q$ 行，每行对应一个询问，代表询问的答案。

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

3
1
3

数据范围

对于所有数据，保证 $1 \leq n,q \leq 3 \times 10^5$，$1 \leq p \leq n$，$1 \leq k \leq n$。