http://www.usaco.org/index.php?page=viewproblem2&cpid=789

Trong thời gian rảnh rỗi, Nông dân John đã tạo ra một dịch vụ chia sẻ video mới, anh ta đặt tên là JohnTube. Trên JohnTube, những con bò của Nông dân John có thể ghi lại, chia sẻ và khám phá nhiều video thú vị. Những con bò của anh ấy đã đăng N video, được đánh số từ 1 đến N. Tuy nhiên, FJ hoàn toàn không thể tìm ra cách giúp những con bò của mình tìm thấy những video mới mà có thể chúng “like”.

FJ muốn tạo một danh sách "video được đề xuất" cho mỗi video JohnTube. Bằng cách này, những con bò sẽ biết được những video đề xuất liên quan, phù hợp nhất với video chúng đang xem.

FJ đưa ra một số liệu về "mức độ liên quan", xác định hai video có liên quan với nhau như thế nào. Anh ta chọn N − 1 cặp video và tự tính toán mức độ liên quan giữa 2 video này. Sau đó, FJ hình dung các video của mình như một mạng, trong đó mỗi video là một nút và N-1 cặp video đã xác định mức độ liên quan là các kết nối giữa những video. Thông qua N-1 cặp video này, FJ có thể truy cập bất kỳ video nào khác dọc theo đường kết nối giữa các video theo đúng một cách duy nhất.

FJ quy định rằng mức độ liên quan của bất kỳ cặp video nào phải được xác định là mức độ liên quan tối thiểu của một kỳ kết nối nào đó trên đường kết nối giữa 2 video này.

Nông dân John muốn chọn một giá trị K mức độ liên quan để bên cạnh bất kỳ video JohnTube cụ thể nào, tất cả các video khác có mức độ liên quan ít nhất K với video đó sẽ được đề xuất. Tuy nhiên, FJ lo lắng rằng quá nhiều video sẽ được đề xuất cho những con bò của mình, điều này có thể khiến chúng mất tập trung vào sản xuất sữa! Do đó, anh ấy muốn đặt cẩn thận một giá trị thích hợp của K cho mỗi video. Nông dân John muốn bạn giúp trả lời một số câu hỏi về các video được đề xuất cho các giá trị nhất định của K.

input

• Dòng đầu tiên chứa N và Q. N−1 dòng tiếp theo, mỗi dòng mô tả một cặp video mà FJ đã tự tính toán gồm ba số nguyên p_i, q_i và r_i cho biết rằng video p_i và q_i được kết nối với nhau với mức độ liên quan là r_i.
• Q tiếp theo, mỗi dòng mô tả câu hỏi Q của Nông dân John gồm hai số nguyên k_j và v_j (1≤v_j≤N; 1≤ j ≤Q), cho biết câu hỏi thứ j của FJ hỏi có bao nhiêu video sẽ được đề xuất cho người xem video v_j nếu K = k_j.

Output:

• Ghi Q dòng, dòng thứ i ghi câu trả lời cho câu hỏi thứ i

Ràng buộc:

• 1 ≤ p_i, q_i ≤N, 1≤r_j, k_j ≤ 10⁹, 1 ≤ j ≤ Q;
• Sub1: 50% test có 1 <= N, Q <=5000;
• Sub2: 50% test khác có1 <= N, Q<= 10⁵.