The nearest pairs on tree

Time Limit: 1000ms

Memory Limit: 65535Kb

Description

Give a tree with n vertices,each edge has a length. Define cost(u,v)=The min edge in the path which from node u to node v .Give two integer k、h,for every pair (u,v) of verticesis called valid if cost (u,v) ∈ [k,h]. Write a program that will count how many pairs which are valid for a given tree. 

Input

The input contains several test cases. The first line of each test case contains two integers n, q. (n<=10000,q<= 10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. Then following q lines each contains two integer k,h(h>=k>=0). End of by EOF. 

Output

For each query output the answer on a singleline.

Sample Input

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

Sample Output

10
0
7
2
1
0

Hint

None

Source

朱黎原创,朱国森改编

提交代码