[省选联考 2020 B 卷] 消息传递

题目描述

给定一个包含 $n$ 个人(从 $1$ 到 $n$ 编号)的树形社交网络。如果一个人在某天收到了一条消息,则下一天他会将消息传递给所有与他有直接社交关系的人。 现在有 $m$ 次询问,每次询问假定第 $0$ 天 $x$ 号人收到了一条消息,请你计算第 $k$ 天时新收到此条消息的人数(即第 $k$ 天前收到过此条消息的人不计入其中)。不同询问间互不影响。

输入输出格式

输入格式


**本题包含多组测试数据。** 第一行一个整数 $T$,为测试数据组数。 对于每组测试数据: 第一行两个数 $n,m$ 分别表示树形社交网络的人数和询问的数量。 接下来 $n - 1$ 行,每行两个数 $a, b$,表示 $a$ 号人和 $b$ 号人之间有直接社交关系。保证输入的是树形社交网络。 接下来 $m$ 行,每行两个数 $x, k$,意义见题目描述。

输出格式


对于每组测试数据:输出 $m$ 行,每行一个数表示询问的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

1
1

说明

**样例解释** 第一个询问,第一天新收到消息的人只有 $2$ 号。 第二个询问,第一天新收到消息的人有 $1$、$3$ 号,第二天新收到消息的人有 $4$ 号。 **数据范围与约定** 对于测试点 $1$:$1\le n, m\le 10$。 对于测试点 $2$:$1\le n, m\le 100$。 对于测试点 $3$:$1\le n, m\le 1000$。 对于测试点 $4\sim6$:$1\le n, m\le 10^5, k\le 20$。 对于测试点 $7\sim10$:$1\le n, m\le 10^5$。 对于所有测试点:$1\le T\le 5, 1\le x\le n, 0\le k < n$。