Có ~ n ~ thị trấn ở Byteotia, được nối bởi đúng ~ n-1 ~ con đường. Mỗi con đường kết nối trực tiếp 2 thị trấn. Mọi con đường đều dài như nhau và là đường 2 chiều. Biết rằng từ một thị trấn bất kỳ có thể đến bất kỳ một thị trấn nào khác qua 1 tuyến đường gồm 1 hoặc nhiều con đường. Nói cách khác, hệ thống đường xá có dạng hình cây.

Nhà vua Byteasar xứ Byteotia muốn xây dựng 3 khách sạn sang trọng để thu hút khách từ khắp thế giới. Nhà vua muốn đặt các khách sạn ở các thị trấn khác nhau và các khoảng cách giữa 2 khách sạn bất kỳ bằng nhau.

Hãy giúp nhà vua tính ra số địa điểm có thể có của những khách sạn này trên xứ Byteotia.

Dữ liệu vào

Dòng đầu tiên của ghi số ~ n ~ là số lượng thị trấn của Byteotia. Các thị trấn được đánh số từ 1 đến ~ n ~. Các con đường được miêu tả trong ~ n-1 ~ dòng. Mỗi dòng chứa 2 số nguyên ~ a ~ và ~ b ~ ~ (1 ≤ a, b ≤ n) ~ thể hiện có 1 con đường kết nối 2 thị trấn ~ a ~ và ~ b ~.

Kết quả

In ra số cách xếp 3 khách sạn.

Ràng buộc

• ~ 1 ≤ n ≤ 5000 ~
• Ít nhất 50% số test thỏa mãn ~ 1 ≤ n ≤ 500 ~.

Ví dụ:

Input 1

7
1 2
5 7
2 5
2 3
5 6
4 5 

Output 1

5