Distance Sum Problem
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Given an undirected connected graph with n vertices and n edges, with no multiple edges or self-loops, find the sum of distances between every pair of vertices whose degree is 1. The distance between two vertices is the minimum length among all simple paths between them. The length of a simple path is the number of edges on that path.

输入描述:

The first line contains an integer n (3\le n\le 5 \times10^5).

The next n lines each contain two integers u,v (1\le u,v\le n,u\neq v), indicating an edge in the graph. It is guaranteed that there are no multiple edges in the graph.

输出描述:

Output a single integer representing the answer.
示例1

输入

复制 
8
1 2
2 3
3 6
3 8
8 7
8 6
6 5
4 6

输出

复制 
20

说明

The undirected connected graph described in the example is shown below.