Tấn công Xenon (MEX trên cây)

Cho một cây gồm $n$ đỉnh, được đánh số từ $1$ đến $n$. Cây có đúng $n-1$ cạnh nối các đỉnh.

Ta gán cho mỗi cạnh một số nguyên thuộc tập $\{0,1,2,\dots ,n-2\}$, sao cho mỗi số xuất hiện đúng một lần (tức là gán là một hoán vị của các số từ $0$ đến $n-2$ lên các cạnh).

Với mỗi cặp đỉnh $(u,v)$ thoả $1\le u<v\le n$, gọi $mex(u,v)$ là số nguyên không âm nhỏ nhất không xuất hiện trên bất kỳ cạnh nào của đường đi đơn từ $u$ đến $v$ trên cây.

Đặt:

$$S=\sum _{1\le u<v\le n}mex(u,v).$$

Hãy tìm giá trị lớn nhất có thể của $S$ trên tất cả các cách gán nhãn hợp lệ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ ($1\le u_i,v_i\le n$; $u_i\ne v_i$) — mô tả một cạnh nối hai đỉnh $u_i$ và $v_i$. Các cạnh được đảm bảo tạo thành một cây.

Dữ liệu ra

In ra một số nguyên duy nhất — giá trị lớn nhất có thể của $S$.

Ràng buộc

• $2\le n\le 3000$.

Ví dụ