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


Submitting .cpp to 'omnomnom2'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 63
Your best score: 0
Source: Classic Problem

Subtask Score
1 0
2 21
3 79