Trong thời gian rảnh, Farmer John tạo dịch vụ chia sẻ video mới tên MooTube. Bò của ông có thể quay, chia sẻ và khám phá nhiều video thú vị. Chúng đã đăng $N$ video ($1 \leq N \leq 5000$), đánh số $1 \ldots N$. Tuy nhiên, FJ chưa biết cách giúp chúng tìm video mới mà chúng có thể thích.

FJ muốn tạo danh sách «video đề xuất» cho mỗi video MooTube để đề xuất những video liên quan nhất đến video bò đang xem.

FJ đặt ra thước đo «mức liên quan», đúng như tên gọi, thể hiện hai video liên quan đến nhau ra sao. Ông chọn $N-1$ cặp và tự tính mức liên quan từng cặp. Sau đó biểu diễn video thành mạng: mỗi video là một đỉnh, $N-1$ cặp đã xét được nối nhau. Ông chọn $N-1$ cặp sao cho giữa hai video bất kỳ có đúng một đường đi qua các kết nối. Mức liên quan của bất kỳ cặp video nào là mức liên quan nhỏ nhất của một kết nối trên đường đi đó.

Farmer John muốn chọn $K$ để bên cạnh mỗi video MooTube đề xuất tất cả video khác có mức liên quan với nó ít nhất $K$. Nhưng quá nhiều đề xuất có thể khiến bò xao nhãng việc sản xuất sữa! Vì vậy ông muốn cẩn thận chọn $K$ thích hợp. Hãy giúp trả lời các câu hỏi về đề xuất với những giá trị $K$ cụ thể.

Dữ liệu vào

Dòng đầu chứa $N$ và $Q$ ($1 \leq Q \leq 5000$).

$N-1$ dòng tiếp theo mô tả các cặp FJ tự so sánh. Mỗi dòng chứa ba số nguyên $p_i$, $q_i$ và $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$): video $p_i$ và $q_i$ được nối với mức liên quan $r_i$.

$Q$ dòng tiếp theo mô tả $Q$ câu hỏi của Farmer John. Mỗi dòng chứa hai số nguyên $k_i$ và $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): câu hỏi thứ $i$ hỏi có bao nhiêu video được đề xuất cho người xem video $v_i$ nếu $K = k_i$.

Dữ liệu ra

In $Q$ dòng. Dòng thứ $i$ là đáp án câu hỏi thứ $i$ của FJ.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3
0
2

Ghi chú

Video1 và2 có mức liên quan3, video2 và3 là2, video2 và4 là4. Do đó mức liên quan giữa1 và3 là $min(3, 2) = 2$, giữa1 và4 là $min(3, 4) = 3$, giữa3 và4 là $min(2, 4) = 2$.

Farmer John muốn biết số video đề xuất từ video2 khi $K=1$, từ video1 khi $K=3$ và từ video1 khi $K=4$. Khi $K=1$, video1,3,4 được đề xuất ở video2. Khi $K=4$, không video nào được đề xuất ở video1. Khi $K=3$, video2,4 được đề xuất ở video1.

Tác giả bài toán: Jay Leeds