p02617 AtCoder Beginner Contest 173 - 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
```python
def main():
    N = int(input())
    edges = [list(map(int, input().split())) for _ in range(N - 1)]
    ans = N * (N + 1) * (N + 2) // 6
    for e in edges:
        u, v = min(e), max(e)
        ans -= u * (N - v + 1)
    print(ans)


if __name__ == '__main__':
    main()
```