Farmer John は余暇に MooTube という動画共有サービスを作りました。牛たちは MooTube で楽しい動画を撮影し、共有し、発見できます。すでに $N$ 本の動画（$1 \leq N \leq 5000$）が投稿され、$1 \ldots N$ と番号が付いています。しかし FJ は牛たちが好きそうな新しい動画を見つける方法が分かりません。

FJ は MooTube の各動画に「おすすめ動画」の一覧を作り、すでに見ている動画に最も関連する動画を牛たちに推薦したいと考えています。

FJ は、その名の通り2本の動画の関連の強さを測る「関連度」を考えます。$N-1$ 組の動画を選び、それぞれの関連度を手計算します。動画をネットワークの頂点とし、調べた $N-1$ 組を辺で結びます。選んだ $N-1$ 組は、どの動画から他のどの動画へも接続の経路がちょうど1通り存在するようになっています。任意の2本の関連度を、その経路上の接続の関連度の最小値と定義します。

Farmer John は $K$ を選び、各 MooTube 動画の横に、その動画との関連度が $K$ 以上である他の全動画を推薦したいと思っています。しかし、推薦が多すぎると牛たちが気を取られて牛乳の生産に支障が出ると心配しています。そのため適切な $K$ を慎重に決めたいのです。特定の $K$ に対するおすすめ動画についての質問に答えるのを手伝ってください。

入力

入力の1行目には $N$ と $Q$（$1 \leq Q \leq 5000$）が与えられます。

続く $N-1$ 行は FJ が手動で比較した動画の組を表します。各行は整数 $p_i$、$q_i$、$r_i$（$1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$）を含み、動画 $p_i$ と $q_i$ が関連度 $r_i$ で結ばれることを表します。

続く $Q$ 行は Farmer John の $Q$ 個の質問を表します。各行は整数 $k_i$ と $v_i$（$1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$）を含み、第 $i$ 問では $K = k_i$ のとき動画 $v_i$ の視聴者に何本の動画が推薦されるかを尋ねます。

出力

$Q$ 行を出力してください。第 $i$ 行に第 $i$ 問の答えを出力します。

入出力例

入力 1

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

出力 1

3
0
2

注記

動画1と2の関連度は3、動画2と3は2、動画2と4は4です。したがって、動画1と3の関連度は $min(3, 2) = 2$、動画1と4は $min(3, 4) = 3$、動画3と4は $min(2, 4) = 2$ です。

Farmer John は $K=1$ で動画2から、$K=3$ で動画1から、$K=4$ で動画1から何本が推薦されるか知りたいと考えます。$K=1$ では動画2に動画1、3、4が推薦されます。$K=4$ では動画1に何も推薦されません。一方、$K=3$ では動画1に動画2、4が推薦されます。

問題作成：Jay Leeds