C. Museum Visit
time limit per test
2 с
memory limit per test
256 megabytes
input
standard input
output
standard output

On Valentines Day, Alice and Bob went to a museum . The museum structure is a tree like structure where there are $$$n$$$ rooms connected by $$$n-1$$$ bidirectional doors, and you can go from any room to any other room. The entrance of the museum is room number 1.

Since Alice and Bob are quite different people, they may split in some room and each one of them goes into a separate route which doesn't contain the room they came from (parent room in the tree like structure). So Bob was worried if the distance would be very large between them (distance between rooms is the number of doors between them). So he asked you $$$q$$$ questions of the form:

  • He gives 2 integers $$$u$$$ and $$$k$$$, you need to find the number of unordered pairs of rooms that they can end up at if they are currently at room $$$u$$$ and decided to split the path and the distance between their final rooms is greater than or equal to $$$k$$$.

Note: Splitting the route also counts the case when someone stays at the current room and the other goes into another room.

Input

The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ $$$(2\leq n \leq 2.10^{5}, 1\leq q \leq 5*n)$$$.

The next $$$n-1$$$ lines each contain $$$2$$$ integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v \leq n)$$$, which means there is a door between room $$$u$$$ and room $$$v$$$, it's guaranteed that you can go from any room to any other room.

The next $$$q$$$ lines each contain $$$2$$$ integers $$$u$$$ and $$$k$$$ $$$(1\leq u \leq n, 1\leq k \leq n-1)$$$

It is guaranteed that every number $$$u$$$ doesn't appear more than $$$5$$$ times in the queries.

Output

For the answer for each question in separate lines.

Example
Input
9 4
1 2
2 3
3 4
4 5
2 6
2 7
6 8
4 9
1 2
2 3
3 2
6 1
Output
7
13
2
1
Note

Explanation of the third query: the only 2 possible pairs are $$$(3,5)$$$ $$$(3,9)$$$, the pair $$$(5,9)$$$ doesn't count since they splitted their route at room $$$4$$$ and not $$$3$$$