Intervals on Tree

We have a tree with N vertices and N-1 edges, respectively numbered 1, 2,\cdots, N and 1, 2, \cdots, N-1. Edge i connects Vertex u_i and v_i.

For integers L, R (1 \leq L \leq R \leq N), let us define a function f(L, R) as follows:

• Let S be the set of the vertices numbered L through R. f(L, R) represents the number of connected components in the subgraph formed only from the vertex set S and the edges whose endpoints both belong to S.

Compute \sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• The given graph is a tree.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N u_1 v_1 u_2 v_2 : u_{N-1} v_{N-1}

Output

Print \sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R).

Examples

Input

3 1 3 2 3

Output

7

Input

2 1 2

Output

3

Input

10 5 3 5 7 8 9 1 9 9 10 8 4 7 4 6 10 7 2

Output

113

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N u_1 v_1 u_2 v_2 : u_{N-1} v_{N-1}

outputFormat

Output

Print \sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R).

Examples

Input

3 1 3 2 3

Output

7

Input

2 1 2

Output

3

Input

10 5 3 5 7 8 9 1 9 9 10 8 4 7 4 6 10 7 2

Output

113

样例

2
1 2

3