MooTube (Gold)#10423

MooTube (Gold)

1 second

128 megabytes

Hard

In his spare time, Farmer John (FJ) has created a new video-sharing service, which he has named MooTube. On MooTube, Farmer John's cows can record, share, and discover many amusing videos. His cows have already posted $n$ videos, conveniently numbered from $1$ to $n$ . However, FJ cannot quite figure out how to help his cows find new videos they might like.

FJ wants to create a list of "suggested videos" for every MooTube video. This way, cows will be recommended the videos most relevant to the ones they have already watched.

FJ devises a metric of "relevance" which, as the name suggests, determines how relevant two videos are to each other. He picks $n - 1$ n - 1 pairs of videos and manually computes the relevance of each pair. FJ then visualizes his videos as a network in which each video is a node, and the $n - 1$ n - 1 pairs of videos he considered manually are connected by edges. Conveniently, FJ has chosen these $n - 1$ n - 1 pairs so that any video can be reached from any other video along a path of connections in exactly one way. FJ decides that the relevance of any pair of videos is defined as the minimum relevance of the connections along this path.

Farmer John wants to pick a value $k$ such that, for any given MooTube video, all other videos with relevance at least $k$ to that video will be suggested. However, FJ is worried that too many videos will be suggested to his cows, which could distract them from milk production! Therefore, he wants to choose the value of $k$ carefully. Farmer John would like your help in answering a number of questions about the suggested videos for certain values of $k$ .

Input

The first line contains two integers $n$ and $q (1 \leq n \leq 1 0^{5}, 1 \leq q \leq 1 0^{5})$ q~(1 \le n \le 10^5, 1 \le q \le 10^5). Each of the next $n - 1$ n - 1 lines describes a pair of videos that FJ compares manually. Each line contains three integers $a_{i}$ a_i, $b_{i}$ b_i and $r_{i} (1 \leq a_{i}, b_{i} \leq n, 1 \leq r_{i} \leq 1 0^{9})$ r_i~(1 \le a_i, b_i \le n, 1 \le r_i \le 10^9), indicating that videos $a_{i}$ a_i and $b_{i}$ b_i are connected with relevance $r_{i}$ r_i.

The next $q$ lines describe Farmer John's $q$ questions. Each line contains two integers $k_{i}$ k_i and $v_{i} (1 \leq k_{i} \leq 1 0^{9}, 1 \leq v_{i} \leq n)$ v_i~(1 \le k_i \le 10^9, 1 \le v_i \le n), indicating that FJ's $i$ -th question asks how many videos will be suggested to viewers of video $v_{i}$ v_i if $k = k_{i}$ k = k_i.

Output

Print $q$ lines. On the $i$ -th line, print the answer to FJ's $i$ -th question.

Examples

Example 1

Note

Farmer John finds that videos $1$ and $2$ have relevance $3$ , videos $2$ and $3$ have relevance $2$ , and videos $2$ and $4$ have relevance $4$ . Based on this, videos $1$ and $3$ have relevance $min (3, 2) = 2$ \min(3, 2) = 2, videos $1$ and $4$ have relevance $min (3, 4) = 3$ \min(3, 4) = 3, and videos $3$ and $4$ have relevance $min (2, 4) = 2$ \min(2, 4) = 2.

Farmer John wants to know how many videos will be suggested for video $2$ if $k = 1$ k = 1, for video $1$ if $k = 3$ k = 3, and for video $1$ if $k = 4$ k = 4. With $k = 1$ k = 1, videos $1$ , $3$ and $4$ will be suggested for video $2$ . With $k = 3$ k = 3, videos $2$ and $4$ will be suggested for video $1$ . With $k = 4$ k = 4, however, no videos will be suggested for video $1$ .