MooTube Video Recommendations

Farmer John has created a new video sharing service called MooTube where his cows can record, share, and discover fun videos. He has published \(N\) videos (numbered \(1,\ldots, N\)) and connected them with \(N-1\) links to form a tree. Each link between two videos has a "relevance" score. The relevance between any two videos is defined as the minimum relevance score along the unique path that connects them.

For a given video and a threshold \(K\), Farmer John wants to recommend all other videos that have a relevance of at least \(K\) with the given video. Your task is to answer several queries. Each query provides a threshold \(K\) and a starting video \(v\); you should output the number of videos (excluding \(v\) itself) that have relevance at least \(K\) with \(v\).

Note: The tree structure ensures that any video can be reached from any other through a unique path.

inputFormat

The first line contains two integers \(N\) and \(Q\) (\(1 \leq N \leq 5000\)) representing the number of videos and the number of queries.

The next \(N-1\) lines each contain three integers \(p\), \(q\), and \(r\) describing a connection between videos \(p\) and \(q\) with a relevance score \(r\).

The following \(Q\) lines contain two integers each: \(K\) and \(v\). For each query, you should output the number of videos different from \(v\) that have a relevance of at least \(K\) with video \(v\).

outputFormat

For each query, output a single integer on a new line representing the number of videos that will be recommended.

sample

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

3
0
2