Trong thời gian rảnh, Farmer John tạo dịch vụ chia sẻ video MooTube. Bò có thể ghi, chia sẻ, khám phá video vui. Chúng đã đăng $N$ video ($1\le N\le100{,}000$), đánh số $1\ldots N$, nhưng FJ chưa biết cách giúp tìm video mới chúng có thể thích.

Ông muốn danh sách “video đề xuất” cho mỗi video, đề xuất những video liên quan nhất tới video đang xem.

FJ đặt thước đo “độ liên quan” giữa hai video. Chọn $N-1$ cặp, ông tự tính từng cặp. Ông xem video là đỉnh mạng và nối các cặp đã chọn sao cho giữa mọi hai video có đúng một đường đi. Độ liên quan của một cặp là độ liên quan nhỏ nhất của các nối trên đường đó.

FJ chọn $K$ để bên mỗi video đề xuất tất cả video khác có độ liên quan ít nhất $K$. Nhưng quá nhiều sẽ khiến bò xao nhãng sản xuất sữa! Ông muốn chọn $K$ kỹ lưỡng và nhờ trả lời các câu hỏi về đề xuất cho vài $K$.

Dữ liệu vào

Dòng đầu chứa $N,Q$ ($1\le Q\le100{,}000$).

$N-1$ dòng tiếp mô tả các cặp tự so sánh. Các số nguyên $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) biểu thị nối giữa $p_i,q_i$ có độ liên quan $r_i$.

$Q$ dòng tiếp là câu hỏi. Số nguyên $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) hỏi trong câu $i$ bao nhiêu video được đề xuất cho người xem $v_i$ nếu $K=k_i$.

Dữ liệu ra

In $Q$ dòng; dòng $i$ trả lời câu $i$.

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ú

Độ liên quan của $1,2$, của $2,3$, của $2,4$ là $3,2,4$. Vậy của $1,3$, của $1,4$, của $3,4$ là $\min(3,2)=2$, $\min(3,4)=3$, $\min(2,4)=2$.

FJ hỏi video $2$ khi $K=1$, video $1$ khi $K=3$, và video $1$ khi $K=4$. Khi $K=1$, $2$ đề xuất $1,3,4$; khi $K=4$, $1$ không đề xuất gì; khi $K=3$, $1$ đề xuất $2,4$.

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