Tý có \(N\) ma trận \(A_1, A_2, \dots, A_N\). Ma trận \(A_i\) có kích thước \(d_{i-1} imes d_i\). Hãy đặt dấu ngoặc để nhân tất cả các ma trận với tổng phép nhân vô hướng ít nhất. Chi phí nhân ma trận \(p imes q\) và \(q imes r\) là \(p imes q imes r\).

Đị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