MooTube Video Recommendation

Farmer John has created a new video sharing service called MooTube, where his cows can record, share, and discover interesting videos. He has posted N videos (numbered 1 to N). To help his cows find videos they may like, Farmer John defines a relevance measure between videos. He selects N-1 pairs of videos and manually assigns a relevance score for each pair. Then, he connects these videos to form a tree (i.e. all videos are connected by exactly N-1 edges). The relevance between any two videos is defined as the minimum relevance score along the unique path connecting them.

For a given video, Farmer John wishes to recommend all other videos for which the relevance is at least a threshold K. Given several queries, each specifying a value K and a starting video v, your task is to count how many videos will be recommended (excluding the starting video itself).

Note: A video u is recommended for video v if the minimum relevance on the path from v to u is at least K.

inputFormat

The first line of input contains two integers N and Q (1 ≤ N ≤ 10⁵), the number of videos and the number of queries.

The next N-1 lines each contain three integers: p, q, and r, indicating that videos p and q are connected by an edge with relevance r.

The following Q lines each contain two integers: K and v, representing a query. For each query, count the number of videos (other than video v) that have a relevance of at least K to video v.

outputFormat

Output Q lines. Each line contains a single integer, the answer to the corresponding query.

sample

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

3
0
2