Problem Description

There is a tree with $ N $ vertices. The $ i $th edge connects vertex $ A_i $ and vertex $ B_i $.

Answer the following $ Q $ queries:

• Determine the number of vertices that can be reached from vertex $ v_i $ by traversing exactly $ k_i $ edges without returning.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ A_1 $ $ B_1 $ : $ A_{N-1} $ $ B_{N-1} $ $ v_1 $ $ k_1 $ : $ v_Q $ $ k_Q $

Output Format

For each query, output the number of vertices that can be reached from vertex $ v_i $ by traversing exactly $ k_i $ edges without returning.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
2
1
0
1

Sample Input #2

7 35
1 2
2 3
1 4
1 5
5 6
5 7
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
6 0
6 1
6 2
6 3
6 4
7 0
7 1
7 2
7 3
7 4

Sample Output #2

1
3
3
0
0
1
2
2
2
0
1
1
1
2
2
1
1
2
3
0
1
3
2
1
0
1
1
2
2
1
1
1
2
2
1

Notes/Hints

Constraints

• $1 \leq N, Q \leq 10^5$
• $1 \leq A_i, B_i \leq N (1 \leq i \leq N-1)$
• $1 \leq v_i \leq N (1 \leq i \leq Q)$
• $0 \leq k_i \leq N - 1 (1 \leq i \leq Q)$
• The graph given in the input is a tree.
• All inputs are integers.

Sample Explanation 1

• For the first query, only vertex $ 1 $ can be reached from vertex $ 1 $ by traversing exactly $ 0 $ edges. Therefore, output $ 1 $.
• For the second query, vertices $ 2 $ and $ 3 $ can be reached from vertex $ 2 $ by traversing exactly $ 1 $ edge. Therefore, output $ 2 $.
• For the third query, only vertex $ 4 $ can be reached from vertex $ 3 $ by traversing exactly $ 2 $ edges. Therefore, output $ 1 $.
• For the fourth query, no vertices can be reached from vertex $ 4 $ by traversing exactly $ 4 $ edges. Therefore, output $ 0 $.
• For the fifth query, only vertex $ 3 $ can be reached from vertex $ 5 $ by traversing exactly $ 1 $ edge. Therefore, output $ 1 $.

见题面 Input 部分

见题面 Output 部分