Tý có một khúc gỗ dài \(L\) mét, trên đó có \(N\) vị trí cắt \(x_1 < x_2 < \dots < x_N\). Bạn cần cắt khúc gỗ tại tất cả các vị trí đó. Mỗi lần cắt một khúc gỗ độ dài \(len\) tốn chi phí đúng bằng \(len\). Các lần cắt độc lập, bạn có thể chọn thứ tự cắt bất kỳ. Tìm tổng chi phí nhỏ nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Ràng buộc