给定一个包含 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
样例 1 解释
第一个询问,第一天新收到消息的人只有 2 号。
第二个询问,第一天新收到消息的人有 1、3 号,第二天新收到消息的人有 4 号。
子任务
对于测试点 1:1≤n,m≤10。
对于测试点 2:1≤n,m≤100。
对于测试点 3:1≤n,m≤1000。
对于测试点 4∼6:1≤n,m≤105,k≤20。
对于测试点 7∼10:1≤n,m≤105。
对于所有测试点:1≤T≤5,1≤x≤n,0≤k<n。