Description

Given a tree-shaped social network with $n$ people (numbered from $1$ to $n$). If a person receives a message on some day, then on the next day they will pass the message to all people who have a direct social relationship with them.

Now there are $m$ queries. In each query, assume that person $x$ receives a message on day $0$. Please compute how many people newly receive this message on day $k$ (that is, people who have received this message before day $k$ are not counted). Different queries do not affect each other.

Input Format

This problem contains multiple sets of testdata.

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains two integers $n, m$, representing the number of people in the tree-shaped social network and the number of queries.

The next $n - 1$ lines each contain two integers $a, b$, indicating that there is a direct social relationship between person $a$ and person $b$. It is guaranteed that the input forms a tree-shaped social network.

The next $m$ lines each contain two integers $x, k$, as described in the statement.

Output Format

For each test case, output $m$ lines, each containing one integer representing the answer to the query.

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

1
1

Hint

Sample Explanation

For the first query, the only person who newly receives the message on day $1$ is person $2$. For the second query, the people who newly receive the message on day $1$ are persons $1$ and $3$, and the person who newly receives the message on day $2$ is person $4$.

Constraints and Notes

For test point $1$: $1\le n, m\le 10$.
For test point $2$: $1\le n, m\le 100$.
For test point $3$: $1\le n, m\le 1000$.
For test points $4\sim6$: $1\le n, m\le 10^5, k\le 20$.
For test points $7\sim10$: $1\le n, m\le 10^5$.
For all test points: $1\le T\le 5, 1\le x\le n, 0\le k < n$.

Translated by ChatGPT 5