题目描述

给定一个包含 $n$ 个节点（从 $1$ 到 $n$ 编号）的树形图。初始有一个节点被标记为 true，其余均为 false。每个标记为 true 的节点在每一秒会把所有相邻节点标记为 true。

现在有 $m$ 次询问，每次询问假定第 $0$ 秒第 $x$ 个节点被标记为 true，请你计算第 $k$ 秒时由 false 变为 true 的节点个数（即第 $k$ 天前已经为 true 的不计入其中）。不同询问间互不影响。

输入格式

本题包含多组测试数据。

第一行一个整数 $T$，为测试数据组数。

对于每组测试数据：

第一行两个数 $n,m$ 分别表示节点个数和询问的数量。

接下来 $n - 1$ 行，每行两个数 $a, b$，表示 $a$ 号节点和 $b$ 号节点之间有连线。保证输入的是一棵树。

接下来 $m$ 行，每行两个数 $x, k$，意义见题目描述。

输出格式

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

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

1
1

提示

样例解释

第一个询问，第 $1$ 秒从 false 变为 true 的节点只有 $2$ 号。 第二个询问，第 $1$ 秒从 false 变为 true 的节点有 $1$、$3$ 号，第 $2$ 秒从 false 变为 true 的节点有 $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$。