Trong thời gian rảnh, bác nông dân John đã tạo một dịch vụ chia sẻ video mới mang tên MooTube. Trên MooTube, đàn bò của ông có thể quay, chia sẻ và khám phá nhiều video thú vị. Đàn bò đã đăng \(N\) video (\(1 \leq N \leq 100{,}000\)), được đánh số thuận tiện từ \(1 \ldots N\). Tuy nhiên, bác nông dân John vẫn chưa tìm ra cách giúp đàn bò khám phá những video mới mà chúng có thể yêu thích.

Bác nông dân John muốn tạo một danh sách “video được đề xuất” cho mỗi video trên MooTube. Nhờ đó, đàn bò sẽ được giới thiệu những video liên quan nhất đến các video chúng đã xem.

Bác nông dân John nghĩ ra một thước đo gọi là “độ liên quan”, đúng như tên gọi, dùng để xác định mức độ liên quan giữa hai video. Ông chọn \(N-1\) cặp video và tự tính độ liên quan của từng cặp. Sau đó, ông hình dung các video như một mạng lưới, trong đó mỗi video là một nút và \(N-1\) cặp video mà ông đã xem xét được nối với nhau. Thật thuận tiện, bác nông dân John đã chọn \(N-1\) cặp sao cho từ bất kỳ video nào cũng có đúng một cách để đi theo một đường gồm các liên kết đến bất kỳ video nào khác. Ông quyết định định nghĩa độ liên quan của một cặp video là độ liên quan nhỏ nhất của một liên kết trên đường đi này.

Bác nông dân John muốn chọn một giá trị \(K\) sao cho bên cạnh một video MooTube bất kỳ, tất cả các video khác có độ liên quan với video đó ít nhất là \(K\) đều được đề xuất. Tuy nhiên, ông lo rằng quá nhiều video sẽ được đề xuất cho đàn bò, khiến chúng xao nhãng việc sản xuất sữa! Vì vậy, ông muốn cẩn thận chọn một giá trị \(K\) phù hợp. Bác nông dân John cần bạn giúp trả lời một số câu hỏi về các video được đề xuất ứng với những giá trị \(K\) nhất định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\) (\(1 \leq Q \leq 100{,}000\)).

Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một cặp video mà bác nông dân John 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\)), cho biết video \(p_i\) và video \(q_i\) được nối với nhau bằng một liên kết có độ liên quan \(r_i\).

\(Q\) dòng tiếp theo mô tả \(Q\) câu hỏi của bác nông dân 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\)), cho biết câu hỏi thứ \(i\) của ông là có bao nhiêu video sẽ được đề xuất cho người xem video \(v_i\) nếu \(K=k_i\).

Dữ liệu ra

In ra \(Q\) dòng. Trên dòng thứ \(i\), in ra câu trả lời cho câu hỏi thứ \(i\) của bác nông dân John.

Ví dụ

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

3
0
2

Nguồn

USACO 2018 January Contest, Gold — MooTube

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