You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小 I 最近学会了一种称作连喵树（link-meow-tree）的算法，他想要你帮他解决下面这样的问题。

题目描述

考虑维护一种数据结构。维护一棵树，初始点全都是白色的，支持以下操作：

• 给定 $u,d$，并把和点 $u$ 距离不超过 $d$ 的点全部染黑。每次染色结束后输出黑色点的个数。

由于你早就学会了连喵树，所以你可以教教小 I。

输入格式

第一行两个正整数表示 $n,q$。

接下来 $n-1$ 行，每行两个正整数描述一条边。

接下来 $q$ 行，每行两个正整数 $u,d$ 表示操作。

输出格式

共 $q$ 行，表示每次操作的答案。

测试样例

样例 $1$ 解释

• 第一次操作后，$1$ 被染黑。
• 第二次操作后，$1,2$ 被染黑。
• 第三次操作后，$1,2$ 被染黑。
• 第四次操作后，$1,2,3$ 被染黑。
• 第五次操作后，$1,2,3,4,5$ 被染黑。

样例 $2$ 解释

样例 $2$ 满足测试点 $5$ 的性质。

数据范围

对于所有数据，保证 $n,q\leq 2\times 10^5$，$u\leq n$，$d\leq\min(500,n)$。