Cho một đồ thị vô hướng liên thông  đỉnh và  ~n - 1~ cạnh, các đỉnh đánh số từ 1 đến ~n~. Mỗi cạnh của đồ thị được gán một giá trị nguyên dương được gọi là trọng số của cạnh.

Một đường đi đơn từ đỉnh ~u~ đến đỉnh ~v~ là dãy ~u = x_1x_2 … x_k = v~. Trong đó ~(x_i, x_{i+1})i = 1 ÷ (k − 1)~ là các cạnh của đồ thị và ngoài ra ~x_i ≠ x_j ∀ i ≠ j~. Giá trị của đường đi trên là:

min{~L(x_i, x_{i+1}~) : ~i = 1, 2, ..., k - 1~}

Ở đây, L(~x_i, x_{i+1})~ là trọng số của cạnh ~(x_i, x_{i+1})~

Yêu cầu: Trả lời ~Q~ câu hỏi, mỗi câu hỏi được mô tả bởi 2 số nguyên dương ~k, v~ với ý nghĩa: Đếm xem có bao nhiêu đỉnh ~u~ của đồ thị mà có trọng số của đường đi đơn từ ~u~ đến ~v~ lớn hơn hoặc bằng ~k~?

Input

• Dòng thứ nhất chứa hai số nguyên ~n, Q~, ~(1 \le n, Q \le 10^5)~
• ~n - 1~ dòng tiếp theo mô tả các cạnh của đồ thị, dòng thứ ~i~ chứa 3 số nguyên ~p_i, q_i~ và ~r_i (1 \le p_i, q_i \le n, 1 \le r_i \le 10^9)~ thể hiện rằng có cạnh nối 2 đỉnh ~p_i, q_i~ có trọng số ~r_i~.
• ~Q~ dòng tiếp theo, mỗi dòng ghi một truy vấn gồm hai số nguyên ~k, v (1 \le k \le 10^9, 1 \le v \le n)~ thể hiện yêu cầu đếm xem có bao nhiêu đỉnh mà trọng số đường đi đơn từ nó đến ~v~ lớn hơn hoặc bằng ~k~?.

Subtasks:

• Subtask 1: ~n \le 10000~
• Subtask 2: ~n \le 10^5~

Output

• gồm ~Q~ dòng, mỗi dòng ghi một số nguyên là kết quả của truy vấn tương ứng (theo thứ tự xuất hiện trong file dữ liệu vào)

Sample

Input #1

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

Output #1

3
0
2

Problem source: Bài tập ôn thầy Lê Thanh Bình - Hải Dương - T11/2019