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!
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 1 integer, the total distance travelled by the messages
Input:
8
1 2
1 3
1 4
1 5
4 6
4 7
4 8
Output:
116
| Subtask | Score |
|---|---|
| 1 | 0 |
| 2 | 21 |
| 3 | 79 |