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 1: Số nguyên \(N\) (\(1 \le N \le 500\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 2 số nguyên \(u, v\) mô tả cạnh của cây.

Định dạng đầu ra

• In ra số cách chia cây thành các thành phần liên thông.

Ví dụ

Input:

3
1 2
2 3

Output:

4

Giải thích: Có \(2^{N-1} = 2^2 = 4\) cách chọn tập cạnh để cắt.

Ràng buộc & Subtasks