Intervals on Tree

Input

The first line contains number $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5). Each of the next $n - 1$ n - 1 lines contains two vertices ( $u_{i}$ u_i, $v_{i}$ v_i) ( $1 \leq u_{i}, v_{i} \leq n$ 1 \le u_i, v_i \le n) - an edge in the graph.

Output

Print the value of the sum.

Examples

Example 1

Loading

Note

We have six possible pairs ( $L$ , $R$ ) as follows:

For $L = 1$ L = 1, $R = 1$ R = 1, $S = {1}$ S = \{1\} and we have $1$ connected component.

For $L = 1$ L = 1, $R = 2$ R = 2, $S = {1, 2}$ S = \{1, 2\} and we have $2$ connected components.

For $L = 1$ L = 1, $R = 3$ R = 3, $S = {1, 2, 3}$ S = \{1, 2, 3\} and we have $1$ connected component, since $S$ contains both endpoints of each of the edges $1$ , $2$ .

For $L = 2$ L = 2, $R = 2$ R = 2, $S = {2}$ S = \{2\} and we have $1$ connected component.

For $L = 2$ L = 2, $R = 3$ R = 3, $S = {2, 3}$ S = \{2, 3\} and we have $1$ connected component, since $S$ contains both endpoints of Edge $2$ .

For $L = 3$ L = 3, $R = 3$ R = 3, $S = {3}$ S = \{3\} and we have $1$ connected component.

The sum of these is $7$ .