### ** omnomnom2**

## Omnomnom2

The Zookeeper has decided to arrest all the hedgehogs. As the hedgehogs stole from an orange tree, the prison will be in the form of a tree. There are N nodes (1 ≤ N ≤ 500000) and N-1 edges. Each node has exactly 1 hedgehog.

As hedgehogs are sociable creatures, each of them wants to send a message to every other hedgehog. Each message travels a distance equal to the number of edges traversed between the 2 corresponding hedghogs.

Help FNH find out the total distance travelled by all messages!

### Input format

The first line of input contains 1 integer N

The next N-1 lines of input contains 2 integers a and b, representing an edge from node a to node b.

It is guaranteed that a tree will be formed from the egdes.

### Output format

Output 1 integer, the total distance travelled by the messages

### Subtasks

Subtask 1: Sample TC

Subtask 2: 1 ≤ N ≤ 1000

Subtask 3: 1 ≤ N ≤ 500000

### Sample Testcase

Input:

8

1 2

1 3

1 4

1 5

4 6

4 7

4 8

Output:

116