Tý có \(N\) quả bóng xếp thành hàng, quả \(i\) có số \(a_i\). Mỗi lần bạn chọc một quả bóng \(i\) và nhận được \(None\)a_{i-1} imes a_i imes a_{i+1}\( điểm. Sau khi chọc, các quả bóng còn lại xích lại gần nhau. Bạn có thể chọc theo thứ tự bất kỳ. Tìm tổng điểm lớn nhất có thể nhận. (Quy ước \)a_0 = a_{N+1} = 1~).

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