Tàu điện ngầm của Sergey

Một hệ thống tàu điện ngầm có $N$ trạm, được đánh số từ $1$ đến $N$. Một số cặp trạm được nối trực tiếp bằng đường hầm, và toàn bộ hệ thống tạo thành một cây: giữa hai trạm bất kỳ tồn tại đúng một đường đi đơn. Khoảng cách giữa hai trạm là số đường hầm ít nhất phải đi qua để di chuyển giữa chúng.

Người ta quyết định nâng cấp hệ thống bằng cách xây thêm đường hầm: với mọi cặp trạm $u$ và $v$ chưa được nối trực tiếp nhưng có chung một trạm láng giềng $w$ (tức là đã có đường hầm $u-w$ và $w-v$), hãy xây thêm một đường hầm nối trực tiếp $u$ và $v$.

Lưu ý rằng tất cả các đường hầm mới được xác định dựa trên hệ thống ban đầu, và được xây cùng lúc; các đường hầm mới không sinh ra thêm đường hầm nào khác.

Hãy tính tổng khoảng cách giữa tất cả các cặp trạm trong hệ thống sau khi nâng cấp. Mỗi cặp trạm không thứ tự được tính đúng một lần.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $N$: số trạm.
• $N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$: có một đường hầm nối trực tiếp trạm $u_i$ và trạm $v_i$.

Dữ liệu đảm bảo $N$ trạm và $N-1$ đường hầm tạo thành một cây.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng khoảng cách giữa tất cả các cặp trạm sau khi nâng cấp.

Ràng buộc

• $2\le N\le 200000$
• $1\le u_i,v_i\le N$, $u_i\ne v_i$

Ví dụ