Farmer John 利用業餘時間建立了一個名為 MooTube 的新影片分享服務。在 MooTube 上，他的乳牛可以錄製、分享和發現許多有趣的影片。乳牛已經發布了 $N$ 部影片（$1 \leq N \leq 5000$），編號為 $1 \ldots N$。然而，FJ 還不知道怎樣幫助乳牛找到可能喜歡的新影片。

FJ 希望為每部 MooTube 影片建立一個「推薦影片」列表，向乳牛推薦與已經觀看的影片最相關的影片。

FJ 設計了一個「相關度」指標，顧名思義，它衡量兩部影片之間的相關程度。他選取 $N-1$ 對影片，手動計算每對的相關度。隨後，他將影片表示為一個網路，每部影片是一個節點，手動考慮的 $N-1$ 對影片之間連有邊。他選取的 $N-1$ 對保證任意兩部影片之間恰有一條連接路徑。FJ 將任意一對影片的相關度定義為該路徑上所有連接的最小相關度。

Farmer John 希望選擇一個 $K$，使任意 MooTube 影片旁都會推薦所有與它的相關度至少為 $K$ 的其他影片。不過，FJ 擔心推薦太多影片會讓乳牛分心，影響產奶！因此，他想謹慎地設定合適的 $K$。請幫助 Farmer John 回答若干關於特定 $K$ 值下推薦影片的問題。

輸入格式

第一行包含 $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$），表示 FJ 的第 $i$ 個問題詢問：當 $K = k_i$ 時，觀看影片 $v_i$ 的乳牛會收到多少部推薦影片。

輸出格式

輸出 $Q$ 行，第 $i$ 行輸出 FJ 的第 $i$ 個問題的答案。

範例

輸入格式 1

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

輸出格式 1

3
0
2

說明

Farmer John 發現影片 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