MooTube (Gold)

Farmer John built a video sharing service called MooTube in his spare time. On MooTube his cows share funny videos with each other. The cows have already uploaded $N$ videos, numbered 1 through $N$. John still has no good way to help a cow find a new video she would like.

John decided to build a list of related videos for every video, so that a cow is recommended videos close to the one she is watching.

How close two videos are is measured by USADO, a unit John invented. He picked $N-1$ pairs of videos and computed the USADO of each pair himself. He chose those $N-1$ pairs so that exactly one path runs from any video to any other video. Treating the videos as vertices and the measured pairs as edges, the whole thing is one tree. The USADO of two videos he did not measure directly is the smallest USADO among the edges on the path between them.

John picks one video and a value $K$, then recommends every video whose USADO with that video is at least $K$. Too many recommendations would keep the cows from working, so he wants to choose $K$ well. Given $K$ and a video number, report how many videos are recommended.

The first line contains the number of videos $N$ and the number of questions $Q$. ($1 \le N \le 100\,000$, $1 \le Q \le 100\,000$)

Each of the next $N-1$ lines contains one measurement as three integers $p_i$, $q_i$, $r_i$ ($1 \le p_i, q_i \le N$, $1 \le r_i \le 1\,000\,000\,000$), meaning that video $p_i$ and video $q_i$ are connected with USADO $r_i$.

Each of the next $Q$ lines contains one question as two integers $k_i$ and $v_i$ ($1 \le k_i \le 1\,000\,000\,000$, $1 \le v_i \le N$), asking how many videos are recommended to a cow watching video $v_i$ when $K = k_i$.

Print $Q$ lines. Line $i$ contains the answer to the $i$-th question.

In the sample the USADO of videos 1 and 2 is 3, the USADO of videos 2 and 3 is 2, and the USADO of videos 2 and 4 is 4. From those measurements the USADO of videos 1 and 3 is $\min(3, 2) = 2$, the USADO of videos 1 and 4 is $\min(3, 4) = 3$, and the USADO of videos 3 and 4 is $\min(2, 4) = 2$.

With $K = 1$ and video 2, the recommended videos are 1, 3 and 4. With $K = 4$ and video 1, nothing is recommended. With $K = 3$ and video 1, videos 2 and 4 are recommended.