Uolevi is visiting a foreign country with lots of tulips, windmills and of course, canals. Even on vacation Uolevi can't help but come up with tasks, and as such, he decided to count the number of canals in the country.

The country's waterways can be represented as a connected graph with n nodes and n-1 edges (that is, as a tree).

Uolevi calls a path (a, b) from node a to node b in this graph a canal, if the minimum index of any node on the path is a, and the maximum index of any node on the path is b.

Given the graph representing the waterways, output how many canals it contains. That is, output the number of ordered pairs (a, b) such that the minimum index of a node on the path from a to b is a, and the maximum index is b.

With this definition, pairs (a, a) are always counted once.

Input

The first line of input contains a single integer n: the number of nodes.

After this, n-1 lines follow, the i'th containing two integers a_i and b_i: nodes a_i and b_i are connected by an edge.

Output

Output a single integer: The number of canals.

Constraints

• 1 \leq n \leq 10^{5}
• 1 \leq a_{i} < b_{i} \leq n

Example

Input:

5
1 2
2 3
3 4
4 5

Output:

15

Explanation:
All 15 pairs (a, b) where a \leq b are canals

Example 2

Input:

4
3 2
2 1
4 2

Output:

9

Explanation:
The canals are

(1 1), (1 2), (1 3), (1 4), (2 2),
(2 3), (2 4), (3 3), (4 4).