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 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 đề 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 hiện 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 của Nông dân John gồm hai số nguyên ~k_j~ và ~v_j~ (~1 \le v_j \le N; 1 \le j \le 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~.

Sample Input 1

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

Sample Output 1

3
0
2

Subtasks

• ~1 \le p_i, q_i \le N, 1 \le r_j, k_j \le 10^9, 1 \le j \le Q~. | Subtask | Điểm | Ràng buộc | |---|---|---| | 1 | ~3.5~ | ~N, Q \le 5000~. | | 2 | ~3.5~ | ~N, Q \le 10^5~. |