Count Nodes

A tree on $N$ nodes labeled with integers between $0$ and $N-1$ is given. Your task is to answer the following query:

• Given the node $u$ and the integer $d$, count the number of unique nodes that can be reached from $u$ by crossing at most $d$ edges.

Input

The first line of input contains the integers $N$ and $Q$ ($1 \leq N,Q \leq 2*10^5$), the number of nodes and queries.

The following $N-1$ lines each contain the integers $a$ and $b$ ($0 \leq a,b \leq N-1$), which means that there is an edge between node $a$ and $b$. These edges are guaranteed to form a tree.

Then, the next $Q$ each contain a query.

Each query consists of the integers $u$ and $d$ ($1 \leq u,d \leq N-1$), the starting node and the number of edges you may cross.

Output

For each query, print the number of unique nodes that can be reached from $u$ by crossing at most $d$ edges.

Scoring

Your solution will be tested on multiple testcases. To solve the problem, your solution must solve every testcase correctly.

5 5
0 1
1 2
2 3
2 4
0 0
0 1
0 2
2 1
2 2

1
2
3
4
5